Testen Sie, ob der Punkt in manchen Rechteck

Ich habe eine große Sammlung von Rechtecken, die alle die gleiche Größe. Ich bin Generierung von Zufallszahlen Punkte, die nicht fallen in diese Rechtecke, also, was ich tun möchte, ist zu testen, ob der erzeugte Punkt liegt in einem der Rechtecke, und wenn es das tut, erzeugen Sie einen neuen Punkt ein.

Verwendung von R-Bäumen zu arbeiten scheinen, aber Sie sind eigentlich für Rechtecke und keine Punkte. Ich könnte mit einer modifizierten version eines R-Baum-Algorithmus, das funktioniert mit den Punkten zu, aber ich möchte lieber nicht das Rad neu erfinden, wenn es schon einige bessere Lösung. Ich bin nicht sehr vertraut mit Daten-Strukturen, also vielleicht es gibt schon eine gewisse Struktur, die funktioniert für mein problem?

In der Zusammenfassung, im Grunde, was ich Frage, ist, ob jemand weiß, von einem guten Algorithmus, das funktioniert in Python, das kann verwendet werden, um zu überprüfen, ob ein Punkt liegt in jedes Rechteck in einem gegebenen Satz von Rechtecken.

edit: Das ist in 2D, und die Rechtecke sind nicht verdreht.

Sind die Seiten der Rechtecke ausgerichtet mit der Achse an, oder sind Sie orientiert an beliebigen Winkel zu den Achsen?
Sie sind alle ausgerichtet, keine rotation oder etwas Phantasie, wie
tun die Rechtecke überlappen?
Ja, es ist durchaus möglich, dass sich die Rechtecke überlappen

