Wie zeichne ich einen Umriss einer Gruppe mehrerer Rechtecke?

Question

Ich muss ein umschließendes Polygon aus einer Gruppe nebeneinander platzierter Rechtecke zeichnen.

Stellen wir uns Textfelder vor, die mindestens eine Kante (oder einen Teil davon) mit mindestens einem der anderen Rechtecke teilen.Ich kann die Punktkoordinaten der Rechtecke erhalten und habe daher im Grunde alle Daten, die ich darüber benötige.

Können Sie sich einen einfachen Algorithmus/ein einfaches Verfahren vorstellen, um ein Polygon (verbundene gerade Pfade) um diese Objekte herum zu zeichnen?

Hier ist eine Demonstration verschiedener möglicher Fälle (A, B, C usw.).In Beispiel A habe ich auch ein blaues Polygon gezeichnet, das den Pfad darstellt, den ich zeichnen muss, und der die Gruppe von Rechtecken umreißt.

Ich habe hier über konvexe Hüllen und ähnliches gelesen, aber in Wirklichkeit scheint das ein viel einfacheres Problem zu sein.Eine (Anfangs-)Lösung, die ich mir überlegt habe, war, dass die Punkte, durch die ich tatsächlich zeichnen muss, nur solche sind, die von keinem Rechteckpaar gemeinsam genutzt werden, was bedeutet, dass Punkte, die Eckpunkte von mehr als einem Rechteck sind, redundant sind.Was ich nicht herausfinden konnte, war die Reihenfolge, in der ich Linien von einer zur nächsten zeichnen muss.

Ich arbeite derzeit an Objective C, aber jede andere Sprache oder jeder andere Algorithmus wäre willkommen, einschließlich Pseudo.

Danke!

Answer 1

IMHO sollte es so sein.Machen Sie eine Liste von Kanten und sehen, ob einige Überlagerungen sind: Dies sollte einfach sein, wenn die Rechtecke mit der X-, Y-Achse ausgerichtet sind.Sie finden nur die Kanten, die die Scheitelpunkte auf demselben X oder Y haben, und die anderen Koordinaten müssen dazwischen sein.Danach sollten die restlichen Kanten den Umriss bilden.

Eine andere Methode, um gemeinsame Kanten zu finden, besteht darin, alle Rechtecke entlang jeder x- und y-Achse zu brechen, in denen Sie Scheitelpunkte haben.Dies sollte aussehen, als wären Sie alle Linien bis unendlich.Danach haben alle gängigen Kanten gemeinsame Scheitelpunkte und können beseitigt werden.

Answer 2

Sie haben zwei Reihen und drei verschiedene y-Werte.Sagen wir y0 ist die Spitze der Sache, y2 ist das untere Ende, und y1 markiert die Mitte zwischen beiden Reihen.
Jede Zeile hat einen maximalen und einen minimalen x-Wert, sagen wir, die oberste Zeile geht von aus x0_min Zu x0_max, und die unterste Reihe von x2_min Zu x2_max.Angesichts dieser Werte zeichnen Sie einfach um die Sache herum:

(x0_min,y0)->
(x0_max,y0)->
(x0_max,y1)->
(x2_max,y1)->
(x2_max,y2)->
(x2_min,y2)->
(x2_min,y1)->
(x0_min,y1)->
(x0_min,y0)