Punkt in Polygon

Danke für den Tipp. Das verfahren müsste
eigentlich funktionieren. Jetzt muss ich
nur zusehen, dass es von der Laufzeit her
nicht zu teuer wird.

Es ist leider vom Rechenaufwand recht aufwändig, da man ja pro Vertex des Polygons ein Skalarprodukt ausrechnen und den Arcus Cosinus nehmen muß.

Ich hab den Artikel übrigens online gefunden, bei Gamasutra.

http://www.gamasutra.com/features/20000210/lander_01…

Dort ist auch eine andere, schnellere aber auch viel kompliziertere Methode beschrieben, die auf dem Aufteilen in Quadranten basiert. Ich verwende diesen Algorithmus, bin aber zu faul, ihn zu beschreiben. Aber bei der obigen Adresse findest Du ihn ja auch. Damit dürfte Dein Problem wohl endgültig gelöst sein und Du mußt nicht mehr unsinnige, alberne Füllexperimente machen :wink:

–Mathias

Ich nehme einfach einen Algorithmus zum
Füllen von Polygonen und prüfe, ob einer
der Füllpunkte gleich meinem Punkt X ist.
Das Füllen von Polygonen klappt ja
anscheinend ganz gut …

Dazu brauchst Du aber einen Startpunkt, von dem Du schon weisst, dass er im Polygon liegt… :wink:)

Ich nehme einfach einen Algorithmus zum
Füllen von Polygonen und prüfe, ob einer
der Füllpunkte gleich meinem Punkt X ist.

naja, ich weiss nicht ob ich es richtig ruebergebracht habe.

ich dachte daran die ganze karte als grosses zweidimensionales array vorzuhalten, dessen elemente die indices der polygone enthalten, halt eine bitmap, mit polygonen in der farbe des betreffenden p. zur laufzeit pruefst du dann nur noch welchen farbwert das pixel[maouse.x][mouse.y] enthaelt.
zur erstellung koennte man auf schnelle grafikfunktionen zurueckgreifen.

vorraussetzung ist natuerlich, dass deine map zur laufzeit nicht dynamisch ist, und du mit dem speicher ein wenig rumurchen kannst

o.k. es klingt ein wenig nach bruteforce…

Hi Mathias :smile:

Danke dir nochmal. Mit dem Artikel hast du mir sehr weitergeholfen. Meines Erachtens funktioniert der Algorihtmus allerdings nur bei konvexen Polygonen. Aber dazu muss ich das Paper erstmal lesen …

cu Stefan.

Hi Dog :smile:

Das von dir vorgeschlagene Verfahren wird ohne Zweifel funktionieren. Aber es ist ein Zeitproblem. Ich habe mehrere 3D-Kuchendiagramme mit zusammen etwa 10000 Polygonen. Jedes 3D-Kuchendiagramm kann im Raum beliebig gedreht und verschoben werden. Wenn ich das Verfahren, so wie von dir vorgeschlagen implementiere, brauche ich einfach zu lange, um den Mausklick einem Polygon zuzuordnen …

Trotzdem „Danke“ …

cu Stefan.

Hi Mathias :smile:

Ich habe mir den Artikel jetzt mal genau durchgelesen. Der erste Algorithmus mit den 360 Grad ist viel zu aufwendig zu implementieren. Das dauert ja ewig. Es ist nicht nur das Skalarprodukt, die Wurzel und der Arcus-Cosinus. Bei nicht-konvexen Polygonen musst du noch eine Art „Sektorverwaltung“ einbauen …

Der zweite Algorihtmus hat dasselbe Problem, wie von mir ganz zu Anfang beschrieben: Sobald eine Vertikale oder Horizontale von Punkt X einen Eckpunkt des Polygons schneidet, versagt der Algorithmus jämmerlich. Außerdem ist er langsamer als der Standard-Algorithmus, in dem man nur eine Horizontale nach rechts zieht …

Damit dürfte Dein
Problem wohl endgültig gelöst sein

Nein, denn die gleichen Fehler bekomme ich mit meinem jetzigen Algorithmus auch, nur schneller :smile:

und Du
mußt nicht mehr unsinnige, alberne
Füllexperimente machen :wink:

Nunja, die scheinen wenigstens „robust“ zu sein …

cu Stefan.

Wie wäre es mit PtInRegion (Windows-API)?
Hi,
warum nimmst Du nicht die schon vorhandenen API-Funktionen „CreatePolygonRgn“ und „PtInRegion“? Stehen in der Win32 Hilfe…

Gruß Thomas

DANKE an alle

Hi :wink:

Ich wollte mich nur noch mal bei euch allen bedanken. Ich habe das Problem jetzt gelöst, dank eurer Hilfe …

cu Stefan.

Ich wollte mich nur noch mal bei euch
allen bedanken. Ich habe das Problem
jetzt gelöst, dank eurer Hilfe …

Neugierig, wie ich bin:
Wie denn nun eigentlich?

-)

Neugierig, wie ich bin:
Wie denn nun eigentlich?

Ich wüßte auf jeden Fall, wie ich es gelöst hätte und hab.

–Mathias

Hi Claudio :smile:

Ich habe mir eine Routine geschrieben, die prüft, ob ein Punkt in einem Dreieck liegt. Das geht sehr schnell und sehr effektiv.

Ein beliebiges Polygon zerlege ich dann in Dreiecke. Dazu habe ich einen effektiven Algorithmus gefunden, der normalerweise beim Füllen von Polygonen verwendet wird. Dieser Algorithmus kommt auch mit nicht-konvexen Polygonen klar.

Tja, wenn ich beides zusammenschiebe, habe ich meinen Punkt-In-Polygon-Checker. Er ist sehr schnell und vor allem arbeitet er zu 100% richtig …

Danke nochmal

cu Stefan.