C# - Fr 08.04.16 08:35
Titel: Algorithmus zum Zusammenfassen von Rechtecken

---

Hey Leute,

Ich bin momentan auf der Suche nach einem Algorithmus der Rechtecke anhand ihres Ortes und ihrer Größe zusammenfasst.
Stellt euch vor ich habe ein Grid das in gleich große Rechtecke unterteilt ist. Jedes Rechteck ist in einer von drei Klassen eingeteilt. Ich möchte nun benachbarte Rechtecke der gleichen Klasse zusammenfassen, sodass diese Zusammenfassung wieder ein Rechteck ergibt.
In Sachen Effizienz ist der mit Abstand wichtigste Faktor, dass Punktabfragen möglichst schnell ablaufen. Sprich: ich frage ab, in welcher Klasse ein beliebiger Punkt auf dem Grid liegt. Welches Rechteck es letztendlich ist, ist nicht wichtig. Nur die Klasse des Rechtecks.

Wenn jemand eine bessere Idee hat, immer her damit ein Flag Array ist keine Option, da der zu prüfende Bereich zu groß ist (ca. 30000×30000).

Es wird nicht mit Gleitkomma gearbeitet. Der kleinste Abstand im Grid ist 1 -> Int32Rect

Gammatester - Fr 08.04.16 09:15

---

C# hat folgendes geschrieben :

Ich möchte nun benachbarte Rechtecke der gleichen Klasse zusammenfassen, sodass diese Zusammenfassung wieder ein Rechteck ergibt.

Keine Ahnung, was das überhaupt bedeuten soll (unabhängig von der Implementation in irgendeiner Sprache). Beispiel: Du hast ein Quadrat durch Halbieren der Seiten in vier Quadrate geteilt, drei gehören zur Klasse 1, eins zur Klasse 2. Etwa so
Wie sieht das zusammengefaßte Rechteck für die Klasse 1 aus?

C# - Fr 08.04.16 09:30

---

Zitat:

Wie sieht das zusammengefaßte Rechteck für die Klasse 1 aus?

in diesem Fall würde es so aussehen:

Wobei 3 die Zusammenfassung darstellt.

Ich habe mich etwas unverständlich ausgedrückt. Deshalb habe ich jetzt nochmal ein Bild dass mein bisheriges Ergebnis anzeigt:


Ich hoffe jetzt ist klar was ich vorhabe. Die Rechtecke sind nicht sehr effizient eingeteilt. Ich suche einen Algorithmus, der diese effizienter einteilt, um so ihre Gesamtanzahl zu minimieren.

Ralf Jansen - Fr 08.04.16 09:52

---

Wenn das im Umfeld von Klassen aus dem System.Drawing Namespace stattfindet frag ich mal warum es Rechtecke sein sollen. Enie Region aus System.Drawing muß nicht rechteckig sein und kann man befragen ob Koordinaten treffen würden. Wenn du 3 unterscheidbare Bereiche hast wären das für mich einfach 3 Region(s) die mal einzeln befragen kann ob sie getroffen wurden.

Dazu wie gut das skaliert/performt wage ich aber keine Aussage.

Horst_H - Fr 08.04.16 10:01

---

Hallo

das ist doch ein Optimierungsproblem.Wie belege ich ein Gebiet mit möglichst wenig rechteckigen Teilen.
momentan erzeugst Du doch sicher eine Liste der äusseren Quadrate eines Gebietes gleicher Klasse und sortierst diese nach x,y , bei gleichem x nach y sortieren.
Damit hast Du ein senkrechtes Streifenmuster.Dann suchst links oder rechts davon gleich große Streifen, die zu einem breiteren Rechteck zusammengefasst werden.
Das geht auch mit nach y und dann nach x sortiert.
Aber Du willst es noch optimierter haben.Vielleicht mehr so, nur so aus der la Mäng


Ich würde versuchen ein möglistes grosses Rechteck heraus zu finden und und dieses zu entfernen und die Restgebiete rekursiv ähnlich zu behandeln.
Aber das scheint mir nicht unbedingt ein optimales Ergebnis zu liefern.

Nun ja, wie war denn Dein Ansatz bisher

Gruß Horst

C# - Fr 08.04.16 10:32

---

@Ralf
Ich habe die Performance von Regions nicht getestet und weiß auch nicht wie geprüft wird, ob ein Punkt in der Region liegt. Falls Polygon Raycasting oder Ähnliches benutzt wird, muss für jede Abfrage jeder Punkt des Polygons untersucht werden, was bei mehreren Hundertausend Anfragen pro Sekunde doch ganz schön auf die Performance schlägt. Ein Quadtree wäre auch eine mögliche Lösung, da sich der in O(log n) durchsuchen lässt.

@Horst_H
Ich mache es bis jetzt so wie du es geschildert hast. Ich sortiere die Rechtecke nach X und Y Koordinaten und starte in der linken, oberen Ecke:

Zuerst prüfe ich, ob ich das Rechteck nach rechts erweitern kann. Anschließend prüfe ich, ob ich das neue (evtl nach rechts vergrößerte) Rechteck nach unten vergrößern kann. Sobald in keine Richtung erweitert werden kann, wird das Rechteck rausgeschnitten und die Suche beginnt von vorne. Der bereits untersuchte Bereich wird bei den Folgenden Suchen dann ignoriert.

Zitat:

Wie belege ich ein Gebiet mit möglichst wenig rechteckigen Teilen.

Genau das ist mein Problem :D. Gibt es dazu eine effiziente Lösung?

Ralf Jansen - Fr 08.04.16 11:19

---

Zitat:

Gibt es dazu eine effiziente Lösung?

http://stackoverflow.com/questions/5919298/algorithm-for-finding-the-fewest-rectangles-to-cover-a-set-of-rectangles

Enthält einen Vorschlag und weiterführende Links

C# - Fr 08.04.16 12:14

---

Sehr geil. Danke dir.

Wenn ich Resultate habe, melde ich mich nochmal. Kann aber ne Weile dauern, da dieses Problem momentan nicht oberste Priorität hat.

C# - Sa 09.04.16 10:27

---

Hallo,

Also meine Anforderungen haben sich jetzt etwas geändert. Ich muss jetzt nur aus den kleinen Quadraten ein umschließendes Polygon bestimmen. Mein Problem ist aber, dass das Raster mehrere Gruppen einer Klasse beinhaltet und folglich mehrere Polygone enthält.
Ich weiß nicht wie ich die Polygone erstellen soll. Theoretisch müsste ich ja an einem Quadrat beginnen und über die Eckpunkte wandern. Ich bin mir nur nicht sicher wie ich das sauber implementieren soll.

Kennt jemand ein gutes Sample? Falls es ein besseres Verfahren gibt immer her damit. Löcher im Polygon müssen nicht erkannt werden.

Blup - Mo 30.05.16 09:56

---

Hallo, mein Vorschlag:

Liste(A) mit Rechtecken aller Typen
1. Daraus Liste(B) mit Rechtecken eines Types erstellen.
2. Ein Rechteck der Liste(B) entnehmen und per Floodfill-Algo alle Rechtecke aus Liste(B) finden, die zum selben Bereich gehören. Diese Rechtecke aus Liste(B) entfernen und in Liste(C) speichern.
3. Liste(C) verarbeiten um das Polygon zu erzeugen.
4. Wenn Liste(B) nicht leer, ab Punkt(2) wiederholen.
5. Wenn weitere Typen, ab Punkt(1) wiederholen