Пересечение отрезков и поворот: определение, свойства, вычисление

Аффинное пространство

Формальное определение есть, например, на википедии. Неформально: аффинное пространство - удобная геометрическая абстракция, рассматривающая точки (в отличие от векторов линейного пространства). Точки нельзя складывать между собой или умножать на число; к точке можно прибавить вектор, получив другую точку; можно получить вектор разности двух точек. Все приведенные операции обладают геометрически интуитивными и ожидаемыми свойствами.

Наряду с линейными комбинациями векторов рассматривают аффинные комбинации точек аффинного пространства [math]A[/math]: [math]\sum \lambda_i a_i[/math], где [math]\lambda_i \in \mathbb{R}, a_i \in A[/math]. По определению считают [math]\sum \lambda_i a_i = b + \sum \lambda_i \overrightarrow{(a_i - b)}, b \in A, \sum \lambda_i = 1[/math] (можно показать, что только в случае равенства единице суммы коэффициентов результат не зависит от выбора точки [math]b[/math]).

Также рассматривают понятие аффинной независимости точек (например, три точки на одной прямой аффинно зависимы). Набор [math]\{a_i\}_{i=0}^{k}[/math] точек называется аффинно (не-)зависимым, если линейно (не-)зависим набор векторов [math]\{\overrightarrow{a_i - a_0}\}_{i=1}^{k}[/math].

Ориентация

Ориентация векторов

Рассмотрим кососимметричную линейную форму от N N-мерных векторов, т.е. функцию [math]f: X \rightarrow \mathbb{R}[/math], обладающую свойством [math]f(x_1, x_2,\hdots, x_{n-1}, x_n) = -f(x_n, x_{n - 1},\hdots, x_2, x_1)[/math].

Из курса линейной алгебры известно, что любые две такие формы отличаются друг от друга только на некоторый множитель. Зафиксируем одну из таких форм (например, считая, что форма равна 1 на наборе из векторов выделенного базиса). Назовем ориентацией набора из N N-мерных векторов знак значения этой формы на этом наборе векторов.

Отметим свойства ориентации:

• Ориентация линейно зависимого набора векторов равна нулю
• Ориентация меняет знак при перестановке двух векторов в наборе

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

Заметим, что определитель является в точности кососимметричной линейной формой от N N-мерных векторов, а значит, подходит для вычисления ориентации набора векторов.

Ориентация точек

Аналогичным образом можно определить ориентацию набора из N+1 N-мерных точек. Ориентацией точек [math]\{a_i\}_{i=0}^{N}[/math] назовем ориентацию набора векторов [math]\{\overrightarrow{a_i - a_0}\}_{i=1}^{N}[/math]

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

• Ориентация набора аффинно-зависимых точек равна нулю
• Ориентация меняет знак при перестановке двух точек в наборе

Предикат левый поворот

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

Предикат "левый поворот" по набору точек определяет, верно ли, что их ориентация - левая. Используется в большинстве алгоритмов вычислительной геометрии.

Вычислить ориентацию точек [math]\{a_i\}_{i=0}^{N}[/math] (и, следовательно, предикат) можно через определитель набора векторов [math]\{\overrightarrow{a_i - a_0}\}_{i=1}^{N}[/math].

О точном вычислении ориентации см. раздел Ссылки.

Пересечение отрезков

Определить, пересекаются ли два отрезка, можно с помощью предиката поворота. Ясно, что отрезки пересекаются тогда и только тогда, когда для каждого из отрезков его точки не лежат с одной стороны от второго отрезка. Пусть даны отрезки [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)

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

Ссылки

Предикат "левый поворот"

Погрешность предиката "левый поворот"