ich hatte gesucht aber nicht gefunden, deshalb etwas vorhandenes aus C in FPC übersetzt, welches ich gerne teile.
Die Quelle
https://web.archive.org/web/20130126163 ... usion.html
zeigt die Implementierung zweier Ansätze, des "crossing number algorithm" und des "winding number algorithm".
Ersterer ist die bekanntere Methode. Sie basiert auf der Überlegung, dass auf einer Geraden, die vom Testpunkt zu einem beliebigen, aber sicher außerhalb des Polygons liegenden Punkt führt, die Anzahl der Kreuzungen 0 oder gerade ist, wenn der Testpunkt außerhalb liegt, 1 oder ungerade ist, wenn er innerhalb liegt.
Die Methode hat ein Problem, wenn das Polygon deformiert ist und sich selber überlagert, dann liefert sie ggf. ein falsches Ergebnis.
Die zweitere Methode ist relativ frisch (2001), sie zählt die Windungszahl an den Grenzen des Polygons, allerdings nur deren Ergebnis, nämlich ob die Kante, die überschritten wird, nach "Oben" oder nach "Unten" führt. Heben sich die "Nach oben"-Kanten mit denen "Nach unten" auf, ist der Punkt außerhalb. Ist der Punkt innerhalb, so ist die Summe aus "Nach oben" und "Nach unten" ungleich null, kann aber bei deformierten Polygonen im Betrag auch größer als 1 werden.
Beide Algorithmen kommen ohne aufwendige Winkelberechnungen aus und sind entsprechend schnell.
Eine Erläuterung der Funktion findet sich in der englischsprachigen Wikipedia: https://en.wikipedia.org/wiki/Point_in_polygon
Es ist aber sehr sinnvoll zunächst an anderer Stelle, das das Polygon umgebende Rechteck zu bestimmen, damit lassen sich die Prüfungen für alle Punkte die außerhalb des Rechteckes liegen sehr stark verkürzen. Die ist insbesondere für komplexe und aus vielen Teilstücken bestehenden Polygone wichtig.
Die Lizenz für das Original ist Public Domain, dies gilt natürlich auch für die Übersetzung.
// This code may be freely used and modified for any purpose
// providing that this copyright notice is included with it.
// SoftSurfer makes no warranty for this code, and cannot be held
// liable for any real or imagined damage resulting from its use.
// Users of this code must verify correctness for their application.
Eine Anwendung sieht in etwa so aus:
Code: Alles auswählen
uses
(...)
uWnPnPoly;
(...)
procedure TForm1.Button1Click(Sender: TObject);
var
poly : array of Double;
rc : Integer;
b : Boolean;
ax,ay : Double;
s : String;
begin
SetLength(poly,5*2);
// X Y
poly[0] := 0.0; poly[1] := 0.0;
poly[2] := 10.0; poly[3] := 0.0;
poly[4] := 10.0; poly[5] := 10.0;
poly[6] := 0.0; poly[7] := 10.0;
poly[8] := 0.0; poly[9] := 0.0;
ax := 5.0;
ay := 5.0;
rc := WindingPointInPolygon(ax,ay,
poly[0],
Length(poly) div 2,
False);
b := CrossingNumberPointInPolygon(ax,ay,
poly[0],
Length(poly) div 2,
False);
if b then
s := 'Crossing result: Inside'
else
s := 'Crossing result: Outside';
Label1.Caption := Format('%s , WindingResult: %d',[s,rc]);
end;
Verein
Links
