Точка внутри полигона

← →
serg_1 (2002-11-04 15:14) [0]

Доброго времени суток,

Где-то (может быть здесь?) видел алгоритм по определению нахождения точки внутри полигона. Насколько я помню этот алгоритм базировался на подсчете количества оборотов луча, исходящего из точки к вершине полигона ("крутимся" по всем вершинам). Если не сложно, поделитесь им плз.

P.S. ф-ции аля PtInRegion не предлагать (нужен сам алгоритм, поскольку я пока "системонезависем", да и точки имеют другой тип).

← →
MBo (2002-11-04 15:18) [1]

проводим из точки прямую, считаем количество пересечений каждого луча со сторонами.
Если четное - внутри. При этом надо не попасть на вершину.

← →
Lord Warlock (2002-11-04 15:23) [2]

А если соединить отрезком проверяемую точку и гарантированно лежащую вне полигона и посчитать кол-во пересечений сторон полигона.

← →
serg_1 (2002-11-04 15:38) [3]

2MBo
берем бублик, точка центр бублика. любая прямая дает 4 пересечения (естественно мы в двумерной с-ме координат). а вообще, насколько я помню, алгоритм "подсчета оборотов" реализуется и работает пошустрее.

← →
MBo (2002-11-04 15:45) [4]

я написал - каждого луча прямой. Но ошибся -для внутренней точки должно быть нечетным.

посмотри еще это - я не проверял

type XYPoint = record
x,y: double;
end;

function IsInsidePolygon(const Polygon: array of XYpoint; const p: XYPoint):
boolean;
// returns "true" if p is inside polygon
var
i: integer;
p1, p2: ^XYPoint;
begin
Result:= false;
p2:= @Polygon[High(Polygon)];
for i:=Low(Polygon) to High(Polygon) do begin
p1:= @Polygon[i];
if ( (((p1.y<=p.y) and (p.y<p2.y)) or ((p2.y<=p.y) and (p.y<p1.y)))
and
(p.x<(p2.x-p1.x)*(p.y-p1.y)/(p2.y-p1.y)+p1.x) )
then Result:= not Result;
p2:= p1;
end;
end;

← →
serg_1 (2002-11-04 16:16) [5]

угу, это похоже есть подсчет числа пересечиний луча (x,y) - (x, +infinity) с полигоном. работает почти всегда:). в случае, если для какой-то стороны y=y1=y2 результат не определен.

← →
Ketmar (2002-11-06 12:57) [6]

2serg_1:
а такие стороны можно смело выкидывать, ибо толку от них - 0. в принципе - очень даже работоспособный алгоритм (у меня шуршит не первый год, и ничего %-)).

Satanas Nobiscum! 06-Nov-XXXVII A.S.

← →
Sapersky_ (2002-11-10 11:44) [7]

А определение пересечения двух произвольных отрезков - не подскажете ли?

← →
MBo (2002-11-10 12:58) [8]

http://algolist.manual.ru/maths/geom/intersect/lineline2d.php

← →
Miha-ha (2002-11-10 14:05) [9]

Есть такой вариант, но только для выпуклых полигонов:
Нужно провести от точки ко всем вершинам полигона прямые и подсчитать сумму углов меж этими прямыми, если она меньше 360градусов тогда точка либо вне полигона либо на границе полигона, если равна 360 то точка внутри!

← →
Sapersky_ (2002-11-10 22:17) [10]

Спасибо. Я вроде и сам уже придумал - у меня есть функция определения положения точки относительно отрезка (справа/слева), и если точки одного отрезка лежат по разные стороны другого и наоборот, то вроде они пересекаются.

← →
serg_1 (2002-11-12 11:22) [11]

2Ketmar
там еще надо смотреть пересекает ли наш луч вершину и если да, то каким образом (возможны три типа, случай когда у=у1=у2 действительно можно просто игнорировать:))
\/ \
--, ---, ---
/\ /
в первом и втором случаях пересечение не считаем, в последнем считаем.
2Miha-ha
насколько я понял имеется ввиду алгоритм, который считает сумму углов между нашей точкой (t) и точками (t1,..,tn) полигона, т.е.
угол_между((t;t1),(t;t2))+угол_между((t;t2),(t;t3))+...+угол_между((t;tn),(t;t1)).
если да, то почему он применим только для выпуклых полигонов? может быть ограничение более слабое, - для несамопересекающихся?

← →
Ketmar (2002-11-12 17:22) [12]

2serg_1:
да, конечно. извиняюсь за краткость и неточность - ну уж очень давно было, мог и забыть %-)

Satanas Nobiscum! 12-Nov-XXXVII A.S.

← →
SashaS (2002-11-15 16:33) [13]

Работает алгоритм для произвольных многоугольников даже с самопересечениями.

Подсчитывает сумму углов при обходе.

function testInsideRegion(X, Y: Integer;points:TPoints):boolean;
var i,j,k:Integer;
gangl,ang,sm,ab,bc,ac,scal:real;
pa,pb,pcl,pav,pnm,pna:Tpoint;

function rr(r1,r2:TPoint):real;
begin
result:= sqrt(sqr(r1.x-r2.x)+sqr(r1.y-r2.y));
end;

begin

ang:=0;

for i:= 1 to length(points) do //
begin

pa:=points[i-1];

if i=length(points) then pb:=points[0]
else pb:=points[i];

pcl.x:=x;
pcl.y:=y;

pav.x:= ((pa.x+pb.x)div 2)-pcl.x;
pav.y:= ((pa.y+pb.y)div 2)-pcl.y;

pnm.x:= pav.y;
pnm.y:=-pav.x;

pna.x:= pb.x-pa.X;
pna.y:= pb.y-pa.y;
scal := pnm.x*pna.X +pnm.y*pna.y;

ab:= rr(pa,pb);
ac:= rr(pa,pcl);
bc:= rr(pcl,pb);

if (abs(ac)<0.01)or(abs(bc)<0.01) then
begin
ang:=2*pi;
break;
end;

gangl:= (-sqr(ab)+sqr(bc)+sqr(ac)) /(2*ac*bc);
if abs(gangl)>=1 then sm:=pi else sm:= arcCos(gangl);

if scal>0 then ang:= ang + sm else ang:= ang - sm;
end;

if abs(abs(ang)-2*pi)<0.01 then
result:=true else
result:=false;

end;

Точка внутри полигона Найти похожие ветки