-         

Ergebnis 1 bis 7 von 7

Thema: Flächen und Punkte

  1. #1
    Erfahrener Benutzer Robotik Einstein Avatar von Geistesblitz
    Registriert seit
    16.03.2011
    Ort
    Dresden
    Alter
    30
    Beiträge
    1.937

    Flächen und Punkte

    Anzeige

    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?

  2. #2
    Erfahrener Benutzer Roboter Genie Avatar von BMS
    Registriert seit
    21.06.2006
    Ort
    TT,KA
    Alter
    26
    Beiträge
    1.192
    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

  3. #3
    Erfahrener Benutzer Robotik Einstein Avatar von Geistesblitz
    Registriert seit
    16.03.2011
    Ort
    Dresden
    Alter
    30
    Beiträge
    1.937
    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?

  4. #4
    Erfahrener Benutzer Roboter Genie Avatar von BMS
    Registriert seit
    21.06.2006
    Ort
    TT,KA
    Alter
    26
    Beiträge
    1.192
    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.ä.?

  5. #5
    Erfahrener Benutzer Robotik Einstein Avatar von Geistesblitz
    Registriert seit
    16.03.2011
    Ort
    Dresden
    Alter
    30
    Beiträge
    1.937
    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.

  6. #6
    Erfahrener Benutzer Robotik Einstein Avatar von Geistesblitz
    Registriert seit
    16.03.2011
    Ort
    Dresden
    Alter
    30
    Beiträge
    1.937
    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.

  7. #7
    Erfahrener Benutzer Roboter Genie Avatar von BMS
    Registriert seit
    21.06.2006
    Ort
    TT,KA
    Alter
    26
    Beiträge
    1.192
    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.

Ähnliche Themen

  1. Schnitt 2er geraden, 2 punkte 2 winkel bekannt
    Von goara im Forum Software, Algorithmen und KI
    Antworten: 7
    Letzter Beitrag: 17.07.2008, 21:10
  2. relative Position zweier Punkte ermitteln
    Von julius12345 im Forum Sensoren / Sensorik
    Antworten: 14
    Letzter Beitrag: 21.12.2006, 00:49
  3. Sensor zum erkennen von Flächen
    Von grex im Forum Sensoren / Sensorik
    Antworten: 18
    Letzter Beitrag: 27.09.2005, 18:42
  4. Sensor für Schwarze Flächen
    Von kowolfgang im Forum Sensoren / Sensorik
    Antworten: 4
    Letzter Beitrag: 28.07.2005, 11:10

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •