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

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

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

Наряду с линейными комбинациями векторов рассматривают аффинные комбинации точек аффинного пространства [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(\hdots, x, \hdots, y, \hdots) = -f(\hdots, y, \hdots, x, \hdots)[/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].

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

Ссылки

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

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