Polygon Prüfung ob innerhalb geklickt wurde

[klausi1305]

Ich brauch mal nen Gedankenanstoss,

wie ist es möglich, in einen Bereich auf einer Canvas zu klicken und zu prüfen, ob innerhalb des N-Ecks geklickt wurde?

Ob in ein Dreieck oder Viereck geklickt wurde ist ja relativ simpel.........

Meine Idee wäre, vom "Klick Punkt" der Maus jeweils in min 3 Richtungen zu prüfen ob die Pixelfarbe der "Umrandungsfarbe" des Polygons entspricht...
Eine andere Idee wäre nen 2d Array of Boolean, sprich jede Koordinate innerhalb des Polygon ist true....ich halte das jedoch recht unschön....

oder ist es besser das Polygon als Objekt zu erzeugen....? (da fehlt mir der Ansatz)

[theo]

http://www.daniweb.com/software-develop ... e-polygon-

[wp_xyz]

Durch den Testpunkt P eine horizontale Gerade legen und z.b. nach rechts verfolgen. Die Schnittpunkte dieser Halbgeraden mit jeder Polygonkante ermitteln. Bei einer ungeraden Anzahl von Schnittpunkten ist der Punkt im, bei einer geraden Anzahl außerhalb des Polygons.
http://de.wikipedia.org/wiki/Punkt-in-P ... ach_Jordan

[klausi1305]

Mit was prüfe ich die "Überschreitung" der Grenze?....Farbe der Linie, Farber des Pixels

[Antrepolit]

Aus der Spiele-Entwicklung kenne ich das Verfahren, dass man zuerst prüft, ob die Maus innerhalb der Bounding-Box deines Polygons liegt, danach Prüft man die "Pixelfarbe" unter der Maus (bzw. ob unter der Maus ein Pixel des Polygons liegt, oder nicht). Das ist ein sehr schnelles Verfahren und kaum Rechenaufwendig.

[Scotty]

Wie wär's mit PtInRegion()? Die Suchmaschine deiner Wahl liefert Hinweise auf den Gebrauch.

[wp_xyz]

Mit was prüfe ich die "Überschreitung" der Grenze?

Du sprichst oben von "N-Eck", also hast du n Eckpunkte. Damit ist der Rand des Polygons definiert. "Pixelfarbe" o.ä. braucht man da nicht. In dem von theo zitierten Link ist sogar schon der Algorithmus in Pascal ausformuliert, schau's dir an.

[klausi1305]

Danke für die Links und Hilfen!!

[Frank Ranis]

Hallo,

schon mal an die Methode mit Hilfe von Dreieckflächen gedacht?

Ein N-Eck kann man leicht in Dreicke aufteilen.

Die Dreickflächen kann man nach Heron berechnen.
http://de.wikipedia.org/wiki/Satz_des_Heron

1) Und somit ist die Polygon-Gesamtfläche die Summe der Teildreicke des Polygons.

2) Wenn wir nun einen irgendwo einen Punkt haben, dann können wird von diesem Punkt aus wieder Teil-Dreicke mit den Eckpunkten des

Polygons bilden und deren Teilflächen nach Heron berechnen.

3) Nun prüfen, ob die Summe der Teil-Dreickflächen gleich der Gesamtfläche des Polygons ist, wenn ja ist der Punkt im Polygon.

4) ist die Summe der Teilflächen größer, dann ist der Punkt außerhalb des Polygons.

Das ganze funktioniert auch in der 3D-Welt, ohne darauf achten zu müßen wie das Polygon im Raum steht.
Für das Heronverfahren brauchen wir ja nur die Seiten-Längen der Dreiecke.

Gruß

Frank