Пересечение отрезков. Вопрос на засыпку

← →
Daemys (2004-01-22 12:13) [0]

Дано:
два отрезка прямых в правоориентированной системе координат

Требуется:
определить, имеют ли отрезки общую точку.

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

Вариант решения №2:
При любом возможном расположении отрезков не приводит к делению на ноль. Как это сделать?

Примечание: мне этот способ известен.

← →
MBo (2004-01-22 12:22) [1]

Если известен - зачем спрашиваешь?

← →
Daemys (2004-01-22 12:25) [2]

>MBo © (22.01.04 12:22) [1]
А я и не спрашиваю. Просто интересно сколько времени понадобится другим, чтобы такой способ придумать. К тому это лишний повод подумать, что никогда не помешает.

← →
fag2000 (2004-01-22 12:26) [3]

Деление на 0 - отрезки параллельны.

← →
Danilka (2004-01-22 12:28) [4]

[2] Daemys © (22.01.04 12:25)
на жабе это выглядит так:
кдасс: java.awt.geom.Line2D
метод: intersectsLine

public boolean intersectsLine(double X1,
double Y1,
double X2,
double Y2)
Tests if the line segment from (X1, Y1) to (X2, Y2) intersects this line segment.

:))
Ежели очень хочется - так уж и быть, заледу в исходники и вытащу тебе эту процедуру.
Кроме того, когда-то находил неплохой сайт с алгоритмами по геометрии, а может даже и на этом сайте есть в разделе создания игр. :))

← →
Рамиль (2004-01-22 12:29) [5]

> Данный способ не годится в силу своей медленности

С чего это он медленный, интересно? И проверка на деление на ноль вообще не проблема.

← →
pasha_golub (2004-01-22 12:30) [6]

Daemys © (22.01.04 12:13)
Как заданы отрезки?

1) Точкой и вектором
2) Двумя точками
3) Системой уравнений
4) ...

← →
fag2000 (2004-01-22 12:32) [7]

2 - вычислять отклонение для концов этих отрезков относительно друг друга.

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

← →
Daemys (2004-01-22 12:32) [8]

>Рамиль © (22.01.04 12:29) [5]
Проблема возникает, когда отрезков много, и надо проверить, что никакие два отрезка из всего множества не перекаются.

← →
Daemys (2004-01-22 12:34) [9]

>pasha_golub © (22.01.04 12:30) [6]
Координатами начальной и конечной точек

>fag2000 (22.01.04 12:32) [7]
тепло. Но что такое "знаки отклонения"

← →
Nikolay M. (2004-01-22 12:35) [10]

> Daemys © (22.01.04 12:32) [8]
> Проблема возникает, когда отрезков много, и надо проверить,
> что никакие два отрезка из всего множества не перекаются.

Оптимизировать однако надо. Например, вписать каждый отрезок в прямоугольники со сторонами, параллельными осям координат и не проверять отрезки, заведомо лежащие в разных прямоугольниках.

← →
pasha_golub (2004-01-22 12:36) [11]

Daemys © (22.01.04 12:34) [9]
Предположу, что можно проверить находятся ли концы одного отрезка в одной полуплоскости относительно другого. Хотя идиотизм это :-)

← →
fag2000 (2004-01-22 12:42) [12]

2
> Daemys © (22.01.04 12:34) [9]

Общеизвестно, что любая прямая имеет уравнение вида f(x,y)=a*x+b*y+c=0. Таким образом оно разбивает полуплоскость на 2 полуплоскости: при подстановки в уранение точки из 1 полуплоскости f(x,y)>0 из другой f(x,y)<0. Соответственно отклонением называется величина f(x,y) при подстановки в него координат точки.

← →
Daemys (2004-01-22 12:43) [13]

>Nikolay M. © (22.01.04 12:35) [10]
Вопрос не об оптимизации, а о логике, и ходе мысли, как сделать без деления на ноль, а оптимизация не помешает.

>pasha_golub © (22.01.04 12:36) [11]
Почему идиотизм?

← →
fag2000 (2004-01-22 12:44) [14]

> pasha_golub © (22.01.04 12:36) [11]

в противном случае получаем все прелести плохообусловленных СЛАУ.

← →
Daemys (2004-01-22 12:45) [15]

>fag2000 (22.01.04 12:42) [12]
При вычислении уравнения прямой и можно нарвать на нестабильность или деление на ноль, отсюда такой способ не катит.

← →
fag2000 (2004-01-22 13:08) [16]

2
> Daemys © (22.01.04 12:45) [15]

А курс аналитической геометрии почитать? или хотя бы подумать?

Вектор задан 2 точками. т.е. a и b уже известны. Для их нахождения не надо выполнять делений. Достаточно вычитаний.
c находим из уравнения:
a*x1+b*y1+c=0 -> с=-(a*x1+b*y1+c) - где же тут деления.

← →
pasha_golub (2004-01-22 13:12) [17]

Ну знаете ли. Концы отрезка могут находится в разных полуплоскостях, но отрезки могут не пересекаться. Так что, я чего-то не пойму хода ваших мыслей.

← →
fag2000 (2004-01-22 13:14) [18]

2
pasha_golub © (22.01.04 13:12) [17]

Концы одного да. Но одновременно концы обоих - нет. Нарисуй - станет понятно.

← →
pasha_golub (2004-01-22 13:17) [19]

fag2000 (22.01.04 13:14) [18]

Не рисовал, представил в мозгу. :-)
Точно, согласен.

