Überschneidung von Rechtecken

[Ulrich Bosch]

Hallo zusammen,

eigentlich ist das Thema hier nicht ganz richtig, aber es hat doch auch etwas mit digitaler Bildverarbeitung zu tun:

Ich habe eine Liste mit beliebig vielen Rechtecken, von denen ich die Koordinaten aller Eckpunkte kenne. Ich muss nun überprüfen, ob sich eventuell Rechtecke überschneiden. Gibt es einen schnelleren Algorithmus, als dies von Fall zu Fall über den Mittelpunkt und die Ausdehnung der Rechtecke zu entscheiden?

Mit besten Grüßen

Uli

[Jochen Reichenberg]

Hallo Uli,

schau mal hier: <a href="/webx?13@@.1dd055e5/2">Ulrich Gerhardt "Kreuzungspunkte zweier Linien" 29.08.2003 17:34</a>

Da Rechtecke nur aus Linien bestehen... Ob das schneller müßte man ausprobieren.

Grüße Joche

[Ulrich Bosch]

Hi Jochen,

den Lösungsansatz hatte ich auch angedacht, aber er ist sicherlich langsamer als der über Mittelpunkt und Ausdehnung der einzelnen Rechtecke.

Viele Grüße

Ul

[Ulrich Bosch]

Hi zusammen,

was ich noch dazu sagen sollte: alle Rechtecke stehen waagerecht oder senkrecht auf der Grundachse. Das vereinfacht die Sache mit Mittelpunkt und Ausdehnung natürlich erheblich.

Gruss

Ul

[Jochen Reichenberg]

Hallo nochmal,

dann müßte doch eigentlich ein Sortierung nach Start und Endpunkt der Linien, die auf der Grundachse liegen und ein Vergleich der Punkte zueinander ein recht schnelles Ergebnis liefern. Sprich alle Rechtecke, deren Start oder Endpunkte zwischen Start oder Endpunkten anderer Rechtecke liegen, überlagern sich.

Mußt Du für alle Rechtecke wissen, von welchen anderen Rechtecken sie überlagert werden, oder reicht es festzustellen, daß sie überlagert werden?

Grüße Joche

[Ulrich Bosch]

Hallo Jochen,

ich hatte mich nicht ganz glücklich ausgedrückt: die Rechtecke stehen nicht senkrecht oder waagerecht <B>auf</B>, sondern <B>zur</B> Grundachse. Zu Deiner Frage, ja ich muss wissen, bei welchen Rechtecken Überschneidungen vorkommen.

Ul

[Jochen Reichenberg]

Hallo Ulrich,

ich würde die vier Eckpunkte der Rechtecke ermitteln, nach diesen sortieren und für jeden Punkt prüfen, ob er zwischen dem Startpunkten der anderen Rechtecke (x- und y-Achse) liegt. Sobald das erste Rechteck gefunden wird, das sich nicht mehr mit dem zu prüfenden Rechteck überschneidet, brauchst Du die folgenden nicht mehr zu überprüfen. Ich denke eine Geschwindigkeitssteigerung läßt sich weniger durch eine schnellere Prüfroutine bewerkstelligen, sondern durch eine Minimierung der Prüfvorgänge.

Du könntest zum Beispiel für jedes Rechteck eine Liste erstellen, in der alle anderen Rechtecke drinstehen. Dann löschst Du in einer Schleife aus dieser Liste alle Rechtecke deren vier Eckpunkte nicht zwischen denen des aktuellen liegen. Wenn Du dann aus den Listen zu den anderen Rechtecken bereits das aktuelle 'Ausgangsrechteck' herauslöschst, bleiben nur die übrig bleiben, sich das Rechteck schneidet. Noch schneller geht es wenn Du zwei getrennte Listen für die zu überprüfenden und die bereits gefundenen machst und auch diese Listen parallel bearbeitest. Also nicht nur die sich nicht Überschneidenden löschst, sondern auch gleich die sich Überschneidenden in die zweite Liste verschiebst. Dadurch reduzierst Du die Anzahl der Prüfungen für jedes Folgerechteck.

Grüße Joche

[Ulrich Bosch]

Hi Jochen,

das ist eine gute und vor allen Dingen einfache Lösung!

Mein derzeitiger Lösungsansatz würde auch funktionieren, wenn die Rechtecke nicht senkrecht oder waagerecht zur Grundachse stehen würden, aber das brauche ich eigentlich gar nicht. Die Winkelbetrachtung würde ich z.Z. sowieso weglassen.

Vielen Dank für Deine Anregungen!

Gruss

Ul