Задача о принадлежности точки многоугольнику: различия между версиями

[отпатрулированная версия]

Содержимое удалено Содержимое добавлено

Линейный

Текущая версия от 04:42, 1 января 2023

В вычислительной геометрии известна задача об определении принадлежности точки многоугольнику. На плоскости даны многоугольник и точка. Требуется решить вопрос о принадлежности точки многоугольнику.

Многоугольник может быть как выпуклым, так и невыпуклым. Обычно предполагается, что многоугольник простой, то есть без самопересечений; но задачу рассматривают и для не-простых многоугольников. В последнем случае разные способы определения принадлежности точки многоугольнику могут привести к разным результатам. Различают алгоритмы без предварительной обработки; и алгоритмы с предварительной обработкой, в ходе которой создаются некоторые структуры данных, позволяющие в дальнейшем быстрее отвечать на множество запросов о принадлежности разных точек одному и тому же многоугольнику.

Метод трассировки луча

Учёт числа пересечений

Один из стандартных методов определения принадлежности точки произвольному простому многоугольнику заключается в следующем. Выпустим луч из данной точки в произвольном направлении (например в положительном направлении горизонтальной оси), и посчитаем сколько раз луч пересекает рёбра многоугольника. Для этого достаточно пройтись в цикле по рёбрам многоугольника и определить, пересекает ли луч каждое ребро. Если число пересечений нечётно, то объявляется, что точка лежит внутри многоугольника, если чётно — то снаружи. Это основано на том простом наблюдении, что при движении по лучу с каждым пересечением границы точка попеременно оказывается то внутри, то снаружи многоугольника. Алгоритм известен под такими названиями, как crossing number (count) algorithm или even-odd rule.

В алгоритме возникает затруднение в вырожденном случае, когда луч пересекает вершину многоугольника. Один из приёмов для его преодоления заключается в том, чтобы считать, что такие вершины многоугольника лежат на бесконечно малую величину выше (или ниже) прямой луча, и стало быть пересечения на самом деле и нет.^[1] Таким образом, пересечение луча с ребром засчитывается, если один из концов ребра лежит строго ниже луча, а другой конец — выше или лежит на луче.

Алгоритм работает за время O(N) для N-угольника.

Учёт числа оборотов

Рассмотрим число оборотов, которое делает ориентированная граница многоугольника вокруг данной точки P. В алгебраической топологии это число называется индексом точки относительно кривой.^[2] Оно может быть вычислено следующим образом. Как и раньше, выпустим луч из P в произвольном направлении и рассмотрим рёбра, которые он пересекает. Каждому пересечению присвоим число +1 или -1, в зависимости от того, как ребро пересекает луч — по часовой (слева направо) или против часовой стрелки (справа налево). Эти два случая можно различить по знаку скалярного произведения между направляющим вектором ребра и нормалью к направляющему вектору луча.^[3] Сумма полученных величин и есть индекс точки относительно кривой. Сумма будет положительной или отрицательной, в зависимости от ориентации границы. Если она не равна нулю, то будем считать, что точка лежит внутри многоугольника, иначе — снаружи.

Такой алгоритм известен под названием nonzero winding rule.^[3]

Для простых многоугольников этот метод работает так же, как и метод, основанный на подсчёте числа пересечений. Разница между ними проявляется при рассмотрении многоугольников с самопересекающейся границей.

Метод суммирования углов

Можно определить, что точка P находится внутри многоугольника с вершинами V₀, V₁, ..., V_n = V₀, вычислив сумму:

\sum _{i=1}^{n}\phi _{i},

где $\phi _{i}$ — угол (в радианах и со знаком) между лучами PV_{i − 1} и PV_i, то есть:

\phi _{i}=\arccos \left({\frac {PV_{i-1}\cdot PV_{i}}{|PV_{i-1}|\cdot |PV_{i}|}}\right)\operatorname {sign} \left(\det {\begin{pmatrix}PV_{i-1}\\PV_{i}\end{pmatrix}}\right).

Можно доказать, что эта сумма есть не что иное, как winding number точки P относительно границы многоугольника, с точностью до константного множителя $2\pi$ . Поэтому можно считать, что точка лежит снаружи многоугольника, если сумма равна нулю (или достаточно близка к нему, если используется приближённая арифметика). Однако данный метод весьма непрактичен, так как требует вычисления дорогостоящих операций для каждого ребра (обратных тригонометрических функций, квадратных корней), и был даже назван «худшим в мире алгоритмом» для данной задачи^[1].

