Besonderer Sortieralgorithmus gesucht!
-
Ich habe eine riesige Liste, in der Punkte in einem Raum gespeichert sind:
struct Punkt{ float x,y,z; }; // ... Punkt VielePunkte[12] = { {1.5f, 2.5f, 3.5f,}, // Erster Punkt {2.4f, -0.25f, 0.1f,}, // Zweiter Punkt {4.6f, -2.25f, -0.75f,}, // Dritter Punkt // usw. ... {1.2f, 3.8f, 0.75f,}};In dem Array sind also sehr viele Punkte gespeichert.
Jetzt sollen jeweils drei aufeinanderfolgende Punkte als ein Dreieck interpretiert werden.
Also die Punkte [0] bis [2], [3] bis [5], [6] bis [8] usw.
Und innerhalb eines solchen Dreiecks sollen jetzt die Punkte 'im Uhrzeigersinn' angeordnet werden. Das klingt also nach Sortieren.
Von den normalen bekannten Sortieralgorythmen kann aber, wie es scheint, keiner verwendet werden. Es bräuchte ja zumindest eine Definition einer 'kleiner / < ' - Relation, damit solche Sortieralgorythmen funktionieren.
Mir fällt auch leider keine Möglichkeit ein, unter welchen Umständen ein Punkt in einer 3-er Liste derartig zu einem anderen Punkt in Beziehung stehen könnte, damit sie vertauscht werden sollten.
Gibt es da eine allgemeine Regel, wie man aus drei gegebenen Punkten ableiten kann, ob sie 'im Uhrzeigersinn' gegeben sind oder nicht? (Irgendetwas mit Normalvektoren oder so?).Vielleicht ist das ja auch gar kein neues Sortierproblem, aber es lässt sich schwer danach googlen, deshalb hätte ich gehofft, dass ich hier ein paar Tipps bekommen könnte? Oder vielleicht kennt jemand eine Webseite, auf der es um dieses spezielle Sortierproblem geht?
Schon vorweg einmal danke für jegliche Hilfe!
-
Für sowas habe ich früher mal das Kreuzprodukt verwendet. Geht der Normalenvektor von zwei Punkten in die falsche Richtung, tauschst du Variablen. Wie und welche genau musst du dir aber selber herleiten
-
es wäre allerdings besser, wenn du die daten bereits in der korrekten reihenfolge liefern könntest. klingt mir so, als wolltest du die oberflächennormale der dreiecke bestimmen bzw. dafür automatisierte methoden von opengl o.ä. verwenden.
so von aussen draufgeguckt erscheint mir die stelle, an der die punkte erzeugt werden, der bessere ansatzpunkt für "sortierung".
-
und dann bist du fertig, schaust von der anderen seite auf die dreiecke, und die arbeit war umsonst, da dann alle ploetzlich gegen den urzeigersinn gehen... ich hoffe mein hint ist hilfreich;)
-
wieso umsonst? gehe eigentlich davon aus, dass "aussen" immer "aussen" bleiben soll und nicht abhängig vom viewpoint wechselt ^^