дан отрезок линии двумя точками

p1(x1,y1), p2(x2,y2)

отрезок может быть в любом положении, не только вертикально или горизонтально

также есть прямоугольник заданый верхней-левой

Pbl(xtl,ytl)

и правой-нижней

Pbr(xbr,ybr)

точками

надо узнать пересекается ли данный отрезок с премоугольником или нет.

Спасибо

Здравствуйте, Holms, Вы писали:

H>также есть прямоугольник заданый верхней-левой и правой-нижней точками

Вынужден огорчить: две точки задают семейство прямоугольников, вписанных в окружность, диаметром которой является отрезок между этими точками.

Здравствуйте, Кодт, Вы писали:

К>Вынужден огорчить: две точки задают семейство прямоугольников, вписанных в окружность, диаметром которой является отрезок между этими точками.

я имел ввиду что-то в этом роде

Здравствуйте, Holms, Вы писали:

H>дан отрезок линии двумя точками
H>также есть прямоугольник заданый верхней-левой и правой-нижней точками
H>надо узнать пересекается ли данный отрезок с премоугольником или нет.
Не совсем понятно, что значит "пересекается". Если отрезок лежит полностью внутри прямоугольника, он пересекается с этим прямоугольником?

"Лобовое" решение:
1. Построить уравнение прямой, содержащей отрезок в виде Ax+By+C=0.
Уравнение прямой, проходящей через точки (x1,y1) и (x2, y2) задается так:

x-x1    y-y1
----- = -----
x2-x1   y2-y1
Тогда
(x-x1)*(y2-y1)=(y-y1)*(x2-x1)
x*(y2-y1)-x1*(y2-y1)=y*(x2-x1)-y1*(x2-x1)
x*(y2-y1)+y*(x1-x2)-x1*(y2-y1)+y1*(x2-x1)=0

Получается A=y2-y1, B=x1-x2, C=-x1*(y2-y1)+y1*(x2-x1).
2. Проверить для каждой стороны прямоугольника
а) пересечение прямой, содержащей отрезок, со стороной
б) пересечение отрезка с прямой, содержащей сторону

Проверяется просто: пусть нам надо проверить пересечение прямой Ax+By+C=0 и отрезка (x1,y1)-(x2,y2). Если

(Ax1+By1+C)*(Ax2+By2+C)<0,

то прямая пересекает отрезок.

Если для какой-то из сторон это выполняется, то пересечение есть.

Если надо, проверку попадания отрезка внутрь прямоугольника, думаю, проверить несложно

Здравствуйте, Holms, Вы писали:

H>дан отрезок линии двумя точками
H>

H>p1(x1,y1), p2(x2,y2)
H>

H>отрезок может быть в любом положении, не только вертикально или горизонтально

H>также есть прямоугольник заданый верхней-левой
H>

H>Pbl(xtl,ytl)
H>

H> и правой-нижней
H>

H>Pbr(xbr,ybr)
H>

H> точками

H>надо узнать пересекается ли данный отрезок с премоугольником или нет.
Задача сводится к проверке того, что 2 отрезка пересекаются. Т.е. если мы можем узнать, пересекаются ли 2 отрезка, то решить эту задачу легко.
Пусть есть 2 отрезка. Зададим параметрически уравнения прямых, на которых лежат эти отрезки. Делается это так:
если есть отрезок (x0,y0) — (x1, y1), то уравнение можно задать так: {x=x0+a*t, y=y0+b*t}, где a=x1-x0, b=y1-y0. Тогда, очевидно, отрезку будут принадлежать точки, для которых 0 <= t <= 1.
Составляем систему уравнений, описывающую точку пересечения. Если концы отрезков обозначить как (x0_1, y0_1), (x1_1, y1_1) для первого отрезка, и (x0_2, y0_2), (x1_2, y1_2) — для второго, то система примет вид:

x0_1 + a1*t = x0_2 + a2*u;
y0_1 + b1*t = y0_2 + b2*u;

Решаем её относительно t,u.
Возможны варианты:
1) Решений бесконечно много. Т.е. прямые совпадают. Рассматриваем точки второго отрезка, как точки прямой, содержащей первый отрезок. Высчитываем для них значения параметров t1, t2. Для того, чтобы отрезки пересекались, необходимо, чтобы "пересекались" отрезки [0; 1] и [t1; t2].
2) Решений нет. Прямые параллельны, отрезки не пересекаются.
3) Решение единственно. Тут надо проверить, что выполняются одновременно 2 условия:
0<=t<=1, 0<=u<=1.

Здравствуйте, Holms.
Возможно, вот это пригодится.

Здравствуйте, conraddk, Вы писали:

C>Здравствуйте, Holms, Вы писали:

H>>дан отрезок линии двумя точками
H>>также есть прямоугольник заданый верхней-левой и правой-нижней точками
H>>надо узнать пересекается ли данный отрезок с премоугольником или нет.
C>Не совсем понятно, что значит "пересекается". Если отрезок лежит полностью внутри прямоугольника, он пересекается с этим прямоугольником?
да

C>"Лобовое" решение:
а вот за это спасибо

C>Если надо, проверку попадания отрезка внутрь прямоугольника, думаю, проверить несложно
возможно

Здравствуйте, Holms, Вы писали:

При условии ограничения
только вертикальности или горизонтальности отрезка задача сводится
к пересечинию двух прямоугольников, что тривиально.

rect line(x1,y1,x2,y2);
rect r(point p1, point p2);

if( r && line ) 
  printf("Got it!");

