Flächen und Punkte

[Geistesblitz]

Ich habe derzeit ein Problem, das sich nur schwer lösen lässt:

Gegeben sei eine Fläche beliebiger Form, die in Pixeln diskretisiert ist. Bekannt sind von ihr Flächeninhalt und Flächenschwerpunkt.
Nun besteht die Aufgabe darin, eine vom Flächeninhalt abhängige Anzahl von gleichgroßen Kreisen in diese Fläche so zu legen, dass ihr gemeinsamer Schwerpunkt mit dem Schwerpunkt der Fläche zusammenfällt und dass sie möglichst gut über die Fläche verteilt sind. Sie sollten also nicht alle irgendwo in der Mitte oder dicht beieinander liegen. Das Problem sind dabei eben die vielen Freiheitsgrade. Das Ganze klingt für mich ein wenig nach Optimierungsproblem, allerdings kenn ich bisher nur Problemstellungen, wo ein Parameter optimiert werden soll, nicht gleich 8 oder so. Ich hatte schon den Einfall, dass man da vielleicht mit genetischen Algorithmen weiterkommen könnte, allerdings müsste ich mich da erst einarbeiten und die Berechnung würde wahrscheinlich auch zu lange dauern, um tauglich zu sein.
Wisst ihr da vielleicht einen Rat?

[BMS]

Hallo,
da würde ich auch mit einem Optimierungsalgorithmus ansetzen.
Die Anzahl der Kreise kannst du ja schonmal im voraus berechnen, das ist kein Problem.
Dann würde ich die Kreise erst mal zufällig in der Fläche verteilen.
Für einen Kreis wird dann eine neue (zufällige) Position berechnet.
Bei dem Zeitpunkt brauchst du eine Art Bewertungsfunktion, die dir sagt, wie gut die
neue Anordnung ist.
Für deine Anwendung müsstest du einerseits den neuen Schwerpunkt berechnen (dieser
soll dem eigentlichen Schwerpunkt sehr nahe kommen) und andererseits die Abstände
messen. Also z.B. die Summe aller Abstände der Kreise untereinander würde dann
Auskunft über die Verteilung geben.
Also ist die neue Anordnung um so besser, je näher der Schwerpunkt mit dem urspr.
berechneten kommt und je größer die Abstände zwischen den Kreisen sind.
Der Kreis wird dann z.B. nur an die neue Position verschoben, wenn die Bewertungsfunktion
sagt, dass die neue Lösung besser ist. Das wäre dann dem "Random Interchange" ähnlich.
Das muss natürlich sehr oft wiederholt werden, damit eine gute Lösung rauskommt.
(Das kann man auch noch zu einem "Simulated Annealing" umbauen, indem schlechtere Lösungen
auch zugelassen werden, aber mit einer Wahrscheinlichkeit, die stets abnimmt.)
Grüße,
Bernhard

[Geistesblitz]

Danke für die schnelle Antwort, das hört sich schonmal ähnlich an, wie es beim genetischen Algorithmus funktionieren würde.
Problem bei dem Kriterium mit den möglicht großen Abständen: die Kreise würden sich am äußersten Rand der Fläche tummeln, während im inneren Bereich tote Hose ist. Zumindest ist das meine Vermutung. Allerdings würde mir kein Kriterium einfallen, welches nur den Abstand zu den nächsten Kreisen berücksichtigt. Aber vielleicht ließe sich da mit dem Verhältnis Kreise/Fläche ein Maximalabstand bestimmen, in dem Kreise berücksichtigt werden und innerhalb diesem möglichst weit wegrücken sollen. Durch Beeinflussung der Bereiche gegenseitig könnten die Kreise dann eine gute Verteilung finden. Oder hab ich grad nen Knoten im Gehirn?

[BMS]

Man könnte natürlich auch einen Mindestabstand festlegen.
Dazu musst du aber alle Abstände berechnen,
d.h. von jedem Kreis zu jedem anderen Kreis.

EDIT: Eine weitere Überlegung: wie stellst du sicher, dass die
eingezeichneten Kreise auch vollständig in der Pixelform drin sind?

EDIT2: Vielleicht könntest du schon mit einfachen Formen anfangen.
Wie würde der Algorithmus z.B. 5 Punkte in einem Dreieck unterbringen o.ä.?

[Geistesblitz]

Ich dachte daran, dass man die Kreise ebenfalls verpixelt und dann überprüft, ob die Fläche des Kreises "leere Pixel" überdeckt, also über den Rand steht. Ist das der Fall, wird stattdessen ein neuer Kreis generiert, der, wieder überprüft wird...
Man könnte ja die Kreise in einer Normalverteilung um den Schwerpunkt generieren, bis die gewünschte Anzahl erreicht ist, deren Positionen dann danach angepasst werden. Allerdings wird es schwierig, zu bestimmen, was passieren soll, wenn der Kreis nach dem Verschieben nicht mehr in der Fläche ist.

[Geistesblitz]

So ich bin jetzt bei der Überlegung angelangt, dass erstmal alle Kreise zufällig normalverteilt auf der Fläche generiert werden. Danach werden die Abstände, die alle Kreise in einem Maximalabstand um einen Kreis haben, herangezogen, um eine Art abstoßende Kraft auf den betreffenden Kreis auszuüben. So, als wenn sich alle Kreise abstoßen würden. Dazu würde dann die Resultierende der reziproken Abstände gebildet werden, wenn also die Kreise näher beieinander sind, desto stärker wirkt die Abstoßung. Das Ganze müsste dann noch so skaliert werden, dass die Kreise nicht sofort aus der Fläche fliegen. Mit jedem Iterationsschritt entfernen sich die Kreise also voneinander. Wenn ein Kreis den Rand der Fläche teilweise überschreitet, dann wird aus den überstehenden Pixeln der Schwerpunkt dieser Fläche gebildet und mit dem Vektor Schwerpunkt Überstandsfläche -> Mitte Kreis eine Gegenkraft gelegt, die dann vll. abhängig vom Flächeninhalt der Überstandsfläche ist, mal sehen. Somit dürften die Kreise sich schön verteilen. Ob dann die Überschneidung der Schwerpunkte gegeben ist, kann man dann aber höchstens überprüfen, jedoch kaum beeinflussen.

Gibt es eigentlich irgendwie eine Funktion, mit dem man den Rand einer Fläche in genau x Pixeln Abstand "abschneiden" kann? Dann ließe sich nämlich anstelle der Kreise mit Punkten arbeiten.

[BMS]

Gibt es eigentlich irgendwie eine Funktion, mit dem man den Rand einer Fläche in genau x Pixeln Abstand "abschneiden" kann? Dann ließe sich nämlich anstelle der Kreise mit Punkten arbeiten.
Könntest den Umriss der Fläche über Kantenerkennung ("welche Pixel der Fläche liegen direkt neben Hintergrundfarbe?") erstellen und
dann alle Kantenpixel löschen. Mit jedem Ausführen wird von der Fläche dann am Rand überall 1 Pixel weggenommen.