Schnittpunkt von N Rechtecken

Ich bin auf der Suche nach einem Algorithmus um dieses problem zu lösen:

Gegeben N Rechtecke auf dem kartesischen Koordinatensystem, finden Sie heraus, wenn der Schnittpunkt dieser Rechtecke leer ist oder nicht. Jedes Rechteck liegen kann in eine beliebige Richtung (nicht nötig zu haben seine Kanten parallel zu Ox und Oy)

Haben Sie Vorschläge, um dieses problem zu lösen? 🙂 Ich kann mir denken, testen der Kreuzung der jedes Rechteck-pair-Mädchen. Es ist jedoch O(N*N) und ziemlich langsam 🙁

Verwandte: stackoverflow.com/questions/115426/...

InformationsquelleAutor Chan Le | 2011-05-04

  1. 3

    Beobachtung 1: gegeben sei ein polygon A und ein Rechteck B, die Schnittmenge A ∩ B können berechnet werden, indem 4 Schnittpunkt mit halb-Ebenen entsprechend jeder Kante des B.

    Beobachtung 2: schneiden Sie eine halbe Flugzeug von einem konvexen polygon gibt Ihnen ein konvexes polygon. Das erste Rechteck ist ein konvexes polygon. Dieser Vorgang erhöht die Anzahl der Knoten pro 1.

    Beobachtung 3: die signierte Distanz der Eckpunkte eines konvexen Polygons auf eine gerade Linie ist, einer unimodalen Funktion.

    Hier ist eine Skizze des Algorithmus:

    Beibehaltung der derzeitigen teilweisen Schnittpunkt D in einem ausgeglichenen binären Baum in ein CCW um.

    Beim schneiden einer halben Ebene, definiert durch eine Linie L, die zwei Kanten in D, die sich L. Diese kann getan werden, in logarithmischer Zeit durch einige clevere binäre oder ternäre Suche Ausnutzung der unimodality der signierten Distanz der L. (Das ist der Teil, den ich nicht mehr genau erinnern.) Entfernen Sie alle Scheitelpunkte auf der einen Seite L von D, und legen Sie die Schnittpunkte zu D.

    Wiederholen Sie dies für alle Kanten aus L aller Rechtecke.

    InformationsquelleAutor

  2. 17

    Abstrakte

    Entweder verwenden Sie einen Sortier-Algorithmus nach kleinsten X-Wert des Rechtecks, oder speichern Sie Ihre Rechtecke im R-Baum und Suche es.

    Straight-forward-Ansatz (mit Sortierung)

    Lassen Sie uns bezeichnen low_x() - die kleinste (ganz Links) X-Wert von einem Rechteck, und high_x() - die höchste (ganz Rechte) X-Wert ein Rechteck.

    Algorithmus:

    Sort the rectangles according to low_x().                   # O(n log n)

