Wieder mal ne Frage, die aus der Entstehung meiner GUI resultiert...
Diese soll auch nicht-rechteckige Kontrollelemente untersützen. Um festzustellen, ob ein Klick (o.ä.) in ein solches Polygon erfolgt ist, hatte ich vor diese zu Triangulieren und zu prüfen ob in eins der so entstandenen Dreiecke geklickt wurde.
Die Triangulation habe ich im Moment mittels Ear-Clipping implementiert, der Algorithmus funktioniert aber ja nur mit im Uhrzeigersinn angeordneten Punkten (und nebenbei wärs auch fürs Backface-Culling ganz nett, wenn die Punkte uhrzeigersinnig angeordnet wären). Meine Suche nach einem Algorithmus, um eine gegebene Punktmenge so zu sortieren, dass die Punkte im Uhrzeigersinn in einer Liste landen war allerdings bisher erfolglos. Gibts da was brauchbares?

Edit: hat sich gerade dann doch erledigt.

Suche Punkt mit tiefster y-Koordinate, wenn mehrere: Aus diesen den mit tiefster x-Koordinate.
Sortiere die anderen Punkte nach ihrem Winkel zu diesem Punkt, wenn mehrere gleiche Winkel: sortiere die Punkte mit gleichem Winkel nach ihrem Manhattan-Abstand.

Sollte so gehen, oder?

ich glaube, das geht nur für konvexe Polygone. Wenn deine GUI-Elemente alle konvex sind geht das also. Ansonsten musst du das Polygon so lange teilen, bis es nur noch aus mehreren konvexen Polygonen besteht. Diese testest du dann einzeln auf click und kannst diese auch einzeln sortieren. Ich gehe jetzt zumindest davon aus, dass das klappt, wenn ich nen Haken an der Sache finde meld ich mich nochmal.

_________________
Klar Soweit?

Kurz: Sellmann, du hast Recht.

Das Teilen funktioniert aber nicht. Das heißt, das Problem beginnt schon viel früher - ich habe keine Chance rauszufinden, ob mein Polygon konvex oder konkav ist. Grund: Mir ist die Konnektivität der Punkte nicht bekannt, also weiß ich nicht, welche drei Punkte gemeinsam eine Ecke bilden - und ohne diese Information kann ich den Winkel an der Ecke nicht bestimmen.

Ich hab mal ein Beispiel angehangen. Die Punkte hab ich da im Gegenuhrzeigersinn übergeben, damit die Triangulation funktioniert und man sieht, wies aussehen sollte.

Im Grunde genommen hab ich keine große Ahnung, wie ich das anstellen soll, ich weiß nichtmal, ob es überhaupt geht. Mein Ansatz momentan wäre, das Polygon zu finden, welches alle Punkte der Punktmenge enthält, und den geringsten Flächeninhalt aufweist.
Allerdings hab ich auch da keinen Schimmer, wie ein Algorithmus aussehen sollte, der dieses Polygon findet - und ob ich überhaupt das richtige Ergebnis kriege, oder da auch das rauskommt, was man im zweiten Screenshot sieht. (Das ist das Ergebnis der Triangulation, nachdem die Punkte mit dem Algorithmus aus dem ersten Post sortiert wurden).

Jemand ne Idee, oder das Wissen, dass die Sache aussichtslos ist, und ich die Punkte korrekt übergeben muss, damit das korrekte Ergebnis rauskommt?

Ok, was hast du genau gegeben? Wenn du nur die Punkte eines konkaven Polygons bekannt sind und diese nicht in sortierter Reihenfolge (*) vorliegen, dann ist es nicht möglich daraus das Polygon zu in Dreiecke zu zerlegen. Das liegt daran, dass es einfach nicht eindeutig ist. Wie du an deinen beiden Bildern sehen kannst, sind beides gültige Dreiecksnetze für die selbe Punktmenge. Das einzige was möglich wäre ist die konvexe Hülle zu generieren.

Also für ein konkaves Polygon brauchst du die Punkte und die Reihenfolge.

Desweiteren, es geht um Gui, also 2D , richtig? 3D wäre möglich, aber nur wenn alle Punkte des Polygons in der gleichen Ebene liegen. Ansonsten wäre das wieder nicht eindeutig.

Edit: (*) du musst wissen welcher Punkt mit welchem Punkt verbunden ist, also z.B. eine Angabe im Uhrzeigersinn oder eine Nachbarschaftsrelation.

_________________
Yeah!

Hm...okeh....sowas hatte ich befürchtet.
Also, das höchste der Gefühle wäre die konvexe Hülle, in der fehlt aber ja dann sozusagen der Punkt, der in meinem "Wunschpolygon" die konkave Ecke bildet, richtig?
Was ist denn, wenn ich danach das Programm nach der Möglichkeit suchen lasse, die den fehlenden Punkt unter einer bestimmten Prämisse in die Hülle integriert? Was mir spontan vorschwebt wäre zum Beispiel, dass das Polygon gesucht wird, welches ausgehend von der konvexen Hülle der Punktmenge alle darin nicht enthaltenen Punkte so integriert, dass der Umfang den geringsten Zuwachs erfährt...
Oder halt irgendwas in der Richtung.
Allerdings ist nicht gesagt, dass das immer zum gewünschten Ergebnis führt...irgendwann will ich mal ein konkaves Polygon, das nicht den minimalen Umfang besitzt und dann steh ich wieder auf dem Schlauch...
Wird wohl einfacher, die Punkte von vorn herein in der richtigen Reihenfolge zu übergeben

Edit: Ja, geht um 2D und um die andere Frage auch noch zu beantworten: Am liebsten wäre es mir, wenn ich nur die Punkte bräuchte, sonst nix.

Ja, wo kommen die Punkte den her?

_________________
Yeah!

Benutzereingabe. Klick in ein Panel -> Punkt mehr in der Liste.

Na dann ist es simple.
Der Nutzer muss die Reihenfolge einhalten. Fertig.
Entweder er macht es richtig, oder er muss es rückgängig machen und nochmal neu, oder du gibst ihm ein Tool, mit dem er die Reihenfolge anpassen kann.

Wenn du in 3DMax ein Poligon malst, machen die das auch so. Entweder du hälst dich an die Reihenfolge, oder du bekommst ein verhunztes Polygon. Selber schuld.

_________________
Blog: kevin-fleischer.de und fbaingermany.com

Gib dem Benutzer eine Linie die die eingegebenen Punkt verbindet. Also genauso wie das in jedem vernünftigen Grafikprogramm ist. Dann ist es ziemlich offensichtlich, dass man die Punkte in der richtigen Reihenfolge eingeben muss. Der Benutzer hat dann nur noch die Wahl zwischen Uhrzeigersinn und gegen den Uhrzeigersinn. Das dürfte aber kein Problem sein.

_________________
Yeah!