Пересекаються ли отрезки Опции

[RathaR]

Привет всем в Новом Году
Вспомнилась мне, задачка, которая фигурировала в цитате с баша, а именно:
"Даны координаты начала и конца двух отрезков, определить пересекаються ли они".
Вот я и задумался над этим... в голову пришел лишь один алгоритм:
1) У нас даны координаты 4 точек, запишем их в таком порядке, чтобы образовался полигон(для нахождения диагоналей).
2) Находим площадь этого полигона(половина произведения диагоналей на синус угла между ними).
3) Сравниваем полученый результат с половиной произведения наших отрезков на синус угла между ними.
4) Если площади совпали, значит отрезки являються диагоналями, а следовательно пересекаються, если нет, значит не перезекаються.
Если какая либо из заданых точек принадлежит другому отрезку, это ведь ничего не меняет, всерамно должен работать. Длинну отрезков по координатам найдем легко, углы между отрезками можна найти через модуль разности углов под которым расположен каждый из отрезков к горизонтали. А сами углы находим через арктангенс в паскале. Следовательно при реализаии проблем возникнуть не должно... но мне интересно, как еще можно решить эту задачу(желательно по проще)? Визуально-графический метод не предлагать

Сообщение отредактировано: RathaR - 1.01.2010 23:03

[andriano]

Сразу споткнулся на:

запишем их в таком порядке, чтобы образовался полигон

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

И чем, собственно, не устраивает наиболее очевидный алгоритм?
1. По координатам записываем уравнения прямых.
2. Решаем полученную систему уравнений, получая координаты точки пересечения прямых (если нет, значит, не пересекаются).
3. Узнаем, лежит ли точка пересечения внутри каждого из отрезков или вне его.

[TarasBer]

2. Решаем полученную систему уравнений, получая координаты точки пересечения прямых (если нет, значит, не пересекаются).

Ага разбирая отдельно случай вертикальных отрезков, горизонтальных, нулевого определитеся системы. Это отвратительное решение в лоб.
Как делал бы я.
Задаём прямую, содержащую отрезок 1 в виде ax+by+c = 0.
Подставляем в левую часть концы второго отрезка. Если получились числа одного знака - то не пересекаются. Если разного, то потом делаем то же самое, но наоборот - концы первого отрезка подставляем в уравнение для второго. Если опять разного знака - то пересекаются.


Добавлено через 2 мин.
Выглядело это примерно так:

function Intersect(X11, Y11, X21, Y21, X12, Y12, X22, Y22: double): boolean;
var
  d11, d21, d12, d22: double;
begin
  d11 := (x22 - x11) * (y12 - y11) - (x12 - x11) * (y22 - y11);
  d21 := (x22 - x21) * (y12 - y21) - (x12 - x21) * (y22 - y21);
  d12 := (x21 - x12) * (y11 - y12) - (x11 - x12) * (y21 - y12);
  d22 := (x21 - x22) * (y11 - y22) - (x11 - x22) * (y21 - y22);
  Result := (((d11 > 0) and (d21 < 0)) or ((d11 < 0) and (d21 > 0)))
  and (((d12 > 0) and (d22 < 0)) or ((d12 < 0) and (d22 > 0)));
end;

На самом деле, это результат выкидывания всего лишнего из функции, считающей квадрат расстояния между двумя отрезками.

Добавлено через 4 мин.

Вах! )) Отрезкм

И вижу я в той теме тот же ужас с разбором отдельного вертикального случая.
Я вообще терпеть не могу анизотропные решения (то есть, зависящие от направления и выбора системы координат).

Добавлено через 1 мин.
А ещё надо разобрать случай, когда отрезки ПОЧТИ вертикальны (да, да, делить на ПОЧТИ ноль тоже запрещено), и ПОЧТИ параллельны.
Короче, мой вариант лучше. И даже операция деления нигде не используется.

[sheka]

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

Класс! +1
Мне подобная идея сразу пришла в голову, только не получалось с реализацией, т.к. думал реализовать разницу знаков через вертикальную и горизонтальную прямые, которые бы проходили через одну из точек отрезка...А тут оказывается все намного проще)