Geometrie-Aufgabe - Herangehensweise - Frage an die Mathematiker

[Thaxll'ssillyia]

Hallo Community,

ich sitze gerade an einer mir selbst gestellten Aufgabe rund um die 3-dimensionale Geometrie.

Gegeben:
- Eine beliebige Anzahl an unterschiedlichen Punkten im 3D-Raum
- Die Punkte bilden ein beliebiges geometrisches Objekt im Raum ab, Beispiele: bei 3 Punkten: 2D-Dreieck, bei 4 Punkten: ein windschiefes Teil oder eine 3-seitige Pyramide, bei 5 Punkten: 4-seitige Pyramide, bei 8 Punkten Würfel, Quader oder Pyramidenstumpf usw.
- Einzige Einschränkung: Die geometrischen Objekte haben keine "Vertiefungen", also keine negativen Ausbuchtungen (finde gerade keine besseren mathematischen Begriff)

Aufgabe: Ein (Pseudo-)Code bilden, um daraus folgende Struktur abzuleiten (Equivalent zu Klassen):
Ein Component (Modell als Ganzes) besteht aus X Panes (Außenseiten), welche wiederum aus X Punkten (Eckpunkten) besteht.

Beispiel:
- Bei 2D-Dreieck entsteht ein Component mit einem Pane, welches 3 Punkte hat.
- Bei 4-sitige Pyramide entsteht ein Component mit 5 Panes, wobei alle 3 Eckpunkte haben außer das "Bodenpanel" mit 4 Eckpunkten
- Bei 4-seitigen Pyramidenstumpf entsteht ein Component mit 6 Panes, welche jeweils 4 Eckpunkte haben.

Meine Idee (Pseudocode):

Iteriere jeden Punkt p {
- Liefere mir alle anderen Punkte
- Bilde zu jedem anderen Punkt einen Vektor v von Punkt p
- Bilde zu jedem gebildeten Vektor v eine Ebene e
Iteriere jede Ebene e {
Setze anderen Punkt in Ebene ein
Bilde aus der resultierenden Ebene ein Pane mit den entsprechenden Eckpunkten
}
}

Probleme:
Problem 1: Der Code würde mir nur Dreiecke liefern (es können aber auch 4- oder 5ecke sein)
Problem 2: Der Code liefert mir auch Dreiecke, die quer durch das Model gehen (ich brauche aber nur die Außenseiten)

Ansatzpunkt zur Problem 1: Ich müsste alle weiteren Punkte erneut einsetzen und prüfen, ob die auf der auch auf der 3-Punkt-Ebene liegen
Ansatzpunkt zu Problem 2: Ich bräuchte vorher eine Methode, um nur "angrenzende" Punkte, also Punkte, die von dem Ausgangspunkt "außen liegen" zu filtern

Vielleicht steh ich auch auf dem Schlauch und es gibt dafür viel einfachere Methoden? Danke für jeden Hinweis!

VG, Thax

 

[M1ch1]

Kann dir jetzt leider nur vage helfen.

Ähnliche probleme gibt es im bereich des rendering/raytracing. wenn es ein gröseres projekt von dir ist, lohnt es sich evtl in diesem bereich schlau zu machen. weil für mich klingt die aufabe jetzt nach etwas was bestimmt schon jemand in diesem bereich gelöst hat.

 

[dr_lupus_]

Klingt für mich, als ob du eine Seminar-/Abschlussarbeit von anderen gelöst haben möchtest.

 

[Thaxll'ssillyia]

Iwo. Ich brauch das für ein Programm was ich mir selber schreibe, um damit privat was mit Holz zu bauen. Da geb ich dann nur die Eckpunkte ein und bekomm den fertigen Bauplan (Maße, Winkel, etc.) für die Panele, die ich bauen muss.

Damit erspar ich mir die Arbeit, jeden Punkt anhand des Panels selber zu berechnen.

 

[MrFr33zer40k]

@dr_lupus
Klingt für mich, als ob du anderen gerne vorschnell falsches unterstellst.

 

[pmkrefeld]

Ich kann dir empfehlen das erst in 2D zu lösen, und die Lösung dann auf 3D zu erweitern.
Male einfach ein paar Punkte auf nem Blatt Papier samt Richtungsvektoren von jedem Punkt zu jedem weiteren.
In 2D muss jeder Punkt 2 Vektoren haben um mit einer Menge anderer Punkte eine Fläche zu bilden.
Es wird dann recht schnell ersichtlich, dass die 2 Vektoren die man behalten will die 2 mit der größten Differenz der Richtung zueinander sind (da ja keine 'Einbuchtungen' erlaubt sind')
So könntest du schon mal bestimmen wie sich die Punkte zu einer Fläche verbinden.
Ich glaube dass ließe sich ohne weiteres auf mehrdimensionale Strukturen erweitern.

Disclaimer: könnte auch völlig falsch liegen

 

[Kanibal]

Problem 2 klingt mir ganz so, als ob Du die konvexe Hülle deiner Punktmenge suchst. Algorithmen dazu findest Du hier: http://www.gm.fh-koeln.de/~hk/lehre/ala/ws0506/Praktikum/Projekt/C_lila/ConvexHull.pdf

 

[Thaxll'ssillyia]

Es wird dann recht schnell ersichtlich, dass die 2 Vektoren die man behalten will die 2 mit der größten Differenz der Richtung zueinander sind (da ja keine 'Einbuchtungen' erlaubt sind')
Ich glaube dass ließe sich ohne weiteres auf mehrdimensionale Strukturen erweitern.

Das klingt sehr logisch. Danke dir!

Problem 2 klingt mir ganz so, als ob Du die konvexe Hülle deiner Punktmenge suchst. Algorithmen dazu findest Du hier: http://www.gm.fh-koeln.de/~hk/lehre/ala/ws0506/Praktikum/Projekt/C_lila/ConvexHull.pdf

Ebenfalls Danke. Ich prüf mal, ob es in deinem Link eine ähnliche Lösung ist wie die von pkmrefeld.

 

[Thaxll'ssillyia]

Nun ja, es gibt Fortschritte (Abbildung zeigt eine 4-seitige Pyramide):

Leider ist der vorletzte Pfeil noch falsch, der müsste eigentlich zu dem untersten Punkt gehen. Ich filtere derzeit schon besuchte Punkte raus. Ich vermute, der von Kanibal verlinkte Artikel beachtet nicht, dass ich keine konkaven Stellen habe... Korrektur: Ich vermute ich hab was falsch implementiert...

 

[kuddlmuddl]

Ja klingt sehr nach konvexer hülle

Was du bei einfacheren algos sonst wahrscheinlich vergisst ist: viele punkte könnten bereits innerhalb einer größeren figur oder auf außenkanten liegen, die durch andere punktgruppen schon entstanden sind

Zb im extremfall: du hast extrem viele punkte die alle innerhalb eines würfels liegen. Die meisten punkte sind dann „innerhalb“ und daher komplett irrelevant für die außenflächen des Würfels

 

[blöderidiot]

Was spricht dagegen, die Abstände zwischen den Punkten nach der Länge zu sortieren und dann der Reihe nach die kürzesten Abstände so lange einzusetzen bis Dein gewünschter "konvexer Simplex" fertig ist?

 

[Thaxll'ssillyia]

So, nach ein paar Tagen probieren bin ich einfach mal auf die Idee gekommen zu schauen, ob es bereits dafür ein Framework gibt, und ja, z.B. MiConvexHull.

Klappt auch ziemlich gut, bis auf die Einschränkung, dass er maximal Dreiecke nutzt. Allerdings lässt sich das Problem einfach beheben, in dem ich jedes Dreieck durchgehe und schaue, ob da noch mehr Punkte auf der Ebene liegen, und dann einfach die Flächen ersetze.