описание

bool operator && (rect ls, rect rs)

смотри здесь:
http://www.terra-informatica.org/gool/geometry.h.htm

Здравствуйте, Кодт, Вы писали:

H>>также есть прямоугольник заданый верхней-левой и правой-нижней точками

К>Вынужден огорчить: две точки задают семейство прямоугольников, вписанных в окружность, диаметром которой является отрезок между этими точками.

А это как?

Здравствуйте, c-smile, Вы писали:

CS>Здравствуйте, Кодт, Вы писали:

H>>>также есть прямоугольник заданый верхней-левой и правой-нижней точками

К>>Вынужден огорчить: две точки задают семейство прямоугольников, вписанных в окружность, диаметром которой является отрезок между этими точками.

CS>А это как?

А так:

Угол между любой точкой на окружности и диаметрально противоположными точками — 90°.
Итого, берём заданный отрезок, находим его середину, поворачиваем на произвольный угол. Так мы получили 2 диагонали прямоугольника.

Естественно, что если есть дополнительное требование — параллельность сторон осям координат — то две точки задают прямоугольник однозначно.

Здравствуйте, Кодт, Вы писали:

К>А так:
К>
К>Угол между любой точкой на окружности и диаметрально противоположными точками — 90°.
К>Итого, берём заданный отрезок, находим его середину, поворачиваем на произвольный угол. Так мы получили 2 диагонали прямоугольника.

Это то понятно...
Но как оно согласуется с начальным определением?
H>>>>также есть прямоугольник заданый верхней-левой и правой-нижней точками

К>Естественно, что если есть дополнительное требование — параллельность сторон осям координат — то две точки задают прямоугольник однозначно.

"верхней-левой и правой-нижней" и есть это требование.

Здравствуйте, c-smile, Вы писали:

CS>Здравствуйте, Кодт, Вы писали:

К>>А так:
К>>
К>>Угол между любой точкой на окружности и диаметрально противоположными точками — 90°.
К>>Итого, берём заданный отрезок, находим его середину, поворачиваем на произвольный угол. Так мы получили 2 диагонали прямоугольника.

CS>Это то понятно...
CS>Но как оно согласуется с начальным определением?
H>>>>>также есть прямоугольник заданый верхней-левой и правой-нижней точками

К>>Естественно, что если есть дополнительное требование — параллельность сторон осям координат — то две точки задают прямоугольник однозначно.

CS>"верхней-левой и правой-нижней" и есть это требование.

CS>

Пересечение отрезка с прямоугольником нельзя свести к пересечению двух прямоугольникв.

Копай Нео, копай -- летать научишься. © Matrix. Парадоксы

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, Holms, Вы писали:

H>>также есть прямоугольник заданый верхней-левой и правой-нижней точками

К>Вынужден огорчить: две точки задают семейство прямоугольников, вписанных в окружность, диаметром которой является отрезок между этими точками.

Написано же верхней-левой и правой-нижней точками. У любого прямоугольника со сторонами непараллельными осям координат таких точек не будет.

Здравствуйте, c-smile, Вы писали:

CS>Здравствуйте, Holms, Вы писали:

CS>При условии ограничения
CS>только вертикальности или горизонтальности отрезка задача сводится
CS>к пересечинию двух прямоугольников, что тривиально.
к сожалению такое условие не удовлетворяет потребностям

Здравствуйте, Holms, Вы писали:

H>дан отрезок линии двумя точками p1(x1,y1), p2(x2,y2)
H>также есть прямоугольник заданый верхней-левой Pbl(xtl,ytl) и правой-нижней Pbr(xbr,ybr)
H>надо узнать пересекается ли данный отрезок с премоугольником или нет.

Буду считать, что пересечение — это пересечение твоего отрезка с хотя бы одной из сторон прямоугольника. Если нужно отловить попадание отрезка внутрь, то это несложно сделать первым шагом.

Соотвественно будем по очереди проверять каждую сторону отрезка на пересечение со стороной прямоугольника, тоже являющейскя отрезком, т.е. будем искать пересечение двух отрезков.

В общем случае есть разные методы, но у нас один из отрезков заведомо горизонтален или вертикален.

Для горизонтального отрезка:

Проверим, что одна точка первого отрезка лежит выше, а другая — ниже второго, горизонтального, отрезка. Если это не так, то отрезки не пересекаются, иначе идем дальше.

Решив несложное уравнение найдем x координату точки пересечения первого отрезка и прямой, содержащей второй отрезок: x=(x1(y2-h)-x2(y1-h))/(y2-y1). Где {x1,y1} — координаты первой точки первого отрезка, {x2,y2} — координаты второй точки первого отрезка, h — координтата y второго отрезка.

Проверим, что найденная координата больше меньшей и меньше большей из координат второго отрезка. Если это так, отрезки пересекаются, иначе — нет.

Для вертикального отрезка: аналогично горизонтальному.

... << RSDN@Home 1.1.3 beta 2 >>

Здравствуйте, Tan4ik, Вы писали:

T>Написано же верхней-левой и правой-нижней точками. У любого прямоугольника со сторонами непараллельными осям координат таких точек не будет.

Нда... Твоя правда. Могут быть "более правая чем верхняя" и т.п.

Люди, одумайтесь! Это же классика!
Берется один гугол и в нем находится "алгоритм Коэна-Сазерленда":
http://program.rin.ru/razdel/html/898.html

Ну а уж посчитать пересечение прямой, заданной отрезком с "ортогональю" — задача тривиальная.