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

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

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

Наряду с линейными комбинациями векторов рассматривают аффинные комбинации точек аффинного пространства <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> 
{{Лемма
|statement=
В случае равенства единице суммы коэффициентов результат не зависит от выбора точки <tex>b</tex>.
|proof=
Рассмотрим точку <tex>b + \overrightarrow{l}</tex>, тогда <tex>\sum \lambda_i a_i = b + \overrightarrow{l} +\sum \lambda_i \overrightarrow{(a_i - (b+l))} = b +\sum \lambda_i \overrightarrow{(a_i - b)} + \overrightarrow{l} - \sum \lambda_i \overrightarrow{l} = </tex><tex> b +\sum \lambda_i \overrightarrow{(a_i - b)}+ \overrightarrow{l}(1 - \sum \lambda_i) = b +\sum \lambda_i \overrightarrow{(a_i - b)}</tex> 
}}

Также рассматривают понятие аффинной независимости точек (например, три точки на одной прямой аффинно зависимы).
Набор <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)

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

== Ссылки ==

[[Предикат_%22левый_поворот%22 | Предикат "левый поворот"]]

[[Представление_чисел_с_плавающей_точкой#.D0.A0.D0.B0.D1.81.D1.87.D0.B5.D1.82 | Погрешность предиката "левый поворот"]]