К. Вейлером был предложен практичный вариант этого метода, избегающий дорогостоящих операций и приближенных вычислений.^[4] Было показано, что сумму углов можно вычислить, используя лишь операцию классификации точки многоугольника по квадрантам относительно точки P. Алгоритм Вейлера и некоторые улучшения к нему описываются в^[5].

Алгоритмы c предобработкой

Выпуклые и звёздные многоугольники

Принадлежность точки выпуклому или звёздному N-угольнику может быть определена при помощи двоичного поиска за время O(log N), при затрате O(N) памяти и O(N) времени на предварительную обработку.^[6]

Произвольный многоугольник

Задачу о принадлежности точки произвольному простому многоугольнику можно рассматривать как частный случай задачи о локализации точки^[англ.] в планарном подразбиении. Для N-угольника эта задача может быть решена за время O(log² N) с использованием O(N) памяти и O(N log N) времени на предобработку.^[7]

Примечания

↑ ¹ ² Eric Haines. Point in Polygon Strategies Архивная копия от 25 сентября 2011 на Wayback Machine
↑ Может переводиться на русский язык как «индекс кривой относительно точки», «число кручения», «число намоток», «винтовое число» и тому подобное.
↑ ¹ ² Foley J. D., et al. Computer Graphics: Principles and Practice. Addison-Wesley. 1990. P. 965.
↑ K. Weiler. An incremental angle point in polygon test, in: P. Heckbert (Ed.), Graphic Gems IV, Academic Press, Boston, MA, 1994, pp. 16—23.
↑ Hormann K., Agathos A. The point in polygon problem for arbitrary polygons (англ.) // Comput. Geom. Theory Appl.. — 2001. — Vol. 20. — P. 131—144. Архивировано 29 декабря 2012 года.
↑ Препарата, Шеймос. Стр. 60-61.
↑ Препарата, Шеймос. Стр. 74. Теорема 2.6.

Литература

Препарата Ф., Шеймос М. Раздел 2.2: Задачи локализации точек. // Вычислительная геометрия: введение. — Москва: Мир, 1989.

Ссылки

Имеется викиучебник по теме «Задача о принадлежности точки многоугольнику»

[haines-1] ¹ ² Eric Haines. Point in Polygon Strategies Архивная копия от 25 сентября 2011 на Wayback Machine

[2] Может переводиться на русский язык как «индекс кривой относительно точки», «число кручения», «число намоток», «винтовое число» и тому подобное.

[foley-3] ¹ ² Foley J. D., et al. Computer Graphics: Principles and Practice. Addison-Wesley. 1990. P. 965.

[4] K. Weiler. An incremental angle point in polygon test, in: P. Heckbert (Ed.), Graphic Gems IV, Academic Press, Boston, MA, 1994, pp. 16—23.

[5] Hormann K., Agathos A. The point in polygon problem for arbitrary polygons (англ.) // Comput. Geom. Theory Appl.. — 2001. — Vol. 20. — P. 131—144. Архивировано 29 декабря 2012 года.

[6] Препарата, Шеймос. Стр. 60-61.

[7] Препарата, Шеймос. Стр. 74. Теорема 2.6.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

@@ Строка 1: / Строка 1: @@
 В вычислительной геометрии известна '''задача об определении принадлежности точки многоугольнику'''. На плоскости даны [[многоугольник]] и [[Точка (геометрия)|точка]]. Требуется решить вопрос о принадлежности точки многоугольнику.
-Многоугольник может быть как [[выпуклый многоугольник|выпуклым]], так и невыпуклым. Обычно предполагается, что многоугольник простой, т.е. без самопересечений, но задачу рассматривают и для не-простых многоугольников. В последнем случае разные способы определения принадлежности точки многоугольнику могут привести к разным результатам.  Различают алгоритмы без предварительной обработки и алгоритмы с предварительной обработкой, в ходе которой создаются некоторые структуры данных, позволяющие в дальнейшем быстрее отвечать на множество запросов о принадлежности точек одному и тому же многоугольнику.
+Многоугольник может быть как [[выпуклый многоугольник|выпуклым]], так и невыпуклым. Обычно предполагается, что многоугольник простой, то есть без самопересечений; но задачу рассматривают и для не-простых многоугольников. В последнем случае разные способы определения принадлежности точки многоугольнику могут привести к разным результатам.  Различают алгоритмы без предварительной обработки; и алгоритмы с предварительной обработкой, в ходе которой создаются некоторые структуры данных, позволяющие в дальнейшем быстрее отвечать на множество запросов о принадлежности разных точек одному и тому же многоугольнику.
 == Метод трассировки луча ==
