Probleme mit Polygonen

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
cime
User
Beiträge: 152
Registriert: Dienstag 24. Mai 2005, 15:49

Hallo,

ich habe ein großes (mathematisches) Problem:

ich habe eine Liste mit Punkten, die ein Polygon darstellt
BSP:

Code: Alles auswählen

>>> polygon = [p1,p2,p3,p4,p5]
die Punkte sind jeweils eine Liste aus zwei Elementen (dem X-Wert und dem Y-Wert)
BSP:

Code: Alles auswählen

>>> p = [12.6, 15.8]
nun habe ich noch einen einzelnen Punkt, bei dem ich feststellen möchte, ob er innerhalb oder außerhalb des Polygons liegt .... ich habe absolut keine sinnvolle Ahnung, könnt Ihr mir helfen???

mein einziger Ansatz ist ein Unterteilung des Polygons in Dreiecke (Prob: ich weiß nicht wie ich es korrekt in dreiecke unterteilen soll .... innerhalb von dreiecken den Punkt dann auszurechnen wäre aber keine Problem)

schon einmal ein Danke im voraus

mfg cime
chaos
User
Beiträge: 52
Registriert: Samstag 21. August 2004, 11:19

Mist, gerade hat mir ein Browserabsturz meinen Beitrag zerstörrt.

Also nochmal:
Ein Brute-Force ansatz wäre zu versuchen, den gewünschen Punkt als Konvexkombination der Eckpunkte darzustellen. Wenn das nicht geht, dann liegt er außerhalb.
Das hört sich aber ziemlich nach Brute-Force an und ist algorithmisch bestimmt nicht schön.

Mir ist dann noch etwas schöneres eingefallen:
Berechne die gerichteten Abstände zu jeder Seitenlinie. Gerichtet heißt, der Abstand bekommt das vorzeichen des inneren Normalenvektors. Ist ein Abstand negativ, so liegt der Punkt außerhalb.
Wie man auf das Vorzeichen des Normalenvektors kommen kann, kann man der angefügten Zeichnung entnehmen.

Bild

HTH
chaos
Slackware will never die.
mawe
Python-Forum Veteran
Beiträge: 1209
Registriert: Montag 29. September 2003, 17:18
Wohnort: Purkersdorf (bei Wien [Austria])

Hi!

Such mal nach "convex hull". Ich hab hier 2 Links für Dich:
1. Convex hull im Cookbook
2. Polygon (von jörg hier aus dem Forum, wenn ich mich nicht irre).

Gruß, mawe
Benutzeravatar
Rebecca
User
Beiträge: 1662
Registriert: Freitag 3. Februar 2006, 12:28
Wohnort: DN, Heimat: HB
Kontaktdaten:

Die Ansaetze von chaos und konvexe Huellen funktionieren aber nur fuer konvexe Polygone.

Eine google-Suche nach 'Punkt in Polynom' hat folgendes zutage gefoerdert:
http://rw7.de/ralf/inffaq/polygon.html :D

Wobei der Teil fuer konvexe Polygone so aehnlich wie der Ansatz von chaos ist.
chaos
User
Beiträge: 52
Registriert: Samstag 21. August 2004, 11:19

Ich bin von der mathematischen Definition eines Polyeders als Schnitt von Hyperebenen ausgegangen (bzw. das daraus induzierte Ungl.system).
Somit hatte ich Konvexität stillschweigend vorrausgesetzt
Slackware will never die.
cime
User
Beiträge: 152
Registriert: Dienstag 24. Mai 2005, 15:49

Ersteinmal ein ganz dolles dankeschön ...

genau soetwas wie http://rw7.de/ralf/inffaq/polygon.html habe ich gesucht ....

Leider versteh ich ich noch nichts von Vektoren ... (bin erst elfte Klasse, und da hatten wir das noch nicht ) aber trotzdem Danke, denn mit dem Trick auf der Seite von Rebecca klappt das ganze schön ....

PS: es war für beliebige sich nich schneidende Polygone gedacht ...

mfg
cime
Antworten