54
правки
Изменения
Нет описания правки
Неформальное объяснение второго свойства: рассмотрим тройку векторов, таких, что если смотреть из конца первого вектора на второй, то он будет левее, чем третий. Перестановка второго и третьего векторов будет означать, что второй вектор будет виден правее третьего, что означает смену ориентации.
Заметим, что определитель является в точности кососимметричной линейно линейной формой от N N-мерных векторов, а значит, подходит для вычисления ориентации набора векторов.
=== Ориентация точек ===
О точном вычислении ориентации см. раздел [[Пересечение_отрезков_и_поворот:_определение,_свойства,_вычисление#Ссылки | Ссылки]].
== Пересечение отрезков ==
Определить, пересекаются ли два отрезка, можно с помощью предиката поворота.
Ясно, что отрезки пересекаются тогда и только тогда, когда для каждого из отрезков его точки не лежат с одной стороны от второго отрезка.
Пусть даны отрезки <math>a_0 a_1</math> и <math>b_0 b_1</math>. Отрезки пересекаются, если
do_intersect = orientation(a0, a1, b0) != orientation(a0, a1, b1)
and orientation(b0, b1, a0) != orientation(b0, b1, a1)
В случае, если обе ориентации в одной из строк равны нулю, отрезки лежат на одной прямой, и в этом случае пересечение можно проверить способом, аналогичным пересечению отрезков на действительной прямой:
between(x, a0, a1) = (a0 <= x <= a1)
if a0 > a1
swap(a0, a1)
if b0 > b1
swap(b0, b1)
do_intersect = between(b0, a0, a1) || between(b1, a0, a1) || between(a0, b0, b1) || between(a1, b0, b1)
== Ссылки ==
