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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Ориентация векторов)
(Аффинное пространство)
 
Строка 6: Строка 6:
 
Наряду с линейными комбинациями векторов рассматривают аффинные комбинации точек аффинного пространства <math>A</math>:
 
Наряду с линейными комбинациями векторов рассматривают аффинные комбинации точек аффинного пространства <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</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>\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>
 +
}}
  
 
Также рассматривают понятие аффинной независимости точек (например, три точки на одной прямой аффинно зависимы).
 
Также рассматривают понятие аффинной независимости точек (например, три точки на одной прямой аффинно зависимы).

Текущая версия на 12:40, 17 апреля 2015

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

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

Наряду с линейными комбинациями векторов рассматривают аффинные комбинации точек аффинного пространства [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]\triangleright[/math]
Рассмотрим точку [math]b + \overrightarrow{l}[/math], тогда [math]\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} = [/math][math] b +\sum \lambda_i \overrightarrow{(a_i - b)}+ \overrightarrow{l}(1 - \sum \lambda_i) = b +\sum \lambda_i \overrightarrow{(a_i - b)}[/math]
[math]\triangleleft[/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)

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

Ссылки[править]

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

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