Suche Punkt links von Polygon Test
-
Erstmals: Entschuldigung für den Doppelpost, aber meine Browser benötigt aus irgentwelchern Gründen sehr lange für den alten Thread zu öffnen. (IE 11, FF, Win7)
Folgendes Problem. Jester bat mich mein Problem zu formalisieren und so probiere ich es mal.
Gegeben ist ein offenes Polygon mit den kartesischen Punkten P := {P1, P2, …, Pn}, n > 3 in 3D.
Das Polygon hat keine doppelten Punkte d.h. für alle i,j e {1,.., n} gilt Pi != Pj. Insbesondere gilt P1 != Pn.
Das Polygon überkreuzt sich nicht selbst. Nur zwischen zwei benachbarten Linien existiert ein Schnittpunkt an dem Punkt wo sie sich berühren, d.h.
für alle i, j e {1, n-1}, j > i gilt: Existiert ein Schnittpunkt I zwischen der Strecke Pi, Pi+1 und der Strecke Pj, Pj+1, so gilt: j = i + 1 und I = Pj = Pi+1.Ferner können wir annehmen das P2, P1 und Pn-1,Pn sich nicht gegenseitig schneidende Halbgeraden mit den Startpunkten P2 bzw. Pn-1 darstellen.
Dadurch erhalten wir (hoffentlich) eine disjunkte Unterteilung des 2D Raums, in die Flächen A und B. Mit Hilfe des Polygon können wir einen repräsentativen
Punkt P in der Fläche A finden. Sei S hierzu die Strecke (P1, P2).1.) Initiale Konstruktion des Punkt P s.d. dessen Lotpunkt LP auf der Strecke S liegt.
2.) Linie L = LP + a * (P - LP).
3.) Bestimme alle Schnittpunkte zwischen dem Polygon und der Linie L in 2D.
4.) Existiert nur ein Schnittpunkt S und ist dieser exakt LP, haben wir unseren repräsentativen Punkt und können unsere Suche beenden.
5.) P = LP + 0.5 * (P - LP)
6.) Gehe zu 2.)Analog kann man die Seite B finden in dem man L = LP + a * (LP - P) annimmt.
Mein Problem:
Gegeben ist ein Punkt P. Liegt der Punkt nun in der Fläche A, Fläche B, oder auf dem Polygon?
-
Du hast nicht dein Problem mathematisch beschrieben sondern nur "triviale" Sachen. Zusammenfassung: Das Polygon ist einfach ( http://de.wikipedia.org/wiki/Polygon ) und in R^3 eingebettet.
offenes Polygon
Also doch kein kein Polygon sondern Streckenzug/Polygonzug?
disjunkte Unterteilung des 2D Raums
Ich dachte wir sind in 3D.
in die Flächen A und B ... Analog kann man die Seite B ... nun in der Fläche A, Fläche B
Was ist B nun.
Leider habe ich auch nicht verstanden was Flaeche A sein soll.
1.) Initiale Konstruktion ...
Hier faengst du an, einen Algorithmus zu beschreiben, obwohl das zu loesende Problem immernoch unklar ist. Dir wurde geraten:
Jester bat mich mein Problem zu formalisieren
Und eine Algorithmus ist eben kein Problemstellung.
Mein konkrete Frage ist, was ist Flaeche A/B. Desweiteren verstehe ich nicht, was links sein soll (nirgends in deiner Problembeschreibung erwaehnt, nur im Titel). Gewoehnlich gibt es nur innerhalb des Polygons und ausserhalb bezogen auf die Polygonebene. Fuer links und rechts bedarf es einer zusaetzlichen Gerade, die aber nicht viel mit dem Polygon zu tun hat.
Nach weiteren ueberlegen und unter Vorraussetzung, das P in der Polygonebene liegt:
1.) Punkt in Polygontest ist einfach. Siehe goolgle.
2.) Wenn der Punkt P nicht im Polygon liegt und rechts von (Pn-1, Pn) aber links von (Pn-2, Pn-1) und (P1, P2) liegt, dann liegt er links vom Polygonzug.
3.) Sonst liegt P rechts vom Polygonzug
-
Ok, zu meiner Verteidigung kann ich nur vorbringen das ich noch keine Vorlesung zu dem Thema gehört habe. Daher habe ich keine Ahnung was der Unterschied zwischen einem Polygon/Polygonzug/Streckenzug ist. Was ein einfaches Polygon ist, wusste ich auch nicht.
Ich habe vergessen zu erwähnen dass zwar die Punkte 3D sind, aber die Höheninformationen keine Rolle spielen und das Polygon immer in der XY Ebene liegt. Projiziert in die XY Ebene, hat das Polygon immer eine Fläche.
Beispiele zu meinem Problem:
P = [ (0, 0), (1, 0), (2,0) ], Halbgeraden (1,0)-(0,0) und (1,0)-(2,0) (Erster Punkt = Startpunkt)
Seite A entspricht alle Punkte mit einer Y Koordinate kleiner 0, Seite B alle Punkte mit einer Y Koordinate größer 0.Für den Punkt (1, 1) soll der Algorithmus Seite B auspucken, für Punkt (-1, 1) Seite A. Dein Vorschlag funktioniert da hier schon nicht. Erstes weil der Punkt in Polygon Test auf geschlossenen Polygonen arbeitet und zweitens weil du anhand von 5 Punkten entscheiden willst ob der Punkt in einer Seite liegt oder nicht.
Weiteres Beispiel:
P = [ (0, 0), (0, 1), (0,2) ], Halbgeraden (0,1)-(0,0) und (0,1)-(0,2)Seite A = Alle Punkte mit X > 0, Seite B = Alle Punkte mit X < 0
P = [ (0, 0), (1, 0), (1,1) ], Halbgeraden (1,0)-(0,0)) und (1,0)-(1,1))
Seite A = Alle Punkte mit Y > 0 und X < 1, Seite B = Alle Punkte mit X > 1 oder Y < 0
–-
Das mit Punkt links von Polygon war eine frühere Idee von mir. Für ein konvexes, geschlossenes Polygon kann ich bestimmen ob ein Punkt innerhalb des Polygon liegt, mit Hilfe des „Punkt-Links-von-Linie“ Test. Aber das brachte mich nicht weiter.
-
Kannst Du die Beispiele mal aufzeichnen? Ich bin mir nicht sicher ob ich Deine Notation verstehe, bei mir sieht das sehr merkwürdig aus...
Aber wenn ich Dich richtig verstehe hast Du folgendes:
- Einen einfachen Polygonzug von A nach B
- Eine Halbgerade a ab A und eine Halbgerade b ab B, sodass a und b sich weder gegenseitig noch eine der Kanten des Polygonzugs schneiden
So ein Gebilde, unterteilt in der Tat die Ebene in zwei Teile, wär also schonmal gut. Und du willst nun rausfinden ob Du rechts oder links davon liegst?