← →
Daemys (2004-01-22 13:32) [20]

>fag2000 (22.01.04 13:08) [16]
Тогда приведите формулу, в которой по двум точкам однозначно вычисляются коэффициенты a и b одними только вычитаниями?

← →
Думкин (2004-01-22 13:38) [21]

> [20] Daemys © (22.01.04 13:32)

(y2-y1,x1-x2)

← →
Radionov Alexey (2004-01-22 13:41) [22]

> [20] Daemys © (22.01.04 13:32)
(x1,y1), (x2,y2) - точки
Уравнение прямой, через них проходящее:
(y2-y1)*x+(-x2+x1)*y+x2*y1-y2*x1 = 0

← →
fag2000 (2004-01-22 13:45) [23]

Ну, уважаемый, однако для человека с ВО это слишком. Или yandex поломался?
http://borlpasc.narod.ru/docym/skola/2_1/2_1_3.htm
Уравнение прямой в общем виде:
F(x,y) = A*x + B*y + C = 0;
где A= y2-y1; B=-(x2-x1); C= -A*x1 - B*y1;

← →
Radionov Alexey (2004-01-22 13:50) [24]

>fag2000 (22.01.04 13:45) [23]
Если это ты мне, то просто подставь значения и раскрой скобки с глазами.

И причем тут yandex, когда речь идет об устном упражнении?

← →
Думкин (2004-01-22 13:54) [25]

> [24] Radionov Alexey © (22.01.04 13:50)

Это он явно не тебе, а автору ветки.

← →
Radionov Alexey (2004-01-22 14:01) [26]

>fag2000
Cорри за мой пост [24]. Я почему-то на свой счет принял :)

>Думкин © (22.01.04 13:54) [25]
Совсем я нервный стал :))

← →
pasha_golub (2004-01-22 14:04) [27]

Radionov Alexey © (22.01.04 14:01) [26]
Гы, нервы, они это... не восстанавливаются. :-)

← →
Clift (2004-01-22 14:18) [28]

В декардовой системе координат уровнение прямой описывается как y=a*x+b. Прямые будут пересекаться если они не параллельны следовательно если дано
первая прямая y=a1*x+b1 (y=2x+5)
вторая прямая y=a2*x+b2 (y=4x-3)
задача состоит в том чтобы узнать параллельны прямые или нет
b1 и b2 двигают прямую по вертикали
кофициент а1 и а2 опряделяют угол наклона прямой по отношению к
оси ИКСОВ если а1 или а2 равен нулю то это не прямая а точка
отсюда если даны прямые то из условия следует что а1 и а2 <>0
если а1=а2 верное то две прямые парралельны следовательно нет точки пересечения
возможно я неправ но геометрия была так давно...

← →
Романов Р.В. (2004-01-22 14:23) [29]

> если а1 или а2 равен нулю то это не прямая а точка

С чего это вы взяли?

← →
Clift (2004-01-22 14:26) [30]

← →
MBo (2004-01-22 14:26) [31]

Вроде бы так получается (если не учитывать легкопроверямую параллельность)

function AreSegmentsIntersect(pa0, pa1, pb0, pb1: TPoint): Boolean; function DetSign(p1, p2, p3: TPoint): Integer; var Det: Integer; begin Det := (p1.x - p3.x) * (p2.y - p3.y) - (p2.x - p3.x) * (p1.y - p3.y); Result := Ord(Det <> 0) - (Det shr 31) shl 1; end; begin Result := (DetSign(pa0, pa1, pb0) <> DetSign(pa0, pa1, pb1)) and (DetSign(pa0, pb0, pb1) <> DetSign(pa1, pb0, pb1)); end;

← →
Думкин (2004-01-22 14:27) [32]

> [28] Clift © (22.01.04 14:18)

У... не все так, не все прямые вы так запишите, например, ось Оу.
И... параллельности или не параллельности недостаточно.
Да не мучтесь - ответ выше.

← →
Clift (2004-01-22 14:27) [33]

Во блин прямая будет параллельно оси ИКСОВ но это не влияет на условие а1=а2

← →
Clift (2004-01-22 14:33) [34]

← →
Думкин (2004-01-22 14:35) [35]

> [34] Clift © (22.01.04 14:33)

Веселый ты.

> [28] Clift © (22.01.04 14:18)
> В декардовой системе координат уровнение прямой описывается как y=a*x+b.

Противоречия не видим?

← →
Daemys (2004-01-22 14:38) [36]

>Clift © (22.01.04 14:18) [28]
Речь идёт о пересечении отрезков, а не прямых.

fag2000 указал способ правильно, но я действовал по-другому - через направляющие косинусы и поворот координатных осей. А мысли о делимости на ноль пришли из справочника Корнов, где формула записывается как (y-y1)/(y2-y1) = (x-x1)/(x2-x1). Она конечно легко преобразовывается в указанные выше, но я сразу как-то непопендрил. бывает.

← →
Clift (2004-01-22 14:42) [37]

← →
NikotiN (2004-01-22 14:45) [38]

Чтоб определить пересечение отрезков надо:
построить по два вектора из каждого конца отрезка1 к концам отрезка2.
и сравнить углы между парами векторов (то есть по тупому: посмотреть в одинаковые ли стороны смотрят уголки образованные из векторов)

← →
pasha_golub (2004-01-22 15:25) [39]

Пересечение отрезков. Вопрос на засыпку Найти похожие ветки