Четный нечетный метод и метод числа обмоток - внутреннее и внешнее испытание полигона
Введение :
Многоугольник может быть представлен как ряд отрезков, соединенных концами с замкнутой фигурой.
Многоугольники могут быть представлены двумя способами:
(i) план с использованием команд перемещения и
(ii) как твердые объекты, установив пиксели высоко внутри полигона, включая пиксели на границе.
Чтобы определить, находится точка внутри многоугольника или нет, в компьютерной графике у нас есть два метода:
(a) Метод четности-нечетности (правило нечетной четности)
(b) Номер обмотки Метод-внутри
Четно-нечетный метод:
Построение отрезка прямой между исследуемой точкой (P) и известной точкой вне многоугольника является одним из способов определить, лежит ли точка внутри многоугольника или нет. Затем подсчитывается количество пересечений сегментом линии границы полигона. Точка (P) является внутренней точкой, если количество ребер многоугольника, пересекаемых этой линией, нечетно; в противном случае точка является внешней точкой.
На рисунке отрезок линии от «А» пересекает одно ребро, и, следовательно, точка А находится внутри многоугольника. Точка B также находится внутри многоугольника, поскольку отрезок линии от B пересекает три (нечетных) ребра. Но точка C находится вне многоугольника, так как отрезок от C пересекает два (четных) ребра.
Но этот четно-нечетный тест не проходит, когда точка пересечения является вершиной.
Чтобы справиться с этим случаем, мы должны сделать несколько модификаций.
Мы должны посмотреть на другие конечные точки двух сегментов многоугольника, которые встречаются в этой вершине. Если эти точки лежат по одну сторону от построенной линии A'P', то точка пересечения считается четным числом пересечений. Но если они лежат на противоположной стороне построенной линии AP, то точки пересечения считаются за одно пересечение.
Как мы видим, отрезок A'P' пересекается в точке M, которая является вершиной, а L и Z являются другими конечными точками двух отрезков, встречающихся в M. L и Z лежат на одной стороне отрезка A'P' , поэтому счет считается четным.
Метод номера обмотки:
Существует еще один альтернативный метод определения внутренней точки многоугольника, который называется методом числа витков. Концептуально можно натянуть кусок резинки между проверяемой точкой (P) и точкой на границе полигона.
При этом резинка прочно привязывается к проверяемой точке (P), а другой конец резинки скользит по границе многоугольника, пока не сделает один полный оборот. Затем проверяем, сколько раз резинка была намотана на точку пересечения. Если он закручен хотя бы один раз, острие внутри. Если чистой обмотки нет, то точка находится снаружи.
В этом методе вместо простого подсчета пересечений мы присваиваем каждой пересеченной линии границы номер направления и суммируем эти номера направлений. Номер направления указывает направление, в котором ребро многоугольника было нарисовано относительно сегмента линии, который мы построили для теста.
Пример: Чтобы проверить точку (x i , y i ), рассмотрим горизонтальный отрезок y = y i , который проходит снаружи многоугольника к ( xi , y i ) . Находим все стороны, которые пересекали этот отрезок.
Теперь есть 2 способа пересечения стороны, сторона может быть нарисована, начиная с конца, пересекая ее и заканчивая над линией. В этом случае мы можем указать номера направления – 1, в сторону, или ребро может начаться над линией и закончиться под ней в этом случае, учитывая направление 1. Сумма чисел направлений для сторон, которые пересекают построенную горизонтальную линию. сегмент дает «Winding Number» для точки.
Если число витков не равно нулю, точка находится внутри многоугольника, в противном случае — снаружи многоугольника.
На приведенном выше рисунке отрезок пересекает 4 ребра с разными номерами направления: 1, -1, 1 и -1 соответственно, тогда:
Номер обмотки = 1 + (-1) + 1 + (-1) = 0
Итак, точка P находится вне многоугольника. Ребро имеет направление номер -1, потому что оно начинается ниже сегмента линии и заканчивается выше. Точно так же ребро имеет направление номер +1, потому что оно начинается сверху сегмента линии и заканчивается ниже сегмента линии (см. направления на рисунке).