Задача о принадлежности точки многоугольнику: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
X7q (обсуждение | вклад) мНет описания правки |
X7q (обсуждение | вклад) Нет описания правки |
||
| Строка 4: | Строка 4: | ||
== Метод трассировки луча == |
== Метод трассировки луча == |
||
=== Учёт числа пересечений === |
|||
| ⚫ | Один из стандартных методов определения принадлежности точки произвольному простому многоугольнику заключается в следующем. Выпустим луч из данной точки в произвольном направлении (например в положительном направлении горизонтальной оси), и посчитаем сколько раз луч пересекает рёбра многоугольника. Для этого достаточно пройтись в цикле по рёбрам многоугольника и определить, пересекает ли луч каждое ребро. Если число пересечений нечётно, то объявляется, что точка лежит внутри многоугольника, если чётно |
||
[[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>Eric Haines. [http://erich.realtimerendering.com/ptinpoly/ Point in Polygon Strategies]</ref> Таким образом, пересечение луча с ребром засчитывается, если один из концов ребра лежит строго ниже луча, а другой конец |
В алгоритме возникает затруднение в вырожденном случае, когда луч пересекает вершину многоугольника. Один из приёмов для его преодоления заключается в том, чтобы считать, что такие вершины многоугольника лежат на бесконечно малую величину выше (или ниже) прямой луча, и стало быть пересечения на самом деле и нет.<ref>Eric Haines. [http://erich.realtimerendering.com/ptinpoly/ Point in Polygon Strategies]</ref> Таким образом, пересечение луча с ребром засчитывается, если один из концов ребра лежит строго ниже луча, а другой конец — выше или лежит на луче. |
||
Алгоритм работает за время O(''N'') для ''N''-угольника. |
Алгоритм работает за время O(''N'') для ''N''-угольника. |
||
=== Учёт числа оборотов === |
|||
== Winding number == |
|||
[[Image:Winding Number 2.svg|right|thumb|150px|Кривая делает два оборота вокруг данной точки.]] |
|||
{{дописать раздел}} |
|||
Рассмотрим число оборотов, которые делает граница многоугольника вокруг данной точки ''P''. В алгебраической топологии это число называется {{lang-en2|winding number}}.<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|winding number}}. Сумма будет положительной или отрицательной, в зависимости от ориентации границы. Если она не равна нулю, то будем считать, что точка лежит внутри многоугольника, иначе — снаружи. |
|||
Такой алгоритм известен под названием {{lang-en2|nonzero winding rule}}.<ref name="foley" /> |
|||
Для простых многоугольников этот метод работает так же, как и метод, основанный на подсчёте числа пересечений. Разница между ними проявляется при рассмотрении многоугольников с самопересекающейся границей. |
|||
{{clear}} |
|||
== Алгоритмы c предобработкой == |
== Алгоритмы c предобработкой == |
||
Версия от 05:11, 2 мая 2011
В вычислительной геометрии известна задача об определении принадлежности точки многоугольнику. На плоскости даны многоугольник и точка. Требуется решить вопрос о принадлежности точки многоугольнику.
Многоугольник может быть как выпуклым, так и невыпуклым. Обычно предполагается, что многоугольник простой, т.е. без самопересечений, но задачу рассматривают и для не-простых многоугольников. В последнем случае разные способы определения принадлежности точки многоугольнику могут привести к разным результатам. Различают алгоритмы без предварительной обработки и алгоритмы с предварительной обработкой, в ходе которой создаются некоторые структуры данных, позволяющие в дальнейшем быстрее отвечать на множество запросов о принадлежности точек одному и тому же многоугольнику.
Метод трассировки луча
Учёт числа пересечений
Один из стандартных методов определения принадлежности точки произвольному простому многоугольнику заключается в следующем. Выпустим луч из данной точки в произвольном направлении (например в положительном направлении горизонтальной оси), и посчитаем сколько раз луч пересекает рёбра многоугольника. Для этого достаточно пройтись в цикле по рёбрам многоугольника и определить, пересекает ли луч каждое ребро. Если число пересечений нечётно, то объявляется, что точка лежит внутри многоугольника, если чётно — то снаружи. Это основано на том простом наблюдении, что при движении по лучу с каждым пересечением границы точка попеременно оказывается то внутри, то снаружи многоугольника. Алгоритм известен под таким названиями, как crossing number (count) algorithm или even-odd rule.
В алгоритме возникает затруднение в вырожденном случае, когда луч пересекает вершину многоугольника. Один из приёмов для его преодоления заключается в том, чтобы считать, что такие вершины многоугольника лежат на бесконечно малую величину выше (или ниже) прямой луча, и стало быть пересечения на самом деле и нет.[1] Таким образом, пересечение луча с ребром засчитывается, если один из концов ребра лежит строго ниже луча, а другой конец — выше или лежит на луче.
Алгоритм работает за время O(N) для N-угольника.
Учёт числа оборотов
Рассмотрим число оборотов, которые делает граница многоугольника вокруг данной точки P. В алгебраической топологии это число называется winding number.[2] Оно может быть вычислено следующим образом. Как и раньше, выпустим луч из P в произвольном направлении и рассмотрим рёбра, которые он пересекает. Каждому пересечение присвоим число +1 или -1, в завимимости от того, как рёбро пересекает луч — по часовой (слева направо) или против часовой стрелки (справа налево). Эти два случая можно различить по знаку скалярного произведения между направляющим вектором ребра и нормалью к направляющему вектору луча.[3] Сумма полученных величин и есть winding number. Сумма будет положительной или отрицательной, в зависимости от ориентации границы. Если она не равна нулю, то будем считать, что точка лежит внутри многоугольника, иначе — снаружи.
Такой алгоритм известен под названием nonzero winding rule.[3]
Для простых многоугольников этот метод работает так же, как и метод, основанный на подсчёте числа пересечений. Разница между ними проявляется при рассмотрении многоугольников с самопересекающейся границей.
Алгоритмы c предобработкой
Выпуклые и звёздные многоугольники
Принадлежность точки выпуклому или звёздному N-угольнику может быть определена при помощи двоичного поиска за время O(log N), при затрате O(N) памяти и O(N) времени на предварительную обработку.[4]
Произвольный многоугольник
Задачу об принадлежности точки произвольному простому многоугольнику можно рассматривать как частный случай задачи о локализации точки в планарном подразбиении. Для N-угольника эта задача может быть решена за время O(log2 N) с использованием O(N) памяти и O(N log N) времени на предобработку.[5]
Примечания
- ↑ Eric Haines. Point in Polygon Strategies
- ↑ Может переводиться на русский язык как «индекс кривой относительно точки», «число кручения», «число намоток», «винтовое число» и т.п.
- ↑ 1 2 Foley J. D., et al. Computer Graphics: Principles and Practice. Addison-Wesley. 1990. P. 965.
- ↑ Препарата, Шеймос. Стр. 60-61.
- ↑ Препарата, Шеймос. Стр. 74. Теорема 2.6.
Литература
- Препарата Ф., Шеймос М. Вычислительная геометрия. Введение. Раздел 2.2: Задачи локализации точек. М.: Мир, 1989.
Ссылки
- Dan Sunday. Fast Winding Number Inclusion of a Point in a Polygon
- Bob Stein. A Point about Polygons
- Российская Интернет-школа информатики и программирования. Учебные курсы. Введение в алгоритмику. Вычислительная геометрия
- Альтернативный метод проверки принадлежности точки многоугольнику - метод трассировки луча
 | Для улучшения этой статьи по информационным технологиям желательно:
|