Fläche - liegt der Punkt P(x,y) darin?

[simlei]

Hallo!
Ich suche eine Funktion (ideal wärs natürlich die existiert schon), mit welcher ich überprüfe, ob ein Punkt mit den Koordinaten x_p und y_p in einem Polygon liegt, welches durch seine Eckpunkte (sind in der richtigen Reihenfolge angegeben) definiert ist (also im Prinzip ist das Polygon derart definiert, dass ich es mit TCanvas.Polygon(arrayvonpunkten:TPoints) zeichnen könnte.
Nun habe ich schon viel versucht; durch ausprobieren (Polygon zeichnen und gucken, ob an der Position x_p, y_p ein schwarzer Punkt = Punkt des Polygons ist, geht nicht, da ja auf die Pixel gerundet wird und man nicht überprüfen kann ob sich an Picture.Pixels[x_p, y_p] ein Punkt des Polygons ist, da ja x_p und y_p real-variablen sind.
Also insgesamt eine Funktion, die idealerweise das Array von Punkten und die Koordinaten x_p und y_p hat und true oder false zurückliefert.

Für Antworten bin ich sehr dankbar!

[Luckie]

Wenn ein Punkt innerhalb einer begrenzen Fläche liegt, dann hat eine Gerade, die von dem Punkt ausgeht, ein eungerade Anzahl von Schnittpunken mit der Begrenzungslinie der Fläche. Liegt der Punkt ausserhalb, ist die Anzahl der Schnittpunkte 0 oder gerade. (Ich meine, das hätte ich mal so gelesen.)

[Hawkeye219]

Hallo,

eine sehr einfache Lösung könnte die Nutzung des Windows-API sein (ungetestet!):

Delphi-Quellcode:

function PtInPoly (const aPoly: array of TPoint;  x, y: Integer): Boolean;
  var lRgn: HRGN;
begin
  lRgn := CreatePolygonRgn(aPoly, Length(aPoly), WINDING);
  Result := PtInRegion(lRgn, x, y);
  DeleteObject(lRgn);
end;

Die Funktion CreatePolygonRgn soll allerdings bei einer großen Anzahl von Punkten ziemlich langsam sein. In diesem Fall wirst du auf andere Algorithmen zurückgreifen müssen.

Gruß Hawkeye

[simlei]

@ Luckie: Danke! Das ist natürlich mathematisch sehr elegant und einfach nachzuweisen; das zu programmieren ist dann sicher leicht :).

und @ Hawkeye: was leistet die Funktion CreatePolygonRgn und was ist der Typ HRGN? ein Datentyp, der Flächen oder Regionen beschreibt?
Jedenfalls: Vielen Dank, da es zu klappen scheint (2 Tests liefen i.o.)

[Nikolas]

Je nachdem für was du es brauchst, solltest du aber auch die Spezialfälle untersuchen:
Luckies Ansatz sagt, dass ein Punkt auf einer Linie im Polygon ist, ein Punkt auf einer Ecke aber nicht.

[Hawkeye219]

@simlei

Zitat:

Zitat von Win32 Programmer's Reference

In Microsoft Windows, a region is a rectangle, polygon, or ellipse (or a combination of two or more of these shapes) that can be filled, painted, inverted, framed, and used to perform hit testing (testing for the cursor location).

Am besten schaust du dir das Kapitel "Regions" in der Datei Win32.hlp an. Diese Hilfedatei liegt normalerweise im Verzeichnis "C:\Programme\Gemeinsame Dateien\Borland Shared\MS Help". Es ist zu viel Text, um ihn hier komplett zu posten.

Gruß Hawkeye

[simlei]

... and used to perform hit testing ...

ok alles klar - das ist ja genau das was ich suchte.