Servus miteinander,

um das leidige gleich voran zu stellen:
ich bin quasi absoluter Neuling im 3D Bereich ...

Ziel der Arbeit:
ich soll einen Farbraum darstellen.

In einer Look-Up Tabelle habe ich die Koordinaten der darstellbaren Farben.
Diese schaffe ich auszulesen und auch schön als Punkte darzustellen. Die Koordinaten innerhalb habe ich bereits entfernen können, sprich, es sind nur noch die Randpunkte zu sehen.

Diese Randpunkte sind folgendermaßen gespeichert:




L,a,b sind hier einfach die X,Y,Z Werte
über folgende Zeilen (funktioniert auch einwandfrei) werden diese in einem extre Fenster für die Darstellung ausgegeben.



Wo sich jetzt vermutlich erfahrene programmierer vor Lachen nicht mehr halten können ist nun folgendes Problem:
Ich habe die Punkte (die sich mit unterschiedlichen Lookup Tables immer ändern können) und möchte daraus ein zusammenhängendes Gebilde machen mit den Randkoordinaten als Eckpunkten (quasi ein riesiges Polygon).

Das Problem, welches sich mir derzeit aufdringt, ist dass diese Koordinaten ja nicht "geordnet" sind.
Die einzige Information ist, ob sie "Rand" sind oder eben nicht.

gibt es hierfür einen Befehl, dass sich aus den vorhandenen Koordinaten (X/Y/Z, allesamt Rand) ein Gebilde "macht"
oder gibt es hierfür einen brauchbaren Algorithmus (TSP - Travelling Salesman Problem - wäre wohl doch eher "mit Kanonen auf Spatzen schießen" )?

Liebe Grüße und Danke im Vorhinein,
Il Principe

PS: drehen/zoomen/Farbe etc. funktioniert dank der Tutorials schon BLENDEND - Danke an dieser Stelle für das bereitstellen dieser

Da irrst du dich, so einfach ist es nicht, aus einer Punktewolke ein Mesh zu basteln. Eine Methode ist diese hier:
http://de.wikipedia.org/wiki/Delaunay-Triangulation

Eine näherung könnte sein, dass man einfach die Entfernung eines Punktes zu den anderen berechnet, und die Punkte die am Nächsten Sind dann verbindet. Ist aber denk ich nicht wirklich korrekt. Bei gebogenen Oberflächen scheitert es garantiert, und bei gerade Flächen könnten trotzdem Löcher bleiben. Alles in allem nicht so toll... da bleibt wohl nur die Fachliteratur.

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

eine konvexe Hülle in 2D zu berechnen(nur wenn die Punkte in einer Ebene liegen macht der Ansatz ein Polygon durch die Randpunkte zu legen überhaupt Sinn) dürfte nicht schwer sein. Hab jetzt gerade nicht die Zeit nen algo zu posten, aber in O(N^2) lässt sich da was mit geringstem positiven Winkel zwischen verbindung letzer-aktueller Punkt und aktueller Punkt-nächster Punkt machen.

_________________

In 2D ginge das so:
- Gegeben: Eine Menge von 2D-Punkten
- Gesucht: Kleinstmögliches Polygon, was alle Punkte einschließt
- Zwei Mengen bilden: Berechnet und unberechnet. Am Anfang ist die erste leer, die zweite beinhaltet alle Punkte.
- Punkt mit der kleinsten y-Koordinate bestimmen. Wenn es mehrere gibt, den mit der kleinsten y- und x-Koordinate nehmen.
*- Bestimme für alle Punkte aus "unberechnet" den Winkel zwischen der zuletzt gezeichneten Linie und der Verbindung zwischen dem letzten gefundenen Punkt und dem zu testenden. Beim Anfangspunkt wird dazu die x-Achse benutzt.
- Den Punkt mit dem kleinsten Winkel in "Berechnet" hinzufügen.
- Ab * Wiederholen, bis der Punkt mit dem kleinsten Winkel der Startpunkt ist.

Ja genau den algo den Alibi beschreiben hat meinte ich. Leider ist er O(n^2). Mir ist jedoch gerade noch eine bessere Lösung eingefallen.
1. Wähle eine beliebigen Punkt A der echt innerhalb des Polygons liegt
2. Für alle Randpunkte P:
berechne den Winkel zwischen P-A und einer beliebigen Achse also z.B. arctan2(p.y-a.y,p.x-a.x)
3. Sortiere nach dem Winkel

Hinweis zu arctan2:
man übergebiebt der funktion y,x nicht umgekehrt
für y=0 funktioniert sie nicht(division durch 0)

_________________

Ist der nicht eher O(n*log(n)), da aus der Menge "Unberechnet" immer welche rausgeschmissen werden?
Bzw. dürfte das im Idealfall, wenn alle Punkte zur konvexen Hülle gehören, O(n*log(n)) sein und im Worstcase sich an O(n^2) sein...

Selbst wenn alle Punkte aus der Hülle liegen ist der 1. Algo O(n^2)
Beim 1. Durchlauf muss man n-1 punkte probieren
Beim 2. Durchlauf muss man n-2 punkte probieren
...
was etwa 0.5*n^2 also O(n^2) ist

Der 2. Algo dürfte O(n*log n) haben, wegen der sortierung. Allerdings funktioniert er in der geposteten Form nur, wenn alle Punkte am Rand liegen und ein konvexes Vieleck bilden.

_________________

Öhm, vielleicht kannst Du das brauchen:
1. http://wiki.delphigl.com/index.php/Tesselierung
2. http://wiki.delphigl.com/index.php/gluNewTess

soll heißen schau mal, ob Du den gluTesselator gebrauchen kannst
Traude