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
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… )
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
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 …
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 …
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
und Du
mußt nicht mehr unsinnige, alberne
Füllexperimente machen
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…
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 …