@@ Строка 9: / Строка 9: @@
 Один из стандартных методов определения принадлежности точки произвольному простому многоугольнику заключается в следующем. Выпустим луч из данной точки в произвольном направлении (например в положительном направлении горизонтальной оси), и посчитаем сколько раз луч пересекает рёбра многоугольника. Для этого достаточно пройтись в цикле по рёбрам многоугольника и определить, пересекает ли луч каждое ребро. Если число пересечений нечётно, то объявляется, что точка лежит внутри многоугольника, если чётно — то снаружи. Это основано на том простом наблюдении, что при движении по лучу с каждым пересечением границы точка попеременно оказывается то внутри, то снаружи многоугольника. Алгоритм известен под такими названиями, как {{lang-en2|crossing number (count) algorithm}} или {{lang-en2|even-odd rule}}.
-В алгоритме возникает затруднение в вырожденном случае, когда луч пересекает вершину многоугольника. Один из приёмов для его преодоления заключается в том, чтобы считать, что такие вершины многоугольника лежат на бесконечно малую величину выше (или ниже) прямой луча, и стало быть пересечения на самом деле и нет.<ref name="haines">Eric Haines. [http://erich.realtimerendering.com/ptinpoly/ Point in Polygon Strategies]</ref> Таким образом, пересечение луча с ребром засчитывается, если один из концов ребра лежит строго ниже луча, а другой конец — выше или лежит на луче.
+В алгоритме возникает затруднение в вырожденном случае, когда луч пересекает вершину многоугольника. Один из приёмов для его преодоления заключается в том, чтобы считать, что такие вершины многоугольника лежат на бесконечно малую величину выше (или ниже) прямой луча, и стало быть пересечения на самом деле и нет.<ref name="haines">Eric Haines. [http://erich.realtimerendering.com/ptinpoly/ Point in Polygon Strategies] {{Wayback|url=http://erich.realtimerendering.com/ptinpoly/ |date=20110925001920 }}</ref> Таким образом, пересечение луча с ребром засчитывается, если один из концов ребра лежит строго ниже луча, а другой конец — выше или лежит на луче.
 Алгоритм работает за время O(''N'') для ''N''-угольника.
@@ Строка 15: / Строка 15: @@
 === Учёт числа оборотов ===
 [[Image:Winding Number 2.svg|right|thumb|150px|Кривая делает два оборота вокруг данной точки.]]
-Рассмотрим число оборотов, которое делает ориентированная граница многоугольника вокруг данной точки ''P''. В алгебраической топологии это число называется [[Порядок точки относительно кривой|индексом точки относительно кривой]].<ref>Может переводиться на русский язык как «индекс кривой относительно точки», «число кручения», «число намоток», «винтовое число» и т.п.</ref> Оно может быть вычислено следующим образом. Как и раньше, выпустим луч из ''P'' в произвольном направлении и рассмотрим рёбра, которые он пересекает. Каждому пересечению присвоим число +1 или -1, в зависимости от того, как ребро пересекает луч — по часовой (слева направо) или против часовой стрелки (справа налево). Эти два случая можно различить по знаку скалярного произведения между направляющим вектором ребра и нормалью к направляющему вектору луча.<ref name="foley">Foley J. D., et al. Computer Graphics: Principles and Practice. Addison-Wesley. 1990. P. 965.</ref> Сумма полученных величин и есть [[Порядок точки относительно кривой|индекс точки относительно кривой]]. Сумма будет положительной или отрицательной, в зависимости от ориентации границы. Если она не равна нулю, то будем считать, что точка лежит внутри многоугольника, иначе — снаружи.
+Рассмотрим число оборотов, которое делает ориентированная граница многоугольника вокруг данной точки ''P''. В алгебраической топологии это число называется [[Порядок точки относительно кривой|индексом точки относительно кривой]].<ref>Может переводиться на русский язык как «индекс кривой относительно точки», «число кручения», «число намоток», «винтовое число» и тому подобное.</ref> Оно может быть вычислено следующим образом. Как и раньше, выпустим луч из ''P'' в произвольном направлении и рассмотрим рёбра, которые он пересекает. Каждому пересечению присвоим число +1 или -1, в зависимости от того, как ребро пересекает луч — по часовой (слева направо) или против часовой стрелки (справа налево). Эти два случая можно различить по знаку скалярного произведения между направляющим вектором ребра и нормалью к направляющему вектору луча.<ref name="foley">Foley J. D., et al. Computer Graphics: Principles and Practice. Addison-Wesley. 1990. P. 965.</ref> Сумма полученных величин и есть [[Порядок точки относительно кривой|индекс точки относительно кривой]]. Сумма будет положительной или отрицательной, в зависимости от ориентации границы. Если она не равна нулю, то будем считать, что точка лежит внутри многоугольника, иначе — снаружи.
 Такой алгоритм известен под названием {{lang-en2|nonzero winding rule}}.<ref name="foley" />
@@ Строка 22: / Строка 22: @@
 == Метод суммирования углов ==
-Можно определить, что точка ''P'' находится внутри многоугольника c вершинами ''V''<sub>0</sub>, ''V''<sub>1</sub>, ..., ''V''<sub>''n''</sub> = ''V''<sub>0</sub>, вычислив сумму:
+Можно определить, что точка {{math|''P''}} находится внутри многоугольника с вершинами {{math|''V''<sub>0</sub>, ''V''<sub>1</sub>, ..., ''V''<sub>''n''</sub> {{=}} ''V''<sub>0</sub>}}, вычислив сумму:
-: <math>\sum_{i=1}^n \phi_i</math>,
+: <math>\sum_{i=1}^n \phi_i,</math>
-где <math>\phi_i</math> — угол (в радианах и со знаком) между лучами ''PV''<sub>''i'' - 1</sub> и ''PV''<sub>''i''</sub>, т.е.:
+где <math>\phi_i</math> — угол (в радианах и со знаком) между лучами {{math|''PV''<sub>''i'' − 1</sub>}} и {{math|''PV''<sub>''i''</sub>}}, то есть:
-: <math>\phi_i = \arccos\left(\frac{PV_{i-1} \cdot PV_i}{|PV_{i-1}| \cdot |PV_i|}\right) sign\left( det \begin{pmatrix} PV_{i-1} \\ PV_{i}\end{pmatrix}\right).</math>
+: <math>\phi_i = \arccos\left(\frac{PV_{i-1} \cdot PV_i}{|PV_{i-1}| \cdot |PV_i|}\right) \operatorname{sign}\left( \det \begin{pmatrix} PV_{i-1} \\ PV_{i}\end{pmatrix}\right).</math>
-Можно доказать, что эта сумма есть не что иное, как {{lang-en2|winding number}} точки ''P'' относительно границы многоугольника, с точностью до константного множителя <math>2 \pi</math>. Поэтому можно считать, что точка лежит снаружи многоугольника, если сумма равна нулю (или достаточно близка к нему, если используется приближённая арифметика). Однако данный метод весьма непрактичен, так как требует вычисления дорогостоящих операций для каждого ребра (обратных тригонометрических функций, квадратных корней), и был даже назван «худшим в мире алгоритмом» для данной задачи.<ref name="haines" />
+Можно доказать, что эта сумма есть не что иное, как {{lang-en2|winding number}} точки {{math|''P''}} относительно границы многоугольника, с точностью до константного множителя <math>2 \pi</math>. Поэтому можно считать, что точка лежит снаружи многоугольника, если сумма равна нулю (или достаточно близка к нему, если используется приближённая арифметика). Однако данный метод весьма непрактичен, так как требует вычисления дорогостоящих операций для каждого ребра (обратных тригонометрических функций, квадратных корней), и был даже назван «худшим в мире алгоритмом» для данной задачи<ref name="haines" />.
-К. Вейлером был предложен практичный вариант этого метода, избегающий дорогостоящих операций и приближенных вычислений.<ref>K. Weiler. An incremental angle point in polygon test, in: P. Heckbert (Ed.), Graphic Gems IV, Academic Press, Boston, MA, 1994, pp. 16–23.</ref> Было показано, что сумму углов можно вычислить, используя лишь операцию классификации точки многоугольника по квадрантам относительно точки ''P''. Алгоритм Вейлера и некоторые улучшения к нему описываются в <ref>Kai Hormann and Alexander Agathos. [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.88.5498&rep=rep1&type=pdf The point in polygon problem for arbitrary polygons]. Comput. Geom. Theory Appl. 20 (2001), 131-144.</ref>.
+К. Вейлером был предложен практичный вариант этого метода, избегающий дорогостоящих операций и приближенных вычислений.<ref>K. Weiler. An incremental angle point in polygon test, in: P. Heckbert (Ed.), Graphic Gems IV, Academic Press, Boston, MA, 1994, pp. 16—23.</ref> Было показано, что сумму углов можно вычислить, используя лишь операцию классификации точки многоугольника по квадрантам относительно точки {{math|''P''}}. Алгоритм Вейлера и некоторые улучшения к нему описываются в<ref>{{статья|автор=Hormann K., Agathos A.|заглавие=The point in polygon problem for arbitrary polygons|издание=Comput. Geom. Theory Appl.|год=2001|том=20|выпуск=|страницы=131—144|ссылка=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.88.5498&rep=rep1&type=pdf|doi=|arxiv=|язык=en|archivedate=2012-12-29|archiveurl=https://web.archive.org/web/20121229054203/http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.88.5498&rep=rep1&type=pdf}}</ref>.
 == Алгоритмы c предобработкой ==
@@ Строка 36: / Строка 36: @@
 === Произвольный многоугольник ===
-Задачу о принадлежности точки произвольному простому многоугольнику можно рассматривать как частный случай задачи о [[:en:Point location|локализации точки]] в планарном подразбиении. Для ''N''-угольника эта задача может быть решена за время O(log<sup>2</sup> ''N'') с использованием O(''N'') памяти и O(''N'' log ''N'') времени на предобработку.<ref>Препарата, Шеймос. Стр. 74. Теорема 2.6.</ref>
+Задачу о принадлежности точки произвольному простому многоугольнику можно рассматривать как частный случай {{iw|Локализация точки|задачи о локализации точки|en|Point location}} в планарном подразбиении. Для ''N''-угольника эта задача может быть решена за время O(log<sup>2</sup> ''N'') с использованием O(''N'') памяти и O(''N'' log ''N'') времени на предобработку.<ref>Препарата, Шеймос. Стр. 74. Теорема 2.6.</ref>
 == Примечания ==
@@ Строка 57: / Строка 57: @@
 * [http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm Dan Sunday. Fast Winding Number Inclusion of a Point in a Polygon]
 * [http://www.visibone.com/inpoly/ Bob Stein. A Point about Polygons]
-* [http://ips.ifmo.ru/courses/course1/chZ/index.html Российская Интернет-школа информатики и программирования. Учебные курсы. Введение в алгоритмику. Вычислительная геометрия]
+* [https://web.archive.org/web/20070810174907/http://ips.ifmo.ru/courses/course1/chZ/index.html Российская Интернет-школа информатики и программирования. Учебные курсы. Введение в алгоритмику. Вычислительная геометрия]
 * [http://pasc.al.ru/www/exampl35.htm Альтернативный метод проверки принадлежности точки многоугольнику - метод трассировки луча]
+{{Многоугольники}}
 [[Категория:Геометрические алгоритмы]]
 [[Категория:Многоугольники]]

Задача о принадлежности точки многоугольнику: различия между версиями

Текущая версия от 04:42, 1 января 2023

Содержание

Метод трассировки луча

Учёт числа пересечений

Учёт числа оборотов

Метод суммирования углов

Алгоритмы c предобработкой

Выпуклые и звёздные многоугольники

Произвольный многоугольник

Примечания

Литература

Ссылки

Навигация

Задача о принадлежности точки многоугольнику: различия между версиями

Текущая версия от 04:42, 1 января 2023

Метод трассировки луча

Учёт числа пересечений

Учёт числа оборотов

Метод суммирования углов

Алгоритмы c предобработкой

Выпуклые и звёздные многоугольники

Произвольный многоугольник

Примечания

Литература

Ссылки

Навигация

Поиск