Проверьте, не сталкиваются ли два сегмента линии (только проверьте, пересекаются ли они, а не где)

Мне нужен быстрый алгоритм для проверки пересечения двух не бесконечных линий. Быть быстрым, потому что он будет работать на сотовом телефоне много.

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

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

Пожалуйста, помогите мне найти хороший и рабочий алгоритм для этого.

Просто чтобы быть ясным: мне нужна функция, которую вы даете...
lineApointAx
lineApointAy
lineApointBx
lineApointBy
lineBpointAx
lineBpointAy
lineBpointBx
lineBpointBy
... и возвращает true или false в зависимости от того, пересекаются ли две линии.

Я был бы признателен, если бы вы ответили (псевдо) кодом, а не формулами.

Ответ 1

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

(B _x - A _x) (P _y - B _y) - (B _y - A _y) (P _x - B _x)

EDIT:
Чтобы сказать это, предположим, что вы смотрите на два сегмента, [AB] и [CD]. Сегменты пересекаются тогда и только тогда, когда ((A и B имеют разные стороны [CD]) и (C и D находятся по разные стороны от [AB])).

Чтобы увидеть, находятся ли две точки P и Q по разные стороны отрезка [EF], вычислите два кросс-произведения, один для P и один для Q:

(F _x - E _x) (P _y - F _y) - (F _y - E _y) (P _x - F _x)

(F _x - E _x) (Q _y - F _y) - (F _y - E _y) (Q _x - F _x)

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

Ответ 2

Если вы являетесь двумя заданными точками (X1, Y1) и (X2, Y2), представьте, что обе являются бесконечными линиями, а не только сегментами:

Определите формулу для обоих (см. http://en.wikipedia.org/wiki/Linear_equation#Two-point_form)
Определите точку пересечения для двух линий (см. http://zonalandeducation.com/mmts/intersections/intersectionOfTwoLines1/intersectionOfTwoLines1.html)
Если X1 < intersectionX < X2 и Y1 < пересечение < Y2, то да, сегменты пересекаются.