Пересечение отрезков и поворот: определение, свойства, вычисление — различия между версиями
Melnik (обсуждение | вклад) (Новая страница: «== Ссылки == Предикат "левый поворот" [[Представление_чисел_...») |
м (rollbackEdits.php mass rollback) |
||
(не показано 6 промежуточных версий 4 участников) | |||
Строка 1: | Строка 1: | ||
+ | == Аффинное пространство == | ||
+ | |||
+ | Формальное определение есть, например, [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) | ||
+ | |||
+ | Если предикат вычисления ориентации был абсолютно точным, то таким же будет описанный алгоритм. | ||
+ | |||
== Ссылки == | == Ссылки == | ||
Текущая версия на 19:31, 4 сентября 2022
Содержание
Аффинное пространство
Формальное определение есть, например, на википедии. Неформально: аффинное пространство - удобная геометрическая абстракция, рассматривающая точки (в отличие от векторов линейного пространства). Точки нельзя складывать между собой или умножать на число; к точке можно прибавить вектор, получив другую точку; можно получить вектор разности двух точек. Все приведенные операции обладают геометрически интуитивными и ожидаемыми свойствами.
Наряду с линейными комбинациями векторов рассматривают аффинные комбинации точек аффинного пространства
: , где . По определению считаютЛемма: |
В случае равенства единице суммы коэффициентов результат не зависит от выбора точки . |
Доказательство: |
Рассмотрим точку | , тогда
Также рассматривают понятие аффинной независимости точек (например, три точки на одной прямой аффинно зависимы). Набор
точек называется аффинно (не-)зависимым, если линейно (не-)зависим набор векторов .Ориентация
Ориентация векторов
Рассмотрим кососимметричную линейную форму от N N-мерных векторов, т.е. функцию
, обладающую свойством .Из курса линейной алгебры известно, что любые две такие формы отличаются друг от друга только на некоторый множитель. Зафиксируем одну из таких форм (например, считая, что форма равна 1 на наборе из векторов выделенного базиса). Назовем ориентацией набора из N N-мерных векторов знак значения этой формы на этом наборе векторов.
Отметим свойства ориентации:
- Ориентация линейно зависимого набора векторов равна нулю
- Ориентация меняет знак при перестановке двух векторов в наборе
Неформальное объяснение второго свойства: рассмотрим тройку векторов, таких, что если смотреть из конца первого вектора на второй, то он будет левее, чем третий. Перестановка второго и третьего векторов будет означать, что второй вектор будет виден правее третьего, что означает смену ориентации.
Заметим, что определитель является в точности кососимметричной линейной формой от N N-мерных векторов, а значит, подходит для вычисления ориентации набора векторов.
Ориентация точек
Аналогичным образом можно определить ориентацию набора из N+1 N-мерных точек. Ориентацией точек
назовем ориентацию набора векторовНетрудно заметить, что ориентация набора точек обладает свойствами, похожими на ориентацию векторов:
- Ориентация набора аффинно-зависимых точек равна нулю
- Ориентация меняет знак при перестановке двух точек в наборе
Предикат левый поворот
Назовем положительную ориентацию левой, а отрицательную - правой (только соглашение; левая ориентация может не совпадать с интуитивным представлением при выборе кососимметричной формы с другим знаком).
Предикат "левый поворот" по набору точек определяет, верно ли, что их ориентация - левая. Используется в большинстве алгоритмов вычислительной геометрии.
Вычислить ориентацию точек
(и, следовательно, предикат) можно через определитель набора векторов .О точном вычислении ориентации см. раздел Ссылки.
Пересечение отрезков
Определить, пересекаются ли два отрезка, можно с помощью предиката поворота. Ясно, что отрезки пересекаются тогда и только тогда, когда для каждого из отрезков его точки не лежат с одной стороны от второго отрезка. Пусть даны отрезки
и . Отрезки пересекаются, если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)
Если предикат вычисления ориентации был абсолютно точным, то таким же будет описанный алгоритм.