Проверка на принадлежность точки многоугольнику
http://delphid.dax.ru/www/exampl35.htm
Проверка на принадлежность точки многоугольнику
Формулировка задачи проста. Задан последовательный набор точек (хi,уi), i=1..n. Для заданной точки проверить, принадлежит ли она замкнутому многоугольнику, заданному этими точками, или нет.
Используется метод 2d.php"трассировки луча. Суть его в том, что если из заданной точки провести произвольный луч (не важно в каком направлении), то по числу пересечений этого луча со сторонами многоугольника можно однозначно сказать, лежит ли точка внутри или снаружи. А именно, если число пересечений четно (или 0) - то снаружи, нечетно - внутри. Причем, как оказывается, не важно в каком порядке следуют стороны. Для проверки пересечения луча со сторонами, используем процедуру из рассмотренной ранее задачи нахождение точки пересечения двух отрезков на плоскости, слегка ее видоизменив. А именно, если раньше нас интересовали только такие решения системы уравнений, когда параметр tb лежит в диапазоне [0.1] (что определяте отрезок), то теперь нас будут устраивать значения [0,бесконечность) (что определяет луч).
Несколько слов о программе. Исходные данные в виде восьми координат считываются из файла poligon.txt. В качестве примера можно использовать, например, такие значения:
1 1 2 1 2 2
3 2 3 1 4 0
4 5 1 5
Только убедитесь, что после последней пятерки в файле не присутствуют ни пробелы, ни концы строк, иначе будет прочитан лишнй ноль.
Точка а задается случайным образом.
Вместо сравнения d с нулем (if (d=0) ...) используется сравнение с малым числом Eps. Сделано это для того, чтобы не делить на очень малые числа. В вещественных представлениях числа 0 зачастую присутствуют что-нибудь вроде 1Е-12, и формального равенства с нулем нет, но фактически это самый что ни на есть 0.
const eps = 0.000001;
maxNodes = 50;
type point = object
x,y:real;
procedure setPoint(xp,yp:real);
end;
poligonType = array[1..maxNodes] of point;
procedure point.setPoint(xp,yp:real);
begin
x:=xp;
y:=yp;
end;
var a,ax,c:point;
function readPoligon(var p:poligonType):integer;
var buf:text;
n:integer;
x1,y1:real;
begin
assign(buf, 'poligon.txt');
reset(buf);
n:=0;
{$I-}
while not eof(buf) and (n<=maxNodes) and (IOResult=0) do
begin
inc(n);
read(buf, p[n].x);
if (IOResult = 0) then
read(buf, p[n].y);
end;
if (IOResult <> 0) then dec(n);
{$I+}
if (not eof(buf)) then
writeln(' The maximum number of nodes has been reached. Using maxN=',maxNodes);
readPoligon := n;
end;
const
ONE_INTERSECTION_POINT = 1;
CHUNKS_ARE_PARALLEL = 0;
NO_INTERSCTION = -1;
A1_BORDER_INTERSECTION = 2;
function checkIntersection(a1,a2,b1,b2:Point):shortint;
{
returns
1 if there is one intersection point "c"
0 if chunks ar on parallel lines
-1 if there are no intersection points
2 if a1 lies on [b1,b2]
}
var d,da,db,ta,tb: real;
{
}
begin
d :=(a1.x-a2.x)*(b2.y-b1.y) - (a1.y-a2.y)*(b2.x-b1.x);
da:=(a1.x-b1.x)*(b2.y-b1.y) - (a1.y-b1.y)*(b2.x-b1.x);
db:=(a1.x-a2.x)*(a1.y-b1.y) - (a1.y-a2.y)*(a1.x-b1.x);
{writeln('d=',d:12:4,'da=',da:12:4,'db=',db:12:4);}
if (abs(d)<eps) then
checkIntersection := CHUNKS_ARE_PARALLEL
else
begin
ta:=da/d;
tb:=db/d;
if (abs(ta)<eps) and ((0<=tb) and (tb<=1))
then checkIntersection := A1_BORDER_INTERSECTION
else
if (0<=ta) {and (ta<=1)} { luch a -----> }
and (0<=tb) and (tb<=1)
then
begin
c.setPoint(a1.x+ta*(a2.x-a1.x),a1.y+ta*(a2.y-a1.y));
checkIntersection := ONE_INTERSECTION_POINT
end
else checkIntersection := NO_INTERSCTION;
end;
end;
var i,n:integer;
plg:poligonType;
xr,yr:real;
function pointInsidePoligon(a:Point;plg:poligonType):integer;
{ 0 - outside
1 - inside
2 - on border
}
var i,k,i1,i2,r:integer;
ax:Point;
begin
ax.setPoint(a.x+5,a.y);
k:=0;
for i:=1 to n do
begin
i1:=i; i2:=i+1; if (i=n) then i2:=1;
r:=checkIntersection(a,ax,plg[i1],plg[i2]);
if (r=2) then
begin
pointInsidePoligon := 2; exit;
end;
if (r=1) then
k:=1-k;
end;
pointInsidePoligon := k;
end;
begin
n:=readPoligon(plg);
xr:=4; yr:=1;
for i:=1 to 20 do
begin
a.setPoint(xr,yr);
write(i:3,'. Point A(',a.x:8:4,',',a.y:8:4,') ');
case pointInsidePoligon(a,plg) of
1: writeln('is inside');
0: writeln('is outside');
2: writeln('on border');
end;
xr:=random(60); xr:=(xr)/10;
yr:=random(50); yr:=(yr)/10;
end;
end.
Примечание 2 .
https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0HYPERLINK "https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83"%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83
В вычислительной геометрии известна задача об определении принадлежности точки многоугольнику. На плоскости даны 0%9C%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA"многоугольник и 0%A2%D0%BE%D1%87%D0%BA%D0%B0_%28%D0%B3%D0%B5%D0%BE%D0%BC%D0%B5%D1%82%D1%80%D0%B8%D1%8F%29"точка. Требуется решить вопрос о принадлежности точки многоугольнику.
Многоугольник может быть как 0%92%D1%8B%D0%BF%D1%83%D0%BA%D0%BB%D1%8B%D0%B9_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA"выпуклым, так и невыпуклым. Обычно предполагается, что многоугольник простой, т.е. без самопересечений, но задачу рассматривают и для не-простых многоугольников. В последнем случае разные способы определения принадлежности точки многоугольнику могут привести к разным результатам. Различают алгоритмы без предварительной обработки и алгоритмы с предварительной обработкой, в ходе которой создаются некоторые структуры данных, позволяющие в дальнейшем быстрее отвечать на множество запросов о принадлежности точек одному и тому же многоугольнику.
Содержание
• 1HYPERLINK "https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83" HYPERLINK "https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83"Метод трассировки луча
• 1.1HYPERLINK "https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83" HYPERLINK "https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83"Учёт числа пересечений
• 1.2HYPERLINK "https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83" HYPERLINK "https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83"Учёт числа оборотов
• 2HYPERLINK "https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83" HYPERLINK "https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83"Метод суммирования углов
• 3HYPERLINK "https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83" HYPERLINK "https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83"Алгоритмы c предобработкой
• 3.1HYPERLINK "https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83" HYPERLINK "https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83"Выпуклые и звёздные многоугольники
• 3.2HYPERLINK "https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83" HYPERLINK "https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83"Произвольный многоугольник
• 4HYPERLINK "https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83" HYPERLINK "https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83"Примечания
• 5HYPERLINK "https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83" HYPERLINK "https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83"Литература
• 6HYPERLINK "https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83" HYPERLINK "https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83"Ссылки
Метод трассировки луча
Учёт числа пересечений
Методы работают по-разному для многоугольников с самопересекающейся границей. Слева: even-odd rule. Справа: nonzero winding rule.
Один из стандартных методов определения принадлежности точки произвольному простому многоугольнику заключается в следующем. Выпустим луч из данной точки в произвольном направлении (например в положительном направлении горизонтальной оси), и посчитаем сколько раз луч пересекает рёбра многоугольника. Для этого достаточно пройтись в цикле по рёбрам многоугольника и определить, пересекает ли луч каждое ребро. Если число пересечений нечётно, то объявляется, что точка лежит внутри многоугольника, если чётно — то снаружи. Это основано на том простом наблюдении, что при движении по лучу с каждым пересечением границы точка попеременно оказывается то внутри, то снаружи многоугольника. Алгоритм известен под такими названиями, как crossing number (count) algorithm или even-odd rule.
В алгоритме возникает затруднение в вырожденном случае, когда луч пересекает вершину многоугольника. Один из приёмов для его преодоления заключается в том, чтобы считать, что такие вершины многоугольника лежат на бесконечно малую величину выше (или ниже) прямой луча, и стало быть пересечения на самом деле и нет.0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83"[1] Таким образом, пересечение луча с ребром засчитывается, если один из концов ребра лежит строго ниже луча, а другой конец — выше или лежит на луче.
Алгоритм работает за время O(N) для N-угольника.
Учёт числа оборотов
Кривая делает два оборота вокруг данной точки.
Рассмотрим число оборотов, которое делает ориентированная граница многоугольника вокруг данной точки P. В алгебраической топологии это число называется 0%9F%D0%BE%D1%80%D1%8F%D0%B4%D0%BE%D0%BA_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BE%D1%82%D0%BD%D0%BE%D1%81%D0%B8%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE_%D0%BA%D1%80%D0%B8%D0%B2%D0%BE%D0%B9"индексом точки относительно кривой.0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83"[2] Оно может быть вычислено следующим образом. Как и раньше, выпустим луч из P в произвольном направлении и рассмотрим рёбра, которые он пересекает. Каждому пересечению присвоим число +1 или -1, в зависимости от того, как ребро пересекает луч — по часовой (слева направо) или против часовой стрелки (справа налево). Эти два случая можно различить по знаку скалярного произведения между направляющим вектором ребра и нормалью к направляющему вектору луча.0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83"[3] Сумма полученных величин и есть 0%9F%D0%BE%D1%80%D1%8F%D0%B4%D0%BE%D0%BA_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BE%D1%82%D0%BD%D0%BE%D1%81%D0%B8%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE_%D0%BA%D1%80%D0%B8%D0%B2%D0%BE%D0%B9"индекс точки относительно кривой. Сумма будет положительной или отрицательной, в зависимости от ориентации границы. Если она не равна нулю, то будем считать, что точка лежит внутри многоугольника, иначе — снаружи.
Такой алгоритм известен под названием nonzero winding rule.0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83"[3]
Для простых многоугольников этот метод работает так же, как и метод, основанный на подсчёте числа пересечений. Разница между ними проявляется при рассмотрении многоугольников с самопересекающейся границей.
Метод суммирования углов
Можно определить, что точка P находится внутри многоугольника c вершинами V0, V1, ..., Vn = V0, вычислив сумму:
,
где — угол (в радианах и со знаком) между лучами PVi - 1 и PVi, т.е.:
Можно доказать, что эта сумма есть не что иное, как winding number точки P относительно границы многоугольника, с точностью до константного множителя . Поэтому можно считать, что точка лежит снаружи многоугольника, если сумма равна нулю (или достаточно близка к нему, если используется приближённая арифметика). Однако данный метод весьма непрактичен, так как требует вычисления дорогостоящих операций для каждого ребра (обратных тригонометрических функций, квадратных корней), и был даже назван «худшим в мире алгоритмом» для данной задачи.0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83"[1]
К. Вейлером был предложен практичный вариант этого метода, избегающий дорогостоящих операций и приближенных вычислений.0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83"[4] Было показано, что сумму углов можно вычислить, используя лишь операцию классификации точки многоугольника по квадрантам относительно точки P. Алгоритм Вейлера и некоторые улучшения к нему описываются в 0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D0%B0%D0%B4%D0%BB%D0%B5%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D1%82%D0%BE%D1%87%D0%BA%D0%B8_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA%D1%83"[5].
Алгоритмы c предобработкой