For each rectangle in sorted array:                         # O(n)
    Finds its highest X point.                              # O(1)
    Compare it with all rectangles whose low_x() is smaller # O(log n)
        than this.high(x)

    Komplexität Analyse

    Sollte diese Arbeit auf O(n log n) auf gleichmäßig verteilten Rechtecken.

    Schlimmsten Fall wäre O(n^2) zum Beispiel, wenn die Rechtecke nicht überlappen, sind aber einer über den anderen. In diesem Fall verallgemeinern den Algorithmus zu haben low_y() und high_y() zu.

    Daten-Struktur-Ansatz: R-Bäume

    Schnittpunkt von N Rechtecken

    R-Bäume (eine räumliche Verallgemeinerung der B-Bäume) sind eine der besten Möglichkeiten zum speichern von räumlichen Daten, und können hilfreich sein, dieses problem. Einfach speichern Sie Ihre Rechtecken einen R-Baum, und Sie können vor Ort Kreuzungen mit einer einfachen O(n log n) Komplexität. (n sucht, log n Zeit für jeden).

    Einfache & gute Lösung
    Es ist O(n^2). Der Letzte Schritt ist nicht in O(log n). Zähler-Beispiel: Menge von Rechtecken { [k, 2n-k]×[0, 1] | k ∈ {0, ..., n-1} }
    Siehe Nachtrag - die Rechtecke werden können, sortiert nach Ihren Y-Werte zu, so bleibt es O(n log n).
    NÖ. Gegenbeispiel 2: { [k, 2n-k]×[k, 2n-k] | k ∈ {0, ..., n-1} } — Art, aber Sie wollen, verwenden Sie ein R-Baum... es ist immer noch O(n^2).
    Ja, das ist die Antwort auf die falsche Frage. Und sich die Kreuzung der n-Achse ausgerichtet Boxen ist trivial, Sie brauchen keine nicht-triviale Datenstrukturen. Nur whack Weg axis-aligned slices of the box.

    InformationsquelleAutor

  3. 2

    Scheint das eine gute Anwendung des Klee ' s measure. Im Grunde, wenn Sie Lesen, http://en.wikipedia.org/wiki/Klee%27s_measure_problem gibt es untere Schranken für die Laufzeit von die besten algorithmen, die gefunden werden kann für die geraden Schnittpunkte in O(n log n).

    das ist richtig, Klee ' s measure ist so ziemlich die Verallgemeinerung dieser Frage und deckt es perfekt zeigen einen optimalen Algorithmus.
    Ich finde die Kreuzung. Ich denke, dass klee ' s measure ist alles über die union dieser Rechtecke?
    Diese Antwort ist faszinierend, aber es ist nicht klar, wie es gilt. Vielleicht ist die Frage über Schnittstellen können gerahmt werden, als eine Frage, über die Gewerkschaften, indem Sie ergänzt das irgendwie?

    InformationsquelleAutor

  4. 1

    Ich glaube, Sie sollten so etwas wie die sweep-line-Algorithmus: Suche nach Schnittmengen ist eine Ihrer Anwendungen. Außerdem haben Sie einen Blick auf Antworten auf diese Fragen

    Ein problem sehe ich hier, dass mit n Rechtecken, die ich erstellen kann n^2 Grenze Kreuzungen... (denken Sie sich ein plus von verschiedener Dicke).

    InformationsquelleAutor

  5. 0

    Da die Rechtecke dürfen nicht parallel zu der Achse, es ist leichter zu transformieren das problem auf ein bereits gelöst: berechnen Sie die Kreuzungen der Grenzen der Rechtecke.

    • bauen eine Menge S enthält alle Grenzen, zusammen mit dem Rechteck sind Sie gehören; Sie bekommen eine Menge von Tupeln der form ((x_start,y_start), (x_end,y_end), r_n), wo r_n ist, ist natürlich die ID des entsprechenden Rechtecks
    • verwenden Sie nun einen sweep-line-Algorithmus zum finden der Schnittpunkte dieser Linien

    Sweep-line hält an jeder x-Koordinate in S, also beginnen alle Werte und alle end-Werte. Für jeden neuen start zu koordinieren, legen Sie die entsprechende Zeile in einer temporären Satz I. Für jede neue Ende-zu koordinieren, entfernen Sie die entsprechende Zeile aus I.

    Zusätzlich zum hinzufügen von neuen Zeilen zu, die ich, Sie können überprüfen für jede neue Zeile, ob es überschneidet sich mit einer der Linien, die derzeit in I. Wenn Sie tun, werden die entsprechenden Rechtecke auch.

    Finden Sie eine detaillierte Erläuterung dieser Algorithmus hier.

    Die Laufzeit ist O(n*log(n) + c*log(n)), wobei c die Anzahl der Schnittpunkte der Linien im I.

    Das problem ist, dass c=n^2 ist möglich. Siehe mein Kommentar auf @MarcoS Antwort.
    das ist richtig, aber das ist die Natur des zugrunde liegenden Problems. Wenn die Lösung das set hat eine maximale Größe von n^2 ist, dann ist der Algorithmus zum finden dieser Satz muss auch ein worst-case-Laufzeit von O(n^2). Der Algorithmus, den ich vorgeschlagen, hat den Vorteil, dass seine Laufzeit passt sich die Komplexität der Lösung.

    InformationsquelleAutor

  6. -1

    Wählen das kleinste Rechteck, aus dem Satz (oder jedes Rechteck), und gehen über jeden Punkt, der innerhalb es. Wenn einem der Punkt existiert auch in allen anderen Rechtecken, die Schnittmenge ist nicht leer. Wenn alle Punkte sind frei von ALLE weitere Rechtecke, die Schnittmenge ist leer.

    Das ist es, was OP tut schon.
    Wenn R1 dont schneiden mit R2 und R3, dont bedeuten, R2 und R3 dont überschneiden
    Hmm, das ist O(2^aleph_0) - Algorithmus...
    aber das bedeutet, dass R1, R2 und R3 nicht überschneiden. Aber das ist immer noch ineffizient, können wir sagen, so schauen Sie einfach nur auf den Kanten (entweder oben/unten oder Links/rechts) die Rechtecke, die wie erwähnt von Adam.
    Wie bestimmen Sie, "jeder Punkt innerhalb es" ? 🙂 da gibt es unendlich Anzahl der Punkte innerhalb einer Fläche.

    InformationsquelleAutor

Schreibe einen Kommentar