Suche nach einem geschickten Umweg

simsa

Hallo,

danke für Eure Antworten:

@knivil:
Ja, diese Rechnung habe ich auch gemacht; daher wollte ich das mit den
verschachtelten Schleifen irgendwie geschickt umgehen.

@SeppJ:
Genau, das ist nicht zum "brute forcen". Ja, den Anfangspunkt kann ich
festlegen; aber dann habe ich immernoch das Problem, die anderen N-1 Punkte
zufinden. Dein zweiter Punkt, die geometrisch theoretische Optimalform
vorzugeben hat ein hacken. Ich muss ja vorher die Eckpunkte kennen. D.h.
ich muss eine Tabelle haben, wo für alle N die Eckpunkte aufgelistet sind.
Dennoch wird es schwierig sein, weil meine Kugel ja nur 642 Punkte hat,
sprich es hat eine "roughness". Dein dritter Punkt ist gut, aber davor
muss ich ja die Eckpunkte gefunden haben, wo ich wieder beim zweiten Punkt wäre.

@Nirvash:
Dein Ansatz hört sich interessant an; leider habe ich es nicht ganz verstanden.

Ich hatte gestern Abend noch gegoogelt um näheres darüber zu finden und bin
dabei auf

http://en.wikipedia.org/wiki/Thomson_problem

gestoßen. Eigentlich ist es genau das, was ich suche bzw. möchte. Nur leider
sehe ich nicht ganz ein, wie es außer die verschachtelten N-Schleifen gehen
soll.

Wohlgemerkt, ich muss es mit meinen 642 Punkten machen und nicht mit irgend-
welchen "abstrakten" Punkten.

Beste Grüße,
simsa

Nirvash

Nimm für die kleineren Kugeln irgendein Schnittpunkt mit deinen vorgegebenen Punkten, welchen ist erstmal egal. Ab einem gewissen N müsste man dann aber Backtracken um ein N-Eck zu erzeugen.

Mit den Kugeln des Radius r_Basis/N wirst du mit hoher Wahrscheinlichkeit auch auf deine vorgegebenen Punkte kommen, da diese auf selbige Weise erzeugt wurden.

Lies dir mal diesen Artikel durch:
http://www.heise.de/developer/artikel/Geometrisches-Programmieren-leicht-gemacht-1867615.html

Dort wird beschrieben wie ähnliche Probleme gelöst werden können. Die Mathematik dahinter kannst du sicherlich nutzen, um dein Problem lösen und effizient in C umsetzen zu können.

simsa

Hallo Nirvash,

danke für den Link. Ich habe es gerade kurz überflogen.

Das passt nicht ganz zu meinem Problem.

Nehmen wir mal das Beispiel mit N = 4, bzw. dein Link mit dem Grill-Beispiel
und den vier Punkten:

Die vier Punkte ergeben einen Tetraeder.

Ich habe ja gesagt, dass meine Kugel 642 Punkte hat. Der Radius ist dabei
variabel. Wenn der Kugelradius r = 1 ist, dann sind die Seitenlängen des
Tetraeders ganz andere als wenn der Kugelradius r = 2 ist.

Daher meinte ich in meinen vorhergigen Post, dass ich es mit meinen 642
Punkten machen möchte und nicht mit irgendwelchen "abstrakten" Punkten.

Kennt jemand evtl. eine andere Methode?

Grüße,
simsa

Nirvash

Wenn der Radius variabel ist, sind deine Punkte nicht mehr gleichverteilt.

Kleine Ergänzung: Mir ist ein Fehler unterlaufen, was ich bisher als Radius der Schnittkugeln bezeichnet hab muss eigentlich der Durchmeser sein, also d=N/2, N/3 etc.

