Пусть лежат, где хотят.
Точки: (x_1, y_1), (x_2, y_2), (x_3, y_3), (x_4, y_4).
Сегменты, соединяющие первую со второй и третью с четвертой:
s (x_1, y_1) + (1 - s)(x_2, y_2)
и
t(x_3, y_3) + (1 - t)(x_4, y_4)
0 <= t, s <= 1
Решаем систему линейных уравнений с двумя неизвестными: s и t
s (x_1, y_1) + (1 - s)(x_2, y_2) = t(x_3, y_3) + (1 - t)(x_4, y_4)
или
(x_1 - x_2)s - (x_3 - x_4)t = x_4 - x_2
(y_1 - y_2)t - (y_3 - y_4)t = y_4 - y_2
Если система не имеет решений -- отрезки параллельны.
Если система имеет одно решение -- проверяем условие 0 <= t, s <= 1 Выполнено -- отрезки пересекаются, по s и t находим, где. Невыполнено -- пересекаются продолжения отрезков.
Если система имеет бесконечно много решений -- отрезки лежат на одной прямой. Решаем уравнения
(x_2, y_2) = t(x_3, y_3) + (1 - t)(x_4, y_4)
и
(x_1, y_1) = t(x_3, y_3) + (1 - t)(x_4, y_4)
Если решение t есть, и находится между нулем и единицей -- отрезки пересекаются по бесконечному числу точек. Если есть и равно нулю и единице -- то по одной точке. Если решение больше единицы или меньше нуля -- пересечения нет.
Думал, пока печатал. Еще какие-нибудь сложнейшие алгоритмы нужны?
