Suche Punkt links von Polygon Test
-
Folgendes Problem:
Ich habe ein 2D Polygon, welches offen oder geschlossen sein kann, aber sich nicht selbst schneidet.
Das Polygon unterteilt den 2D Raum in zwei Teile. Und ich möchte nun für einen Punkt feststellen in welchem Teil sich der Punkt befindet.
Ist das Polygon geschlossen, gibt es ein Innen und ein Außen. Mittels eines „Punkt in Polygon“ Tests (Strahl-Test) kann man feststellen ob der Punkt innerhalb oder außerhalb ist.
Im offenen Fall habe ich aber nun ein Problem und ich finde da kein passenden Algorithmus. Ich überlege das Polygon in konvexe Teilpolygon zu zerlegen. Für jedes Teilpolygon kann ich anhand eines modifizierten „Links von Linie“ Tests die entsprechende Seite feststellen. Ist aber auch kompliziert...
Kennt jemand einen entsprechenden Test?
Kann mir auch jemand ein Buch zu Algorithmische Geometrie empfehlen?
-
Inwiefern zerlegt denn ein offenes Polygon die Ebene? Kannst du sauber definieren was du genau haben willst? Sonst wird dir wohl auch ein buch nur begrenzt helfen. Das "Drei-Mark-Buch" finde ich ganz gut: Computational Geometry | ISBN: 3540779736