54
правки
Изменения
→Пересечение отрезков
and orientation(b0, b1, a0) != orientation(b0, b1, a1)
В случае, если обе ориентации в одной из строк равны нулю, отрезки лежат на одной прямой, и в этом случае пересечение можно проверить способом, аналогичным пересечению отрезков на действительной прямой(считаем, что точки сравниваются лексикографически):
between(x, a0, a1) = (a0 <= x <= a1)
do_intersect = between(b0, a0, a1) || between(b1, a0, a1) || between(a0, b0, b1) || between(a1, b0, b1)
Если предикат вычисления ориентации был абсолютно точным, то таким же будет описанный алгоритм.
== Ссылки ==
