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

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

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

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

Линейный

Текущая версия от 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]

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

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

Содержание

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

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

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

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

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

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

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

Примечания

Литература

Ссылки

Навигация

@@ Строка 1: / Строка 1: @@
+В вычислительной геометрии известна '''задача об определении принадлежности точки многоугольнику'''. На плоскости даны [[многоугольник]] и [[Точка (геометрия)|точка]]. Требуется решить вопрос о принадлежности точки многоугольнику.
-{{стиль}}
-'''Проверка принадлежности данной точки данному многоугольнику'''
+Многоугольник может быть как [[выпуклый многоугольник|выпуклым]], так и невыпуклым. Обычно предполагается, что многоугольник простой, то есть без самопересечений; но задачу рассматривают и для не-простых многоугольников. В последнем случае разные способы определения принадлежности точки многоугольнику могут привести к разным результатам.  Различают алгоритмы без предварительной обработки; и алгоритмы с предварительной обработкой, в ходе которой создаются некоторые структуры данных, позволяющие в дальнейшем быстрее отвечать на множество запросов о принадлежности разных точек одному и тому же многоугольнику.
-На плоскости даны [[многоугольник]] и [[Точка (геометрия)|точка]]. Многоугольник может быть как выпуклым, так и невыпуклым. Требуется решить вопрос о принадлежности точки многоугольнику.
+== Метод трассировки луча ==
-Благодаря тому, что многоугольник является частным случаем замкнутой односвязной области, алгоритм решения задачи может быть следующим. Вершины многоугольника последовательно нумеруются от 1 до n. Из заданной точки проводятся лучи, проходящие через вершины 2 и 1. Определяется разность направлений этих лучей. Процесс повторяется для пары вершин 3 и 2 и т. д. до пары вершин n и (n-1) и, наконец, 1 и n. Указанные разности суммируются. Если сумма равна нулю, то делается вывод о том, что заданная точка лежит вне заданного многоугольника.
+=== Учёт числа пересечений ===
+[[Image:Even-odd and non-zero winding fill rules.svg|right|thumb|300px|
+Методы работают по-разному для многоугольников с самопересекающейся границей. Слева: even-odd rule. Справа: nonzero winding rule.]]
+Один из стандартных методов определения принадлежности точки произвольному простому многоугольнику заключается в следующем. Выпустим луч из данной точки в произвольном направлении (например в положительном направлении горизонтальной оси), и посчитаем сколько раз луч пересекает рёбра многоугольника. Для этого достаточно пройтись в цикле по рёбрам многоугольника и определить, пересекает ли луч каждое ребро. Если число пересечений нечётно, то объявляется, что точка лежит внутри многоугольника, если чётно — то снаружи. Это основано на том простом наблюдении, что при движении по лучу с каждым пересечением границы точка попеременно оказывается то внутри, то снаружи многоугольника. Алгоритм известен под такими названиями, как {{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] {{Wayback|url=http://erich.realtimerendering.com/ptinpoly/ |date=20110925001920 }}</ref> Таким образом, пересечение луча с ребром засчитывается, если один из концов ребра лежит строго ниже луча, а другой конец — выше или лежит на луче.
-Реализация описанного алгоритма определения принадлежности точки многоугольнику требует большого объёма вычислений с использованием обратных [[Тригонометрические функции|тригонометрических функций]]. Он практически непригоден для компьютерных интерактивных графических приложений, в которых многоугольник аппроксимирует, к примеру, область на географической карте и имеет большое число вершин.
+Алгоритм работает за время O(''N'') для ''N''-угольника.
-Если перейти к [[Октант (значения)|октанным координатам]], этот очевидный алгоритм лишается своего единственного недостатка и требует только простых арифметических операций
-* [http://code.google.com/p/polypuch/source/browse/trunk/src/libs/Polygon/General/general_have.cpp Реализация на c++]
+=== Учёт числа оборотов ===
-Все алгоритмы в данной статье имеют '''сложность O(n)'''.
+[[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> Сумма полученных величин и есть [[Порядок точки относительно кривой|индекс точки относительно кривой]]. Сумма будет положительной или отрицательной, в зависимости от ориентации границы. Если она не равна нулю, то будем считать, что точка лежит внутри многоугольника, иначе — снаружи.
+Такой алгоритм известен под названием {{lang-en2|nonzero winding rule}}.<ref name="foley" />
-Для выпуклого полигона существует [[Алгоритм точки в выпуклом многоугольнике|алгоритм работающий за O(logn)]].
+Для простых многоугольников этот метод работает так же, как и метод, основанный на подсчёте числа пересечений. Разница между ними проявляется при рассмотрении многоугольников с самопересекающейся границей.
-== Алгоритм, требующий простых арифметических операций ==
+== Метод суммирования углов ==
+Можно определить, что точка {{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>\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) \operatorname{sign}\left( \det \begin{pmatrix} PV_{i-1} \\ PV_{i}\end{pmatrix}\right).</math>
+Можно доказать, что эта сумма есть не что иное, как {{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> Было показано, что сумму углов можно вычислить, используя лишь операцию классификации точки многоугольника по квадрантам относительно точки {{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>.
-Для принадлежности точки ''выпуклому'' многоугольнику вершины последовательно нумеруются от 1 до n. Вершина с условным номером 1 соединяется отрезками со всеми другими вершинами. Образуются (n-2) [[Треугольник|треугольника]] с вершинами {1, (i-1), i}, где 3 ≤ i ≤ n. Осуществляется проверка принадлежности заданной точки хотя бы одному из этих треугольников.
+== Алгоритмы c предобработкой ==
-Если точка не принадлежит ни одному треугольнику, значит, она не принадлежит и многоугольнику.
+=== Выпуклые и звёздные многоугольники ===
-Иначе подобное разбиение многоугольника на треугольники и проверка принадлежности заданной точки треугольникам выполняется для вершин с последующими номерами — до выполнения одного из условий:
+Принадлежность точки [[Выпуклый многоугольник|выпуклому]] или [[Звёздная область|звёздному]] ''N''-угольнику может быть определена при помощи [[двоичный поиск|двоичного поиска]] за время O(log ''N''), при затрате O(''N'') памяти и O(''N'') времени на предварительную обработку.<ref>Препарата, Шеймос. Стр. 60-61.</ref>
-* нашлось разбиение, в котором точка не принадлежит ни одному из треугольников, и тогда делается вывод, что точка не принадлежит многоугольнику;
-* перебраны все вершины, и тогда делается вывод, что точка принадлежит многоугольнику.
+=== Произвольный многоугольник ===
-Что касается проверки принадлежности точки треугольнику, то, благодаря тому, что треугольник является ''выпуклым'' многоугольником, соответственно, может использоваться следующий алгоритм проверки принадлежности точки выпуклому многоугольнику. Если при последовательном обходе вершин в одном направлении выясняется, что заданная точка и вершина n + 2 лежат по разные стóроны от стороны, соединяющей текущую вершину n и вершину n + 1, то делается вывод, что точка не принадлежит многоугольнику, и процесс прерывается. Если обход вершин не был прерван, то делается вывод, что точка принадлежит многоугольнику.
+Задачу о принадлежности точки произвольному простому многоугольнику можно рассматривать как частный случай {{iw|Локализация точки|задачи о локализации точки|en|Point location}} в планарном подразбиении. Для ''N''-угольника эта задача может быть решена за время O(log<sup>2</sup> ''N'') с использованием O(''N'') памяти и O(''N'' log ''N'') времени на предобработку.<ref>Препарата, Шеймос. Стр. 74. Теорема 2.6.</ref>
+== Примечания ==
-Для проверки принадлежности точки треугольнику (а также ''выпуклому'' многоугольнику с любым числом вершин) можно применить и другой алгоритм. Заданная точка соединяется отрезками с вершинами треугольника. Если площадь исходного треугольника равна сумме площадей образовавшихся трёх треугольников, то считается, что точка принадлежит треугольнику.
+{{примечания}}
-В приведённом ниже коде алгоритма проверки принадлежности заданной точки заданному многоугольнику используется второй из описанных алгоритмов проверки принадлежности точки треугольнику.
-Алгоритм определяет точки границ многоугольника как точки, ему принадлежащие.
-Для того чтобы все результаты вычислений в программе могли быть представлены целочисленными переменными (манипулирование данными целого типа повышает быстродействие программы и является естественным для приложений компьютерной графики), вычисления и сравнения площадей треугольников заменяются вычислениями и сравнениями их удвоенных площадей. Тем самым исключается погрешность округления при программной реализации всего алгоритма, в целом.
-Аргументами функции, реализующей проверку принадлежности данной точки данному многоугольнику произвольного вида, являются
-* указатель на массив пар целочисленных координат вершин многоугольника, а именно, на массив структур вида
-<code>
-    struct Point {
-                     int x;
-                     int y;
-                 };</code>
-* число вершин многоугольника;
-* целочисленное значение координаты X заданной точки;
-* целочисленное значение координаты Y заданной точки.
-Функция возвращает 1, если точка принадлежит многоугольнику, иначе — 0.
-Функция имеет следующий вид.
-<code>
- int IsPointInsidePolygon (Point *p, int Number, int x, int y)
- {
-  int i1, i2, n, N, S, S1, S2, S3, flag;
-  N = Number;
-  for (n=0; n<N; n++)
-  {
-   flag = 0;
-   i1 = n < N-1 ? n + 1 : 0;
-   while (flag == 0)
-   {
-    i2 = i1 + 1;
-    if (i2 >= N)
-      i2 = 0;
-    if (i2 == (n < N-1 ? n + 1 : 0))
-      break;
-    S = abs (p[i1].x * (p[i2].y - p[n ].y) +
-             p[i2].x * (p[n ].y - p[i1].y) +
-             p[n].x  * (p[i1].y - p[i2].y));
-    S1 = abs (p[i1].x * (p[i2].y - y) +
-              p[i2].x * (y       - p[i1].y) +
-              x       * (p[i1].y - p[i2].y));
-    S2 = abs (p[n ].x * (p[i2].y - y) +
-              p[i2].x * (y       - p[n ].y) +
-              x       * (p[n ].y - p[i2].y));
-    S3 = abs (p[i1].x * (p[n ].y - y) +
-              p[n ].x * (y       - p[i1].y) +
-              x       * (p[i1].y - p[n ].y));
-    if (S == S1 + S2 + S3)
-    {
-     flag = 1;
-     break;
-    }
-    i1 = i1 + 1;
-    if (i1 >= N)
-      i1 = 0;
-   }
-   if (flag == 0)
-     break;
-  }
-  return flag;
- }</code>
-== Очень быстрый алгоритм ==
-В основе алгоритма лежит идея подсчёта количества пересечений луча, исходящего из данной точки в направлении горизонтальной оси, со сторонами многоугольника. Если оно чётное, точка не принадлежит многоугольнику.
-В данном алгоритме луч направлен влево.
-<code>
-  int pnpoly(int npol, float * xp, float * yp, float x, float y)
-  {
-    int c = 0;
-    for (int i = 0, j = npol - 1; i < npol; j = i++)
-    {
-      if ((((yp[i]<=y) && (y<yp[j])) || ((yp[j]<=y) && (y<yp[i]))) &&
-        (x > (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i]))
-          c = !c;
-    }
-    return c;
-  }</code>
-'''Замечание:'''
-Так как умножение быстрее деления, условие можно записать так:
-<code>
-  int pnpoly(int npol, float * xp, float * yp, float x, float y)
-  {
-    int c = 0;
-    for (int i = 0, j = npol - 1; i < npol; j = i++)
-    {
-      if ((
-        (yp[i]<yp[j]) && (yp[i]<=y) && (y<=yp[j]) &&
-        ((yp[j] - yp[i]) * (x - xp[i]) > (xp[j] - xp[i]) * (y - yp[i]))
-      ) || (
-        (yp[i]>yp[j]) && (yp[j]<=y) && (y<=yp[i]) &&
-        ((yp[j] - yp[i]) * (x - xp[i]) < (xp[j] - xp[i]) * (y - yp[i]))
-      ))
-        c = !c;
-    }
-    return c;
-  }</code>
-Однако, стоит заметить, что данный алгоритм не эквивалентен предыдущему, по-этому его использование может привести к неправильным результатам.
-'''Perl:'''
-<code>
- my $x = -40; my $y = -60; # Проверяемая точка
- my @xp = (-73,-33,7,-33); # Массив X-координат полигона
- my @yp = (-85,-126,-85,-45); # Массив Y-координат полигона
- &InPoly(\@xp,\@yp,$x,$y);
-  sub InPoly()
-  {
- 	 my($xp, $yp, $x, $y) = @_;
- 	 my $npol = @{$xp};
-   	 my $j = $npol - 1;
- 	 my $c = 0;
- 	 for(my $i = 0; $i < $npol;$i++) {
-            if ((((@{$yp}[$i]<=$y) && ($y<@{$yp}[$j])) || ((@{$yp}[$j]<=$y) && ($y<@{$yp}[$i]))) &&
-               ($x > (@{$xp}[$j] - @{$xp}[$i]) * ($y - @{$yp}[$i]) / (@{$yp}[$j] - @{$yp}[$i]) + @{$xp}[$i]))
-                {
-                  $c = !$c
-                }
-                 $j = $i;
-         }
-  return $c;
-  }
-</code>
-'''JavaScript:'''
-<code>
- var x = -40;
- var y = -60;
- var xp = new Array(-73,-33,7,-33); // Массив X-координат полигона
- var yp = new Array(-85,-126,-85,-45); // Массив Y-координат полигона
- function inPoly(x,y){
-   npol = xp.length;
-   j = npol - 1;
-   var c = 0;
-   for (i = 0; i < npol;i++){
-       if ((((yp[i]<=y) && (y<yp[j])) || ((yp[j]<=y) && (y<yp[i]))) &&
-       (x > (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i])) {
-        c = !c
-        }
-        j = i;
-   }
- return c;
- }
- inPoly(x,y);</code>
-'''Python 3:'''
-На Python программа несколько отличается от других языков в сторону компактности из-за особенностей адресации элементов массива. Не нужны дополнительные переменные.
-<code>
- def inPolygon(x, y, xp, yp):
-    c=0
-    for i in range(len(xp)):
-        if (((yp[i]<=y and y<yp[i-1]) or (yp[i-1]<=y and y<yp[i])) and \
-            (x > (xp[i-1] - xp[i]) * (y - yp[i]) / (yp[i-1] - yp[i]) + xp[i])): c = 1 - c
-    return c
- print( inPolygon(100, 0, (-100, 100, 100, -100), (100, 100, -100, -100)))
-</code>
-== Быстрый алгоритм для случая, когда луч пересекает одну или несколько вершин ==
-Функция Cross определяет, пересекает ли луч j-ое ребро многоугольника:
-<code>
-  bool Cross(int j)
-  {
-    int first = j;
-    int second = j == n - 1 ? 0 : j + 1;
-    double y = (xh - points[first].x) * (points[second].y - points[first].y) / (points[second].x - points[first].x) + points[first].y;
-    double minimal = min(points[first].x, points[second].x);
-    double maximal = max(points[first].x, points[second].x);
-    return (points[first].x != points[second].x) && (yh >= y) && (xh > minimal) && (xh <= maximal);
-  }</code>
-Фрагмент основной программы:
-<code>
-  ...
-  int count = 0;
-  for (int i = 0; i < n; i++)
-  {
-    count += Cross(i);
-  }
-  ...</code>
-Если переменная count примет нечетное значение, то точка лежит внутри многоугольника. В противном случает точка лежит вне заданого многоугольника.
-'''Замечание:'''
-В данной реализации алгоритма луч направлен вниз.
 == Литература ==
+* {{книга
-* Джалиашвили З. О., Подольский А. А. Алгоритмы анализа ответов в тестовых заданиях с графическим интерфейсом. Информационный бюллетень ассоциации История и компьютер, N 1, 2005.
+ | автор         = Препарата Ф., Шеймос М.
-* Ласло М. Вычислительная геометрия и компьютерная графика на C++. М.: БИНОМ, 1997.
-* Препарата Ф., Шеймос М. Вычислительная геометрия: введение. М.: Мир, 1989.
+ | заглавие      = Вычислительная геометрия: введение
+ | часть         = Раздел 2.2: Задачи локализации точек.
+ | место         = Москва
+ | издательство  = Мир
+ | год           = 1989
+ | isbn          =
+ | ref           = Препарата, Шеймос
+}}
 == Ссылки ==
+{{wikibooks|Реализации алгоритмов/Задача о принадлежности точки многоугольнику|Задача о принадлежности точки многоугольнику}}
+* [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/inpoly.c.txt Исходный код на C]
 * [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 Альтернативный метод проверки принадлежности точки многоугольнику - метод трассировки луча]
+{{Многоугольники}}
-* [http://code.google.com/p/polypuch/ реализация на c++]
-{{rq|style|cleanup|img|topic=comp}}
 [[Категория:Геометрические алгоритмы]]
 [[Категория:Многоугольники]]
-[[en:Point in polygon]]
-[[sr:Припадност тачке многоуглу]]
-[[vi:Điểm trong đa giác]]

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

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

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

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

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

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

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

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

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

Примечания

Литература

Ссылки

Навигация

Поиск