Smilebey - Di 27.03.07 14:33
Titel: Sortieren von TPoints für Polygon

---

Hallo,
wie der Titel schon sagt geht es um ein Sortieralgoritmus. Man hat z.B. den Points Array und man will die Punkte zu einem Polygon verbinden.
Die Verbindung der Punkte geht nach der Reihenfolge der Punkte im Points Array. Wie könnte man die Punkte sortieren?

ene - Mi 28.03.07 06:27

---

Hi,

was für Werte besitzen deine Punkte denn? Und was ist deine Absicht dabei? Bisschen knapp für eine Sortieralgorithmus.

Horst_H - Mi 28.03.07 06:58

---

Hallo,

Glaskugel an:
-Kürzeste Verbindung zu einem Polygon wäre das Problem des Handlungsreisenden (TSP TravellingSalesmanProblem)
( interessante Lösung http://www.ameisenalgorithmus.de/problem.htm )
-Konvexe Hülle, um alle Punkte einzuschliessen, dann wären aber nicht notwendigerweise alle Punkte im Polygon erfasst.
Glaskugel aus:

Gruß Horst

Spaceguide - Mi 28.03.07 07:59

---

Für konvexe Polygone: Graham Scan, ansonsten würde ich mal probieren, einfach die Winkel zum gewichteten Mittelpunkt des Polygons (z.B. Summe(Koordinaten(n))/n) zu berechnen und nach denen zu sortieren, wird aber nur suboptimale Ergebnisse bringen.

Smilebey - Mi 28.03.07 10:09

---

Also ich versuche es mal zu erklären.
Nehmen wir z.B. ein Dreieck mit den Koordinaten: (1,1), (5,3) und (2,5). Die Daten sind in einem "array of TPoints". OK, jetzt kommt ein Punkt dazu, nähmlich (3,2). Dieser Punkt ist nicht im Polygon (was ich mit einem anderen Algorithmus überprüfe). OK, weil der Punnkt (3,2) nicht im Polygon ist will ich ihn (in diesem Beispiel) als vierte Ecke haben, also aus dem Dreieck ein Viereck machen. Aber wenn ich den Punkt nur an die letzte Stelle des Array hinzufüge, zeichnet das Programm kein Viereck weil sich die Linien die die Punkte verbinden sich schneiden,
Also ich will die Punkte so sortieren dass es keine Überschneidungen gibt wenn ich die Punkte in der Reihenfolge des Array verbinde. Ich hoffe ich konnte es ein bisschen besser erklären.

ene - Mi 28.03.07 10:21

---

Dann würde ich vorneweg gern den Aufbau des Arrays kennen und woher man weiß, ob es sich um ein Dreieck oder Viereck handelt. Gibt es auch noch andere Polyeder? Vielleicht kann man das mit den Schnittpunkten ermitteln.

Gausi - Mi 28.03.07 18:13

---

Man muss ja eine Kante suchen, die man wegnimmt, damit dort eine neue Ecke entstehen kann. Man muss dabei eine Kante suchen, die von dem neuen Punkt aus komplett sichtbar sein muss. Dafür reicht es, die Sichtbarkeit der beiden Eckpunkte zu überprüfen.

Eine kurze Google-Suche nach Kanten, Polygon, Sichtbarkeit liefert z.B. http://www.geometrylab.de/polygon/RandomPolygon.html.de - das sieht für den Einstieg recht vielversprechend aus.