Nimm doch mal eine Kugel und lasse sie mit einer kleineren Kugel schneiden, das Ergebnis ist ein Kreis. Liegt der Mittelpunkt der kleineren Kugel auf der größeren Kugel, so ist der Abstand zweier gegenüberliegender Punkte im Schnittkreis gleich dem Durchmesser der kleineren Kugel.
Würdest du nun die kleinere Kugel erneut mit diesen beiden Kugeln schneiden, sodass der Mittelpunkt der neuen Kugel auf dem Schnittkreis liegt, entsteht ein neuer Schnittkreis. Verbindest du nun die gegenüberliegenden Punkte beider Schnittkreise, sodass der Schnittpunkt der zueinander entstehenden Gerade auf dem Punkt liegt, wo sich die beiden Schnittkreise treffen, hast du den größtmöglichsten Winkel für ein Vieleck mit der Kantenlänge des Durchmessers der Kugeln.

simsa

Wenn der Radius variabel ist, sind deine Punkte nicht mehr gleichverteilt.

Doch, sie sind dann immernoch gleichverteit. Wie kommst du darauf, dass sie nicht
mehr gleichverteilt sind?

Ich glaube, dass deine kleine und große Kugel sehr weit entfernt sind davon, was
ich suche.

Grüße,
simsa

Nirvash

Wie sind denn die Punkte auf der Kugel angeordent worden? Angenommen ich Habe eine Kugel vom Kreisumfang 10, möchte darauf 20 Punkte anordnet, dann muss zwischen jedem Punkt ein Abstand von der Kreisfläche (10/20)² * pi bestehen für eine gleichmäßige Verteilung aller Punkte über die Kugeloberfläche.

simsa

Meine 642 Punkte sind gleichmäßig auf der Kugeloberfläche verteilt bzw.
angeordnet.

Aus deinem Beispiel kannst Du aber auch sehen, dass der Radius der Kugel
oder des Kreises keine Rolle spielt.

Grüße,
simsa

Nirvash

Der Radius der innenkugel spielt auch keine Rolle. Du musst ja aber für deine Vielecke der Größe N mögliche Eckpunkte berechnen und das geht gut mit Schnittkugeln deren Radius abhängig von dem radius der großen Kugel und N ist.

Alternativ, was hälst du von folgendem Algorithmus:

Ausgangsprinzip:

Jede Fläche deines Vielecks ist ein gleichschenkliges Dreieck, die Seitenlänge S ist Abhängig von der Anzahl der Ecken und dem Radius der Kugel (je größer die Kugel ist, desto größer sind die Abstände zwischen deinen gegebenen Punkten bei gleichmäßiger Verteilung).

N=3 ergibt also eine dreieckige Fläche innerhalb der Kugel
N=4 ergibt einen Tetraeder mit 4 Seiten, jeweils 4 gleichschenklige Dreiecken
N=5 ergibt einen Oktaeder mit 8 Seiten, jeweils 8 gleichschenkligen Dreiecken

usw.

N=642 ein Vieleck mit 642 Ecken und X gleichschenkligen Dreiecken

Folgender Lösungsansatz:

Für jedes N derselbe Ausgangspunkt P.
Nun musst du von P aus den Punkt X suchen, welcher auf der Kugel liegt und dessen Abstand von P der Seitenlänge S entspricht.
Berechnen lässt sich dies Beispielweise über den Pythagoras mit a = S/2 und b = Abstand von P nach X.
An der Stelle musst du selbst mal überlegen, wie du den Wert für S am besten berechnest. Sobald du irgendein X gefunden hast (auf einer Kugel kommen mehrere in Frage) verfährst du genauso wie bisher, nur ist diesmal der neue Ausgangspunkt P = X. Dies wird solange durchgeführt bis alle Punkte des Vielecks der Größe N gefunden wurden.
Du wirst dir noch eine sinnvolle Reihenfolge überlegen müssen, wie du ohne Backtracking gewährleistet, dass der entstehende Körper auch geschlossen ist.

Denke dies sollte mit die einfachste Lösung sein.

simsa

gibt es dafür schon fertige C codes?

besten dank und einen schönen abend,
simsa

Nirvash

Denke mal nein, den Algorithmus wirst du selber Ausarbeiten und Implementieren müssen. Schließlich ist es ja deine Aufgabe