InformationsquelleAutor pafcu | 2009-12-13

  1. 8

    Diesem Reddit-thread-Adressen Ihr problem:

    Ich habe eine Reihe von Rechtecken, und benötigen, um zu bestimmen, ob ein Punkt enthalten ist, innerhalb einer von Ihnen. Was sind einige gute Daten-Strukturen, um dies zu tun, mit schnellen lookup-sein wichtig?

    Wenn Ihr Universum ist integer, oder wenn die Präzision ist gut bekannt und wird nicht zu hoch sein, können Sie abelsson's Vorschlag aus dem thread, mit O(1) lookup mit Farbstoff:

    Wie gewohnt können Sie Handel mit Raum für
    mal.. hier ist ein O(1) lookup mit sehr
    niedrige Konstante. init: Erstellen Sie eine bitmap
    groß genug, um Sie umhüllen alle Rechtecke
    mit ausreichender Genauigkeit zu initialisieren
    es zu schwarz. Farbe alle Pixel
    mit jedem Rechteck weiß. O(1)
    lookup: der Punkt (x,y) white? Wenn
    so, ein Rechteck getroffen wurde.

    Ich empfehle Euch, geht zu post und vollständig gelesen ModernRonin's Antwort, die am meisten akzeptierte. Ich klebte es hier:

    Erste, der Mikro-problem. Sie haben eine
    beliebig gedrehtes Rechteck, und eine
    Punkt. Ist der Punkt innerhalb des
    Rechteck?

    Gibt es viele Möglichkeiten, dies zu tun. Aber
    die beste, die ich denke, ist mit Hilfe der 2d -
    Vektor-Kreuz-Produkt. Erstens, stellen Sie sicher, dass
    die Punkte des Rechtecks gespeichert werden
    reihum im Uhrzeigersinn. Dann machen Sie den Vektor
    Kreuz-Produkt mit 1) der Vektor
    gebildet durch die beiden Punkte von der Seite
    und 2) einen Vektor vom ersten Punkt
    von der Seite auf die Probe Stelle. Überprüfen
    das Zeichen des Ergebnis - positiv ist
    im inneren (rechts) der Seite,
    negativ ist draußen. Wenn es drin ist
    alle vier Seiten, ist es im inneren des
    Rechteck. Oder was dasselbe ist, wenn es
    außerhalb einer der Seiten, es ist außerhalb der
    das Rechteck. Weitere Erklärung hier.

    Diese Methode wird 3 subtrahiert pro
    vector * - mal 2 Vektoren pro Seite,
    plus ein Kreuz Produkt pro Seite, die
    ist drei multipliziert und zwei adds. 11
    flops pro Seite, 44-flops pro
    Rechteck.

    Wenn Sie nicht wie die cross Produkt,
    dann könnte man etwas machen wie:
    herauszufinden, die eingeschrieben und
    umschriebenen Kreise für jede
    Rechteck, überprüfen Sie, ob der Punkt innerhalb
    die eingeschrieben. Wenn ja, ist es in der
    Rechteck als gut. Wenn nicht, überprüfen Sie, ob
    es ist außerhalb des umschriebenen
    Rechteck. Wenn ja, ist es außerhalb der
    Rechteck als gut. Wenn es fällt, zwischen
    die beiden Kreise, Sie sind f****d und Sie
    müssen, überprüfen Sie es auf die harte Art und Weise.

    Herauszufinden, ob ein Punkt in einem Kreis
    in 2d dauert zwei Subtraktionen und zwei
    squarings (= multipliziert), und dann
    vergleichen distance squared zu vermeiden
    zu tun eine Quadratwurzel. 4
    flops, mal zwei Kreise ist 8-flops -
    aber manchmal ist Sie immer noch nicht wissen.
    Auch dies setzt Voraus, dass Sie nicht bezahlen
    jeder CPU-Zeit zur Berechnung der
    umschriebene oder geritzte Kreise,
    die kann oder kann nicht wahr sein, je nachdem
    wie viel pre-Berechnung bist du
    bereit zu tun, auf das Rechteck legen.

    In jedem Fall, es ist wahrscheinlich nicht ein
    tolle Idee zum testen der Punkt, gegen
    jedes Rechteck, vor allem, wenn Sie
    hundert Millionen von Ihnen.

    Das bringt uns zu der makro-problem.
    Wie zu vermeiden, testen Sie den Punkt gegen
    jedes einzelne Rechteck im set? In
    2D, das ist wohl ein quad-Baum
    problem. In 3d, was generic_handle
    gesagt - ein octree. Aus der Spitze von meinem
    Kopf, wahrscheinlich würde ich es umsetzen wie
    ein B+ - Baum. Es ist verlockend, zu verwenden, d = 5,
    so, dass jeder Knoten kann bis zu 4
    Kinder, da die Karten so schön
    auf die quad-tree-Abstraktion. Aber wenn
    die Menge der Rechtecke ist zu groß, um
    passen in Hauptspeicher (nicht sehr wahrscheinlich
    in diesen Tagen), dann, dass der Knoten der
    gleiche Größe wie Platte Blöcke ist wahrscheinlich
    der Weg zu gehen.

    Watch out für die lästigen ausarten
    Fälle, wie auch einige Daten, die über zehn
    tausend fast identische Rechtecke
    mit den Zentren an der gleichen Stelle.
    😛

    Warum ist dieses problem wichtig? Es ist
    nützlich in computer-Grafik, zu überprüfen
    wenn ein Strahl schneidet, ein polygon. I. e.,
    hab das sniper Gewehr erschossen, die Sie gerade
    gemacht trifft die person, die Sie geschossen haben
    ? Es ist auch in real-time anzeigen
    software, wie zum Beispiel GPS-Geräte. GPS
    sagt Ihnen die Koordinaten, die du bist,
    aber die software der Karte zu finden, wo
    dieser Punkt ist in eine riesige Menge von anzeigen
    Daten, und tun es mehrmals pro
    zweite.

    Wieder Kredit zu ModernRonin...

    Ich habe eine harte Zeit vorzustellen, wie die ModernRonin "Vektor-Produkt" - Methode kann schneller sein als lediglich die überprüfung, ob min_x <= x <= max_x und max_x <= y <= max_y... ich bin mir nicht sicher über die quadtree-Ansatz, da Sie meist helfen bei der Speicherung von Punkten, nicht Rechtecke...
    Die Vektor-Produkt ermöglicht ein Rechteck beliebiger Orientierung; ich bin sicher, dass andere Methoden besser geeignet sind, wenn alle Rechtecke sind, ausgerichtet an den Achsen von einem Koordinatensystem.
    Auch die Vektor-Produkt-Methode ermöglicht ein um zu überprüfen, ob ein Punkt im inneren eines jeden 4-seitige Form, ob oder nicht es ist ein Rechteck.

    InformationsquelleAutor Roee Adler

  2. 2

    Für Rechtecke, die ausgerichtet sind mit den Achsen, brauchen Sie nur zwei Punkte (vier Ziffern) zu identifizieren, die Rechteck - konventionell, unteren linken und oberen rechten Ecken. Um festzustellen, ob einem gegebenen Punkt (Xtest, Ytest) überlappt mit einem Rechteck (XBL, YBL, XTR, YTR) Test:

    • Xtest >= XBL && Xtest <= XTR
    • Ytest >= YBL && Ytest <= YTR

    Klar, für eine ausreichend große Anzahl von Punkten zu testen, könnte dies ziemlich zeitaufwendig. Die Frage ist also, wie die Optimierung der Tests.

    Klar, eine Optimierung ist die Festlegung der minimalen und maximalen X-und Y-Werte für das Feld um alle Rechtecke (bounding box): eine schnelle test auf dieser zeigt, ob es gibt keine Notwendigkeit, weiter zu suchen.

    • Xtest >= Xmin && Xtest <= Xmax
    • Ytest >= Ymin && Ytest <= Ymax

    Je nachdem, wie viel von der gesamten Oberfläche bedeckt ist mit Rechtecken, die Sie vielleicht in der Lage sein zu finden, nicht überlappende Teilbereiche, die Rechtecke enthalten, und Sie können dann vermeiden, auf der Suche diesen sub-Gebieten, die nicht enthalten ein Rechteck überlappen der Punkt, wieder speichern vergleichen während der Suche auf Kosten der pre-Berechnung von geeigneten Datenstrukturen. Wenn die Menge der Rechtecke ist spärlich genug, kann es keine überschneidungen, in welchem Fall diese degeneriert in der brute-force-Suche. Ebenso, wenn die Menge der Rechtecke ist so dicht, dass es keine sub-Bereiche, die in der bounding-box, kann aufgeteilt werden, ohne zu brechen Rechtecke.

    Jedoch, Sie könnte auch willkürlich brechen die Begrenzungsrahmen in, sagen wir, Viertel (die Hälfte in jede Richtung). Dann könnten Sie über eine Liste von Feldern, die mit mehr Boxen als im original-set (zwei oder vier Boxen für jede box, überlappt eine der willkürlichen Grenzziehungen). Dies hat den Vorteil, dass Sie könnten, dann beseitigen Sie drei der vier Quartale von der Suche, die Verringerung der Menge des Suchens getan werden, insgesamt - auf Kosten der auxiliary storage.

    So, es gibt Raum-Zeit-trade-offs, wie immer. Und pre-computation-versus-Suche von trade-offs. Wenn man Pech hat, sind die pre-Berechnung bringt nichts (es gibt zum Beispiel zwei Boxen nur, und Sie sich nicht überlappen, auf beide Achsen). Auf der anderen Seite, könnte es zu erheblicher such-Zeit profitieren.

    InformationsquelleAutor Jonathan Leffler

  3. 1

    Warum nicht versuchen, diese. Es scheint vielmehr Licht auf die Berechnung und Speicher.

    Betrachten Sie die Projektionen aller Rechtecke auf der base line von Ihrem Platz. Zu zeigen, dass Satz von Linien-Abständen, wie

     {[Rl1, Rr1], [Rl2, Rr2],..., [Rln, Rrn]}, ordered by increasing left coordinates.

    Nehmen wir nun an, dein Punkt ist (x, y), starten Sie eine Suche bei den Links von dieser Reihe, bis Sie eine Zeile Intervall, das enthält den Punkt x.

    Wenn keiner wird, der Punkt (x,y) ist, die außerhalb aller Rechtecke.

    Wenn es einige tun, sagen, [Rlk, Rrk], ..., [Rlh, Rrh], (k <= h), dann prüfen Sie einfach, ob y ist innerhalb der vertikalen Ausdehnung jedes dieser Rechtecke.

    Getan.

    Glück.

    John Döner

    InformationsquelleAutor John R Doner

  4. 0

    Ich schlage vor, Sie nehmen einen Blick auf BSP-Bäume (und möglich quadtrees oder octrees, links auf dieser Seite). Sie werden verwendet, um die partition, die den gesamten Raum rekursiv und ermöglichen es Ihnen, schnell zu überprüfen, ob ein Punkt, mit dem die Rechtecke, die Sie brauchen, um zu überprüfen, zu alle.

    Mindestens Sie müssen nur mit einer großen partition und überprüfen müssen, um alle Rechtecke, höchstens deine Partitionen so klein, dass Sie runter, um die Größe der einzelnen Rechtecke. Natürlich feiner die partition, desto länger benötigen Sie zu Fuß nach unten den Baum um zu finden, die Rechtecke, die Sie überprüfen möchten.

    Allerdings können Sie frei entscheiden, wie viele Rechtecke, die geeignet sind, überprüft werden, für einen Punkt und erstellen Sie dann eine entsprechende Struktur.

    Achten Sie auf sich überlappende Rechtecke obwohl. Als die BSP-Baum werden muss vorausberechnete sowieso, kann man da auch "überlappungen entfernen" während dieser Zeit, so können Sie Partitionen löschen.

    InformationsquelleAutor Frank

  5. 0

    Ihre R-tree-Ansatz ist der beste Ansatz, den ich kenne (das ist der Ansatz, den ich wählen würde, über quadtrees, B+ - Bäume, BSP-Bäume, R-Bäume scheinen bequem zu bauen, in deinem Fall). Caveat: ich bin kein Experte, obwohl ich erinnere mich an ein paar Dinge von meinem senior-Jahr an der Universität-Klasse von algorithmischen!

    InformationsquelleAutor Eric O Lebigot

Schreibe einen Kommentar