Bereich der Schnittmenge Zweier Gedrehter Rechtecke
Habe ich zwei 2D-Rechtecke, definiert als ein Herkunft (x,y) eine Größe (Höhe, Breite) und ein Drehwinkel (0-360°). Ich kann garantieren, dass beide Rechtecke die gleiche Größe haben.
Ich brauche zu berechnen, die Ungefähre Fläche der Schnittmenge der beiden Rechtecke.
Die Berechnung nicht brauchen, um genau zu sein, obwohl es sein kann. Ich vergleichen das Ergebnis mit anderen Bereichen der Kreuzung, um zu bestimmen, die größte Bereich der Kreuzung in eine Reihe von Rechtecken, so dass es nur zu sein, muss präzise relativ zu anderen Berechnungen, die von den gleichen Algorithmus.
Ich dachte über die Verwendung der Fläche der bounding-box des durchschnittene region, aber ich habe Probleme dabei, die Eckpunkte der Durchschnitt der region, da, wie all die verschiedenen möglichen Fälle:
Schreibe ich dieses Programm in Objective-C im Cocoa-framework, für was es Wert ist, also wenn jemand weiß, alle Verknüpfungen, die über NSBezierPath oder etwas, du bist willkommen, zu vermuten, dass auch.
- Ich bin nicht immer, was Sie genau brauchen. Aber ich denke, dass die maximale Schnittmenge Bereich ist immer gleich um die Fläche eines der Rechtecke wie Sie die beiden Rechtecke der gleichen Gegend.
- er will nicht die maximal mögliche Kreuzung Bereich, aber die eigentliche Kreuzung der beiden angegebenen Rechtecke.
- Ja, du hast Recht. Aber in der Frage, die er erwähnt hat " ich kann garantieren, dass beide Rechtecke die gleiche Größe haben." und "ich werde vergleichen Sie das Ergebnis mit anderen Bereichen der Kreuzung, um zu bestimmen, der größte Bereich der Kreuzung in eine Reihe von Rechtecken". Also ich Zweifel, was erforderlich ist, genau.
- Shahbaz ist korrekt; ich habe eine Reihe von Rechtecken-von diesem Satz, muss ich feststellen, der größte Bereich der Kreuzung zwischen zwei von Ihnen. Der einzige Grund, warum ich erwähnen, es ist, um einen Kontext für den Grund, warum ich brauchen, um in der Lage sein, um den Bereich zu finden der Schnittpunkt von zwei Rechtecke.
- Dies ist im wesentlichen ein Duplikat der stackoverflow.com/questions/8011267/....
Du musst angemeldet sein, um einen Kommentar abzugeben.
Einen einfachen Algorithmus geben, der eine Ungefähre Antwort ist die Probenahme.
Teilen eine der Rechtecke in ein Gitter aus kleinen Quadraten. Für jeden Schnittpunkt, überprüfen, ob dieser Punkt innerhalb des anderen Rechtecks. Die Anzahl der Punkte, die sich innerhalb des anderen Rechtecks wird eine Recht gute Annäherung an den Bereich der überlappenden region. Die Erhöhung der Dichte der Punkte erhöht sich die Genauigkeit der Berechnung, auf Kosten der Leistung.
Ergänzung zu den anderen Antworten, Ihr problem ist eine Instanz von line-clipping, ein Thema stark studierte in computer-Grafik, und für die gibt es viele algorithmen zur Verfügung.
Wenn Sie drehen Sie das Koordinatensystem so, dass ein Rechteck hat eine horizontale Kante, dann das problem ist, genau line-clipping von dort aus auf.
Könnte man anfangen, an der Wikipedia-Artikel zum Thema, und untersuchen von dort aus.
In jedem Fall zur Berechnung der exakten Kreuzung polygon von zwei konvex Polygone ist eine einfache Aufgabe, da jedes konvexe polygon kann man als eine Kreuzung von halb-Ebenen. "Sequential cutting" macht den job.
Wählen Sie ein Rechteck (beliebige) als Rechteck schneiden. Durchlaufen Sie die Seiten des Schnitt-Rechtecks, eines nach dem anderen. Schneiden Sie das zweite Rechteck von der Zeile, in der sich die aktuelle Seite der Rechteck schneiden und entsorgen Sie alles, was liegt in der "äußeren"-halbebene.
Sobald Sie fertig sind, Durchlaufen alle Seiten schneiden, was bleibt von dem anderen Rechteck ist das Ergebnis.
Kann man tatsächlich berechnen, die genaue Fläche.
Dem freigegebenen Bereich ist
Nehmen jede Strecke jedes Rechteck und sehen, ob Sie sich überschneiden. Gibt es mehrere Möglichkeiten:
Wenn keine schneiden - shared-Bereich ist null - es sei denn, alle Punkte, die von einer innerhalb des anderen. In diesem Fall wird die freigegebene Bereich ist der Bereich, der die kleinere.
ein, Wenn zwei aufeinanderfolgende Kanten einer rectactangle schneiden mit einer einzigen Kante ein weiteres Rechteck, dieses bildet ein Dreieck. Berechnen Sie seine Fläche.
b. Wenn die Kanten nicht consequtive, dadurch bildet sich ein viereck. Berechnen Sie eine Linie, die von zwei gegenüberliegenden Ecken des Vierecks, das macht zwei Dreiecke. Berechnen Sie die Fläche eines jeden und Summe.
Wenn zwei Kanten von einer Schnittmenge mit zwei Kanten von anderen, dann hast du ein viereck. Berechnen Sie, wie in 2b.
Wenn jede Kante eines schneidet jede Kante des anderen, haben Sie ein Achteck. Brechen Sie in Dreiecke ( z.B. zeichnen Sie einen Strahl von einem vertex auf jeden anderen Eckpunkt, um 4 Dreiecke )
@edit: ich habe eine mehr Allgemeine Lösung.
Check der Besondere Fall in der 1.
Dann beginnen Sie mit einer schneidenden vertex, und Folgen Sie den Kanten von dort aus zu jedem anderen Schnittpunkt, bis Sie wieder auf dem first sich kreuzenden vertex. Dies bildet ein konvexes polygon. zeichnen Sie einen Strahl von der ersten Eckpunkt, um die Gegenseite vetex ( z.B. überspringen Sie den Eckpunkt nach Links und rechts. ) Dies wird teilen es in eine Reihe von Dreiecken. berechnen Sie den Bereich für jede Summe.
Einen brute-force-ish Weg:
Rechtecke] + [Schnittpunkte von Kanten]
.