Suche nach einem geschickten Umweg

simsa

Guten Abend,

da mir in diesem Forum immer weiter geholfen wurde, hoffe ich, das jemand mir wieder helfen kann.

Mein Problem ist nun etwas geometrisch:

Ich habe auf einer Kugeloberfläche 642 Punkte. Diese Punkte sind annähernd gleichverteilt. Damit meine
ich, dass die Abstände zwischen benachbarten Punkten annähernd gleich groß ist.

Falls euch es interessiert; ich habe die Dreickesflächen eines Ikosaeders immer wieder geteilt…

Nun möchte ich N Punkte auf der Kugeloberfläche so wählen, dass der Abstand bzw. der Winkelabstand
am maximalsten ist; geometrisch kann man sich das Gebilde von N Punkten innerhalb der Kugel dann so
vorstellen: für

N = 2 wäre es eine Gerade
N = 3 wäre es ein Dreieck in der Null-Ebene
N = 4 wäre es ein Tetraeder
.
.
.
N = 12 wäre es ein Ikosaeder (wie man die Abstände bzw. die Winkelabstände ausrechnet, ist mir klar).
.
.
.

Mir ist klar, dass ich z.B. für N = 2 zwei verschachtelte, für N = 3 drei verschachtelte oder für N = 21
einundzwanzig verschachtelte Schleifen benötige.

Ich suche einen geschickten Weg, die mir für ein beliebiges N die entsprechenden Punkte rausfindet. Ich
möchte aber nicht den Umweg gehen, für die entsprechenden N’s die entsprechenden verschachtelten
Schleifen in einer Funktion zu schreiben.

Daher ist meine Frage: Wie kann man das Verschachteln geschick umgehen?

Hat jemand mit sowas Erfahrungen gehabt?

Vielen Dank und viele Grüße,
simsa

SeppJ

Beliebig verschachtelte Schleifentiefen kann man mit Rekursion lösen. Ganz einfach, indem die Rekursion eine Schleife ist, die sich bis zu gewünschten Tiefe selber aufruft.

Ich muss aber sagen, ich habe dein Problem nicht verstanden, deswegen kann ich nur obiges Stichwort als Lösung geben. Die N Punkte, die du suchst, sind das welche von den 642 Punkten? Wieso brauchst du verschachtelte Schleifen? Könntest du mal als Pseudocode schreiben, wie du dir die Fälle N=2, 3 und 4 vorstellst?

simsa

Hallo SeppJ,

Danke für Deine Antwort.
Ja, die N Punkte müssen aus der Menge der 642 Punkte sein.

ein minimal Beispiel für N = 2 wäre folgendes:

int pt1, pt2;
double dx = 0.0;

for(i=0; i<N; i++){
 for(j=0; j<N; j++){

  dcalc = distance(vector[i], vector[j]);

  if (dcalc > dx) {
   pt1 = i;
   pt2 = j;
  } 

 }
}

für N = 3:

int pt1, pt2, pt3;
double dx = 0.0;

for(i=0; i<N; i++){
 for(j=0; j<N; j++){
  for(k=0; k<N; k++){

   dcalc = distance(vector[i], vector[j], vector[k]);

   if (dcalc > dx) {
    pt1 = i;
    pt2 = j;
    pt3 = k;
   } 

  }
 }
}

Der Code ist jetzt nicht 100% sauber.

Wie sieht denn so ein beliebig verschachtelte Schleifentiefen rekursiv aus?

Viele Grüße,
simsa

knivil

Grobe Abschaetzung fuer N=12:

642^12 = 4*10^33

bei 3 GHz und 4 Kernen mit 1.2*10^10 getesteten Moeglichkeiten in der Sekunde ergiebt sich eine Rechenzeit von zehn Million Milliarden Jahren.

Grobe Abschaetzung fuer N=6:

67 Tage.

Grobe Abschaetzung fuer N=5:

2.5 Stunden.

SeppJ

knivil schrieb:

Grobe Abschaetzung fuer N=12:

642^12 = 4*10^33

bei 3 GHz und 4 Kernen mit 1.2*10^10 getesteten Moeglichkeiten in der Sekunde ergiebt sich eine Rechenzeit von zehn Million Milliarden Jahren.

Grobe Abschaetzung fuer N=6:

67 Tage.

Genau. Das ist kein Problem zum Brute Forcen. Zwei Ideen:
1. Da sind jede Menge Symmetrien drin, da deine Punkte auf einem regelmäßigen Gitter liegen. Du musst nicht alle Punkte ausprobieren. Allereinfachstes Beispiel ist der Anfangspunkt, den du einfach o.b.d.A. festlegen kannst.
2. Ganz was exotisches wird ja wohl nicht rauskommen. Du kannst die theoretische Optimalform (gleichseitges Dreieck, Tetraeder, usw.) vorgeben und dann an die jeweils nächst gelegenen Punkte springen. Vielleicht noch ein bisschen wackeln und alle Möglichkeiten zwischen den jeweils M nächsten Nachbarn der Optimalpunkte durchprobieren,, wobei M eine Zahl ist, dass die Anzahl der Kombinationen noch überschaubar ist.
3. Als Verfeinerung des 2. Verfahrens könnte man auch jeweils einen Eckpunkt variieren und gucken, ob es besser oder schlechter wird. Ich bin mir nicht sicher, ob das Maximum bei dieser Art von Problem eindeutig ist, aber gefühlt würde ich sagen, dass es keine lokalen Maxima geben sollte.

Nirvash

Wesentlich einfacher:

Für einen Kreis gilt jeweils vom Startpunkt ausgehend zum nächsten Punkt:

N=2: Hälfte aller Punkte liegen zum nächsten Punkt
N=3: Drittel aller Punkte liegen zum nächsten Punkt
N=4: Viertel aller Punkte liegen zum nächsten Punkt
.
.
.
bis du bei N=642 ankommst, da dann jeder Punkt in dem Vieleck ein Eckpunkt ist.

Daraus lässt sich auch eine Folgefunktion abbilden...diese für den Einheitskreis mit dem Limes ins positive Unendliche für N betrachtet ist eine Näherung für π...

Diesen Sachverhalt musst du nun auf eine Kugel über tragen. Die Logik wandert sich nicht, es kommt nur eine Dimension hinzu. Die n-tel sind nicht wie einem Kreis langen im 2-dimensionalen Raum, sondern langen im 3-dimensionalen.

Weiter kann dir die geometrische Algebra helfen:
Für N < 2 ergeben sich weitere mögliche Ausgangspunkte aus den Schnittpunkten der Basis Kugel mit einer Kugel vom Radius r_Basis/N

Für solche Probleme gibt es sogar eine eigene Programmiersprache. Hoffe die Ansätze könnendir weitrrhelfen. Auf die schnelle fällt mir nichts genaueres ein.

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