Autor Beitrag
C#
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 561
Erhaltene Danke: 65

Windows 10, Kubuntu, Android
Visual Studio 2017, C#, C++/CLI, C++/CX, C++, F#, R, Python
BeitragVerfasst: Fr 08.04.16 08:35 
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

_________________
Der längste Typ-Name im .NET-Framework ist: ListViewVirtualItemsSelectionRangeChangedEventHandler
Gammatester
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 328
Erhaltene Danke: 101



BeitragVerfasst: Fr 08.04.16 09:15 
user profile iconC# hat folgendes geschrieben Zum zitierten Posting springen:
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
ausblenden Quelltext
1:
2:
1 1
1 2
Wie sieht das zusammengefaßte Rechteck für die Klasse 1 aus?
C# Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 561
Erhaltene Danke: 65

Windows 10, Kubuntu, Android
Visual Studio 2017, C#, C++/CLI, C++/CX, C++, F#, R, Python
BeitragVerfasst: 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:
ausblenden Quelltext
1:
2:
3 3
1 2

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:
sample

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.
Einloggen, um Attachments anzusehen!
_________________
Der längste Typ-Name im .NET-Framework ist: ListViewVirtualItemsSelectionRangeChangedEventHandler
Ralf Jansen
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 4431
Erhaltene Danke: 906


VS2010 Pro, VS2012 Pro, VS2013 Pro, VS2015 Pro, Delphi 7 Pro
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1643
Erhaltene Danke: 236

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: 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
attachedImage

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
Einloggen, um Attachments anzusehen!
C# Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 561
Erhaltene Danke: 65

Windows 10, Kubuntu, Android
Visual Studio 2017, C#, C++/CLI, C++/CX, C++, F#, R, Python
BeitragVerfasst: 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:
sample2
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?
Einloggen, um Attachments anzusehen!
_________________
Der längste Typ-Name im .NET-Framework ist: ListViewVirtualItemsSelectionRangeChangedEventHandler
Ralf Jansen
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 4431
Erhaltene Danke: 906


VS2010 Pro, VS2012 Pro, VS2013 Pro, VS2015 Pro, Delphi 7 Pro
BeitragVerfasst: Fr 08.04.16 11:19 
Zitat:
Gibt es dazu eine effiziente Lösung?


stackoverflow.com/qu...-a-set-of-rectangles

Enthält einen Vorschlag und weiterführende Links

Für diesen Beitrag haben gedankt: C#, Horst_H
C# Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 561
Erhaltene Danke: 65

Windows 10, Kubuntu, Android
Visual Studio 2017, C#, C++/CLI, C++/CX, C++, F#, R, Python
BeitragVerfasst: 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.

_________________
Der längste Typ-Name im .NET-Framework ist: ListViewVirtualItemsSelectionRangeChangedEventHandler
C# Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 561
Erhaltene Danke: 65

Windows 10, Kubuntu, Android
Visual Studio 2017, C#, C++/CLI, C++/CX, C++, F#, R, Python
BeitragVerfasst: 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.

_________________
Der längste Typ-Name im .NET-Framework ist: ListViewVirtualItemsSelectionRangeChangedEventHandler
Blup
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 165
Erhaltene Danke: 42



BeitragVerfasst: 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