Ist ein Punkt in einem Polygon

[Amateurprofi]

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;

[EDatabaseError]

In dem angehängten Polygon erkennt er garkeinen Punkt der innen liegt.

Tobi

[Neutral General]

Zitat von Amateurprofi:

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.

Kann es sein das du da was überlesen hast EDatabaseError

Gruß
Neutral General

[Amateurprofi]

Zitat von EDatabaseError:

In dem angehängten Polygon erkennt er garkeinen Punkt der innen liegt.

Tobi

Also funktioniert das ganz ausgezeichnet.

Bei "Deiner" Figur handelt es sich um ein nichtkonvexes, überschlagendes Polygon, also um genau das Gegenteil eines konvexexn, nichtüberschlagenden Polygons. Im Begleittext steht aber unmißverständlich, daß die Prüffunktion nur für konvexe, nichtüberschlagende Polygone gedacht ist.

[JasonDX]

Geil sehr coole Idee, wie dus geloest hast
Nur eine ganz kleine Kleinigkeit zur Polygon-Bedingung: Ein konvexes Polygon kann sich IMHO nicht ueberschlagen, also koenntest du das theoretisch weglassen

greetz
Mike

[Gandalfus]

passent zum Thema:
http://blubplayer.de/tipppointinpolygon.html

ein Programm zum testen hab ich auch noch:
http://www.blubplayer.de/PointinPolygon.zip


Wie genau ist ein konvexes Polygon definiert?

[Amateurprofi]

Zitat von Gandalfus:

passent zum Thema:
http://blubplayer.de/tipppointinpolygon.html

Superschnell die Funktion.
Jedoch (wenn ich nicht grobe Fehler gemacht habe), leider nicht zuverlässig.

Die in anhängendem Bild rot markierten Punkte wurden nicht richtig erkannt.

Teilweise wird für Punkte außerhalb des Polygons True zurückgegeben, teilweise für Punkte innerhalb des Polygons false.

[Amateurprofi]

Zitat von JasonDX:

Geil :D sehr coole Idee, wie dus geloest hast :thumb:
Nur eine ganz kleine Kleinigkeit zur Polygon-Bedingung: Ein konvexes Polygon kann sich IMHO nicht ueberschlagen, also koenntest du das theoretisch weglassen ;)

greetz
Mike

Ja, dem könnte ich mich anschließen.
Aber sieh Dir mal anhängendes Bild an.
Die Angaben, welche Punkte zum Polygon gehören stehen daneben.

Weiß nicht wie Fachleute das sehen.....
Die äußere Begrenzung ist ein Quadrat, m.E. konvex.
Durch die Senkrechten innerhalb des Quadrates wird es zu einem überschlagenden Polygon.
Wir haben also ein konvexes überschlagendes Polygon.
Sicherlich sehr konstruiert....

[EDatabaseError]

Zitat von Neutral General:

Zitat von Amateurprofi:

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.

Kann es sein das du da was überlesen hast EDatabaseError

Gruß
Neutral General

kann ja mal vorkommen...