Algorithmus um den freien Raum im Grid in Rechtecke einzuteilen
-
Müssen die Rechtecke disjunkt sein?
-
an sich schon, wobei ich gerne auch infos ueber ueberlappende rechtecke durchlese
-
Mein Tipp ist, dass das NP-schwer ist. In dem Fall könnte entweder ein Approximationsalgorithmus interessant sein, oder du verwendest eine Heuristik. Wenn du an einer exakten Lösung interessiert bist würd ichs mal mit nem ILP probieren.
-
Für den Fall disjunkter Rechtecke wird man mit "finding a minimum dissection/partition (cover für den nicht disjunkten Fall) of a rectangular region which may have holes" fündig, ein Problem, das wohl vor allem im VLSI-Design auftritt. Das Paper "Efficient Algorithms for Geometric Graph Search Problems" von Imai und Asano reduziert dieses Problem auf das Finden eines maximales Matchings in einem bipartiten Graphen (Edit: eigentlich das Finden einer maximalen stabilen Menge in einem bipartiten Graphen). Wenn man dieses Problem mit dem Netzwerksimplex löst, ist man wahrscheinlich auch in der Praxis richtig flott.
Edit: Der Cited-By-Abschnitt von http://epubs.siam.org/doi/abs/10.1137/0215033 ist eine wahre Fundgrube. Ohne mir das alles im Detail angesehen zu haben, spricht http://link.springer.com/article/10.1007%2FBF02189307 z.B. von einem O(n*sqrt(n)*log(n))-Algorithmus. Andere Paper gehen sogar auf dein Bildzerlegungsproblem genauer ein.
-
Ha, da lag ich daneben.
das letztgenannte paper erlaubt auch punktförmige löcher, ohne ausdehnung. Deswegen scheint der Algorithmus komplexer zu sein. Der vorliegende fall scheint sowas nicht zu haben. Ich würde mir dann lieber das zeug von imai und asano anschauen.
-
Ich hab zwar grad keinen Zugriff auf das Paper, aber ich glaub ich hab die grobe Idee verstanden: an jeder (konvexen)Ecke eines Hindernisses muß eine rechtecksgrenze verlaufen: horizontal oder vertikal oder beides. Wenn man sich jetzt an jeder solchen ecke entschieden hat liegt die anzahl der rechtecke schon fest.,an ziehtneinfach die entsprechenden segmente ein, bis man irgendwo anstößt. Wichtig ist, dass man sich mache segmente teilen kann und sie dann nur einmal zählen (wenn zwei ecken zum beispiel auf derselben horizontalen liegen). Allerdings klappt das nur, wenn kein anderes segment dazwischen das dann horizontal durchschneidet, daher der schnittgraph von horizontalen +vertikalen segmenten.
Grobes vorgehen:
-
erzeuge für jede konvexe hindernisecke das entsprechende horizontale und vertikale segment, identifiziere dabei identische segmente.
-
Betrachte diese als knoten eines graphen und füge kanten zwischen segmenten ein, die sich überschneiden.
-
Berechne dann maximum independent set (via vertex cover) und füge schließlich für die ecken, die noch kein segment bekommen haben greedy jeweils eines ein.
-
-
Jester: Fast
Das Paper argumentiert über konkave Ecken des Polygons, was aber in unserem Fall keinen Unterschied macht, weil die Grundfläche konvex ist. Aber die Segmentlinien im ersten Schritt werden nur jeweils zwischen konkaven Ecken gezogen. Wenn ich deine Formulierung richtig verstanden habe, willst du von jeder konkaven Ecke je eine horizontale und eine vertikale Segmentlinie ziehen. Das Finden der Segmentlinien sowie der dritte Schritt werden mit einem Sweep erledigt.
-
danke danke!
hab anhand der antworten auch meine keywords ergattert, um ein wenig mehr informationen darueber zu finden, z.B.:
"Rectangular Decomposition of Binary Images"
fand z.b.:
http://library.utia.cas.cz/separaty/2012/ZOI/suk-rectangular decomposition of binary images.pdfwas mir aber irgendwie zeigt (siehe abgedecktes vogelbild) z.b.:
Distance transformation decomposition (DTD) of the bird image (1306
blocks in total), (b) GBD decomposition (923 blocks in total)dabei schaut das bild mit den minimalen blocks ziemlich 'fancy' aus. an sich will ich einfach nur moeglichst wenige nodes traversen wenn ich von einer freien stelle an die naechste kommen moechte. ich dachte 'minimale anzahl blocke' ist da schon gut, aber wenn ihr euch das minimalbeispiel fuer den vogel anschaut, bin ich mir nicht so ganz sicher, ob ich im schnitt, beim weg von jedem punkt zu jedem anderen weniger nodes traversieren wuerde.
in einem anderen paper sah ich dass "minimal circumference", also die summe der umfaenge aller rechtecke minimiert werden sollte damit man das erreicht.
werde mal ein paar test programmer basteln.
-
Evtl. Kannst du eine quad-tree mäßig zerlegung bauen, indem du ein Hindernis aus der Mitte nimmst und dortnals erstes die Segmente einfügst, und dann den Rest rekursiv löst. Das dürfte für eine gewisse Balance sorgen.
-
Da du dich auf den Vogel beziehst: Geht es also eigentlich um glatte Konturen und keine Polygone? Was genau willst du denn minimieren? Den maximalen Abstand zwischen zwei Punkten? Den mittleren Abstand?