Delphi-PRAXiS - Ist ein Punkt in einem Polygon

Seite 1 von 3

Delphi-PRAXiS (https://www.delphipraxis.net/forum.php)

- Software-Projekte der Mitglieder (https://www.delphipraxis.net/26-software-projekte-der-mitglieder/)

- - Ist ein Punkt in einem Polygon (https://www.delphipraxis.net/86939-ist-ein-punkt-einem-polygon.html)

Ist ein Punkt in einem Polygon

Nicht immer, aber immer wieder taucht die Frage auf, wie man wohl feststellen kann, ob ein Punkt innerhalb eines Dreiecks oder innerhalb einer anderen Figur liegt.

Ich habe dieses Thema mal ganz allgemein betrachtet und eine kleine Funktion geschrieben, die prüft, ob sich ein Punkt innerhalb eines konvexen nicht überschlagenden Polygons befindet.
Ein Programm zum Testen ist im Anhang.
Vielleicht interessiert es den einen oder anderen.

Delphi-Quellcode:

			{------------------------------------------------------------------------------}

{ PtInPolygon                                                                  }

{ Prüft, ob ein Punkt innerhalb eines Polygons liegt.                          }

{ Das Polygon muß konvex sein und darf keine Überschneidungen haben.           }

{------------------------------------------------------------------------------}

FUNCTION PtInPolygon(const points:array of TPoint; N:integer; const p:TPoint):boolean;

var i:integer; angles:single;

//------------------------------------------------------------------------------

FUNCTION Angle(const p1,p2:TPoint):Extended;

var a2,b2,c2,cosa:single;

//--------------------------------------------------------------

begin

   a2:=Sqr(p2.x-p1.x)+Sqr(p2.y-p1.y);

   b2:=Sqr(p2.x-p.x)+Sqr(p2.y-p.y);

   c2:=Sqr(p1.x-p.x)+Sqr(p1.y-p.y);

   cosa:=(b2+c2-a2)/(2*Sqrt(b2)*Sqrt(c2));

   if cosa<=-1 then result:=pi

      else if cosa>=1 then result:=0

         else Result:=ArcCos(cosa);

end;

//------------------------------------------------------------------------------

begin

   result:=(n>2) and (n-1<=High(points));

   if not result then exit;

   for i:=0 to n-1 do if (p.x=points[i].x) and (p.y=points[i].y) then exit;

   angles:=Angle(points[n-1],points[0]);

   for i:=0 to n-2 do angles:=angles+Angle(points[i],points[i+1]);

   result:=Abs(angles-Pi*2)<0.00001;

end;

Dieses Thema wurde von "SirThornberry" von "Programmieren allgemein" nach "Open-Source" verschoben.