Определение положения точки относительно плоского многоугольника

Введение

Определение местоположения точки относительно сопланарного многоугольника

В вычислительной геометрии задача «точка в многоугольнике» (PIP) заключается в определении, находится ли заданная точка на плоскости внутри, снаружи или на границе многоугольника. Это частный случай задач определения местоположения точки и находит применение в областях, связанных с обработкой геометрических данных, таких как компьютерная графика, компьютерное зрение, географические информационные системы (ГИС), планирование траекторий и системы автоматизированного проектирования (САПР). Раннее описание этой проблемы в компьютерной графике демонстрирует два распространенных подхода (метод отбрасывания лучей и суммирование углов), которые использовались уже в 1974 году. Попытка опытных специалистов в области компьютерной графики проследить историю этой задачи и некоторые методы ее решения можно найти в одном из выпусков Ray Tracing News.

Алгоритм лучевого отбрасывания

Один из простых способов определить, находится ли точка внутри или снаружи простого многоугольника, — это проверить, сколько раз луч, исходящий из этой точки в любом фиксированном направлении, пересекает ребра многоугольника. Если точка находится снаружи многоугольника, луч пересечет его ребра четное число раз. Если точка находится внутри многоугольника, луч пересечет его ребра нечетное число раз. Статус точки, лежащей на ребре многоугольника, зависит от деталей алгоритма определения пересечений луча. Этот алгоритм также известен как алгоритм числа пересечений или алгоритм правила «чёт-нечёт», и был известен ещё в 1962 году. Алгоритм основан на простом наблюдении: если точка движется вдоль луча от бесконечности к проверяемой точке и пересекает границу многоугольника, возможно, несколько раз, то она попеременно переходит извне внутрь, а затем изнутри наружу, и так далее. В результате, после каждого второго пересечения границы движущаяся точка оказывается снаружи. Это наблюдение может быть математически доказано с помощью теоремы Жордана о кривой.

Ограниченная точность

Если реализовать на компьютере с арифметикой конечной точности, результаты могут быть неверными, если точка находится очень близко к этой границе из-за ошибок округления. Для некоторых приложений, таких как видеоигры или другие развлекательные продукты, это не является существенной проблемой, поскольку они часто отдают предпочтение скорости, а не точности. Однако для формально корректной компьютерной программы необходимо ввести числовую погрешность ε и проверять, находится ли точка P (точка) на расстоянии не более ε от линии L (линии), в этом случае алгоритм должен остановиться и сообщить, что "точка P находится очень близко к границе". Большинство реализаций алгоритма трассировки лучей последовательно проверяют пересечения луча со всеми сторонами многоугольника. В этом случае необходимо решить следующую проблему. Если луч проходит точно через вершину многоугольника, он будет пересекать два сегмента в их конечных точках. Хотя это допустимо для верхней вершины в примере или вершины между пересечениями 4 и 5, для правой вершины (в примере) требуется учитывать только одно пересечение для правильной работы алгоритма. Аналогичная проблема возникает с горизонтальными сегментами, которые случайно оказываются на луче. Проблема решается следующим образом: если точка пересечения является вершиной рассматриваемой стороны многоугольника, то пересечение учитывается только в том случае, если другая вершина стороны находится ниже луча. Это эквивалентно тому, что вершины, лежащие на луче, рассматриваются как немного выше луча. Вновь, случай прохождения луча через вершину может вызывать численные проблемы при арифметике конечной точности: для двух сторон, примыкающих к одной и той же вершине, прямое вычисление пересечения с лучем может не дать вершину в обоих случаях. Если многоугольник задан своими вершинами, эта проблема устраняется путем проверки y-координат луча и концов рассматриваемой стороны многоугольника перед фактическим вычислением пересечения. В других случаях, когда стороны многоугольника вычисляются из других типов данных, для обеспечения численной устойчивости алгоритма необходимо применять другие методы.

If implemented on a computer with finite precision arithmetics, the results may be incorrect if the point lies very close to that boundary, because of rounding errors. For some applications, like video games or other entertainment products, this is not a large concern since they often favor speed over precision. However, for a formally correct computer program, one would have to introduce a numerical tolerance ε and test in line whether P (the point) lies within ε of L (the Line), in which case the algorithm should stop and report "P lies very close to the boundary." Most implementations of the ray casting algorithm consecutively check intersections of a ray with all sides of the polygon in turn. In this case the following problem must be addressed. If the ray passes exactly through a vertex of a polygon, then it will intersect 2 segments at their endpoints. While it is OK for the case of the topmost vertex in the example or the vertex between crossing 4 and 5, the case of the rightmost vertex (in the example) requires that we count one intersection for the algorithm to work correctly. A similar problem arises with horizontal segments that happen to fall on the ray. The issue is solved as follows: If the intersection point is a vertex of a tested polygon side, then the intersection counts only if the other vertex of the side lies below the ray. This is effectively equivalent to considering vertices on the ray as lying slightly above the ray. Once again, the case of the ray passing through a vertex may pose numerical problems in finite precision arithmetics: for two sides adjacent to the same vertex the straightforward computation of the intersection with a ray may not give the vertex in both cases. If the polygon is specified by its vertices, then this problem is eliminated by checking the y coordinates of the ray and the ends of the tested polygon side before actual computation of the intersection. In other cases, when polygon sides are computed from other types of data, other tricks must be applied for the numerical robustness of the algorithm.

