Algorithmus für gleichmäßige Punkteverteilung auf Kreis?
Angenommen ich habe einen Kreis und möchte darauf n Punkte möglichst gleichmäßig verteilen, aber habe bereits m dieser Punkte an gewissen Stellen vorgegeben.
Was wäre ein Algorithmus, welcher nun die gleichmäßigste Verteilung berechnet, d.h. die Minimaldistanz zwischen zwei (nicht bereits festgelegten) Punkten maximiert.
Z.B. wäre ein Problem n = 10, m = 4:
Wäre auch froh über Code in beliebiger Sprache.
3 Antworten
Zuerst sollte man feststellen, vieviele Punkte in die Zwischenräume kommen. Seien
a, b, c und d die Längen (Winkel) der Zwischenräume.
Dann suchen wir den längsten, z.B. a, der bekommt jetzt die maximale Länge a/2. Im Gegensatz zu anderen Vorschlägen empfehle ich, die Teilung noch nicht auszuführen, denn wir wissen ja jetzt noch nicht, ob die optimale Anzahl der Punkte im Abschnitt a wirklich durch 2 teilbar ist.
Wir haben jetzt a/2, b, c, d
Jetzt wird wieder der längste gesucht. Wenn das a/2 ist, kommt der nächste Punkt auch ins Feld a und wir haben a/3, b, c, d.
Wenn stattdessen aber z.B. die Länge c die längste war, kommt der Punkt nach c und wir haben a/2, b, c/2, d.
Erst wenn wir alle Punkte auf die vier Abschnitte verteilt haben, führen wir die Teilung abschnittsweise wirklich durch.
Beispiel m = 2, n = 5:
Abschnitt 0 .. Pi Pi .. 2Pi
max. Länge Pi Pi
plaziert 1 0
max. Länge Pi/2 Pi
plaziert 1 1
max. Länge Pi/2 Pi/2
plaziert 2 1
max. Länge Pi/3 Pi/2
plaziert 2 2
max. Länge Pi/3 Pi/3
plaziert 3 2
max. Länge Pi/4 Pi/3
Also liegen die Ergebnispunkte
im ersten Abschnitt bei 0, Pi/4, Pi/2, 3Pi/4
und im zweiten Abschnitt bei Pi, Pi+Pi/3 und Pi+2Pi/3.
Du berechnest den Abstand der beiden Punkte jedes Segments in Grad (oder einer anderen Winkeleinheit) und sortierst die Segmente nach diesem Abstand absteigend.
Du wählst den Mittelpunkt des Segments mit dem größtem Abstand. es entstehen zwei Segmente mit der Hälfte des Abstands, die du in deine Liste passend einordnest. Zudem entsteht ein neuer Punkt, der den Abstand zu den anderen Punkten maximiert.
(Es würde sich vermutlich lohnen, die Punkte jeweils in Gruppen zusammenzufassen und den Abstand als Bruchteil des ursprünglichen anzugeben oder anderweitig den Speicherplatzverbrauch zu optimieren. Sonst wird dein Platzverbrauch linear größer.)
(Bzw. weißt du auch schon immer, wann die neuen Segmente erneut drann kommen werden. Du bearbeitest quasi immer in der selben reihenfolge die Originalsegmente bzw. dann später deren Kinder (mit Ausnahmen allerdings in der Anfangsphase, wenn die Kinder größer sind als andere Originalsegmente).)
Ah ja, ich sehe, was du meinst. Stimmt, an sich wäre es besser (und wohl auch effizienter) die Segmente herzunehmen und jeweils zu schauen, wie viele Punkte man da draufpacken kann.
Sollte aber an sich auch trivial sein Man muss im Grunde die Längen im Verhältnis zueinander betrachten und schauen, wie kurz die jeweils werden.
(Also ersteinmal füllt man die großen, bis die nur noch so viel Platz haben wie die kleinen (oder weniger). Man füllt also immer den größten so gut es geht.)
(Evtl. kann man das auch mit Linearer Programmierung lösen)
Ich kann nicht folgen. Wie evaluierst du, wie viele Punkte man draufpacken kann?
Wenn du jeweils in so viele Kreisabschnitte teilst, dass diese einzeln kleiner sind als der global größte, dann hättest du ja immer noch das Problem, dass du dich anfangs auf die Hälfte festlegst, oder?
Z.B. n=6, m=2 und Punkte bei 0 und π.
Hm, funktioniert so auch nicht. Versuch es mit Linearer Programmierung. (Hier ist das eigentlich ganzzahlige Programmierung, aber womöglich kann man das problemlos linear programmieren und dann eine lineare Anzahl an Randfällen betrachten.)
Du hast als Variablen die Anzahl der Punkte pro Segment, als Funktion, die es zu maximieren/minimieren gilt, eine Metrik, die die gleichmäßige Verteilung der Punkte wiederspiegelt (maximale Punktdichte oder soetwas).
Als Nebenbedingung hast du unter anderem eine, die die Gesamtzahl der Punkte beschreibt.
(Wobei das reichlich wenige Nebenbedingungen gibt, womöglich geht es doch einfacher und ich komme gerade nicht darauf.)
Vielleicht kann man es auch direkt so machen, dass man die Punkte nur auf die originalen Kreissegmente verteilt, jeweils auf das, auf dem nach dem Einfügen noch am meisten Abstand wäre.
Ich würde alle Zwischenräume betrachten,
und der größte bekommt in der Mitte einen Punkt.
Das dann wiederholen, bis alle Punkte verteilt sind.
Das ist ein vernünftiger Ansatz, allerdings wäre z.B. der Fall n=5, m=2 mit vorgegebenen Punkten bei 0 und π nicht optimal.
Danke. Auch hier gäbe es allerdings das gleiche Problem mit n=5, m=2 und Punkten bei 0 und π.
Speicher- oder Komplexitätsgrenzen habe ich im Grunde keine. Ich werde vermutlich nicht mehr als n=20 betrachten.