Алгоритм намотки

Другой метод, используемый для проверки, находится ли точка внутри многоугольника, — это вычисление числа обмотки данной точки относительно многоугольника. Если число обмотки не равно нулю, точка лежит внутри многоугольника. Этот алгоритм также известен как алгоритм ненулевого правила. Один из способов вычисления числа обмоток — суммировать углы, образуемые каждой стороной многоугольника. Однако это требует использования дорогостоящих обратных тригонометрических функций, что обычно делает этот алгоритм менее эффективным (более медленным) по сравнению с алгоритмом отбрасывания лучей. К счастью, вычислять эти обратные тригонометрические функции не обязательно. Поскольку результат, сумма всех углов, может быть равен только 0 или π (или кратным π), достаточно отслеживать, через какие квадранты обходит многоугольник, вращаясь вокруг проверяемой точки. Это делает алгоритм числа обмотки сопоставимым по скорости с подсчетом пересечений границы. Улучшенный алгоритм вычисления числа обмотки был разработан Дэном Сандеем в 2001 году. Он не использует углы или тригонометрию в вычислениях и работает точно так же, как описанные выше алгоритмы отбрасывания лучей. Алгоритм Сандея работает, рассматривая бесконечный горизонтальный луч, исходящий из проверяемой точки. Каждый раз, когда этот луч пересекает ребро многоугольника, используется алгоритм пересечения ребер Хуана Пинеды (1988) для определения того, как это пересечение повлияет на число обмоток. Как описывает Сандей, если ребро пересекает луч, идущий "вверх", число обмотки увеличивается; если оно пересекает луч "вниз", число уменьшается. Алгоритм Сандея дает правильный ответ для не простых многоугольников, в то время как алгоритм пересечения границы в этом случае дает сбой. На алгоритм заполнения влияет атрибут "правило заполнения". Значение может быть либо 0, либо 1. Например, в пентаграмме есть центральное "отверстие" (видимый фон) со значением 1, и его нет со значением 0. Для простых многоугольников алгоритмы дадут одинаковый результат. Однако для сложных многоугольников алгоритмы могут давать разные результаты для точек в областях, где многоугольник самопересекается, где у многоугольника нет четко определенной внутренней и внешней сторон. Одним из решений, использующих правило четности, является преобразование (сложных) многоугольников в более простые, эквивалентные по правилу четности, перед проверкой пересечения. Однако это вычислительно дорого. Дешевле использовать быстрый алгоритм ненулевого числа обмотки, который дает правильный результат даже при самопересечении многоугольника.

Another technique used to check if a point is inside a polygon is to compute the given point's winding number with respect to the polygon. If the winding number is non zero, the point lies inside the polygon. This algorithm is sometimes also known as the nonzero rule algorithm. One way to compute the winding number is to sum up the angles subtended by each side of the polygon. However, this involves costly inverse trigonometric functions, which generally makes this algorithm performance inefficient (slower) compared to the ray casting algorithm. Luckily, these inverse trigonometric functions do not need to be computed. Since the result, the sum of all angles, can add up to 0 or (or multiples of ) only, it is sufficient to track through which quadrants the polygon winds, as it turns around the test point, which makes the winding number algorithm comparable in speed to counting the boundary crossings. An improved algorithm to calculate the winding number was developed by Dan Sunday in 2001. It does not use angles in calculations, nor any trigonometry, and functions exactly the same as the ray casting algorithms described above. Sunday's algorithm works by considering an infinite horizontal ray cast from the point being checked. Whenever that ray crosses an edge of the polygon, Juan Pineda's edge crossing algorithm (1988) is used to determine how the crossing will affect the winding number. As Sunday describes it, if the edge crosses the ray going "upwards", the winding number is incremented; if it crosses the ray "downwards", the number is decremented. Sunday's algorithm gives the correct answer for nonsimple polygons, whereas the boundary crossing algorithm fails in this case. The algorithm of filling is influenced by 'fill rule' attribute. The value may be either or For example, in a pentagram, there is a central "hole" (visible background) with , and none with attribute. For simple polygons, the algorithms will give the same result. However, for complex polygons, the algorithms may give different results for points in the regions where the polygon intersects itself, where the polygon does not have a clearly defined inside and outside. One solution using the even odd rule is to transform (complex) polygons into simpler ones that are even odd equivalent before the intersection check. This, however, is computationally expensive. It is less expensive to use the fast non zero winding number algorithm, which gives the correct result even when the polygon overlaps itself.

Точка в запросах полигона

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

Особые случаи

Простейшие алгоритмы возможны для монотонных, звездообразных, выпуклых многоугольников и треугольников. Случай треугольника можно легко решить, используя барицентрические координаты, параметрическое уравнение или скалярное произведение. Метод скалярного произведения естественно расширяется на любой выпуклый многоугольник.