Wie funktionieren Formen (Rechtecke) in Quad-Bäumen?

10

Mir wurde gesagt, dass ein Quad-Baum die ideale Datenstruktur für mein Spiel ist, aber ich habe Probleme zu verstehen, wie genau Formen in Quad-Bäumen funktionieren.

Ich mache das in JavaScript, aber ich denke, diese Fragen könnten für Quad-Bäume in jeder Sprache gelten.

Ich denke, ich verstehe meistens, wie grundlegende (x, y) Punkte und das Einfügen von Punkten in Quad-Bäumen funktionieren und dass ich es auf Papier tun könnte.

Hier ist eine JSfiddle meines Experimentierens mit Punkten.

Quad Tree Punkte

Abgesehen von einem Fall funktionieren meine Tests mit Punkten wie erwartet.

Aber meine Verwirrung beginnt, wenn es um Formen wie Rechtecke geht. Überprüft es beim Abrufen von einem Quad-Baum mit Formen jeden Punkt der Form und in welche Knoten fallen sie? Und wie funktionieren Formeinfügungen überhaupt, wenn sie Parameter (x, y, Breite, Höhe) für jede Form akzeptieren? Verwendet es die Breite / Höhe vom Startpunkt aus, um andere Eckpunkte zu berechnen, die dann in geeignete Knoten verteilt werden? Wenn sich eine eingefügte Form in vier Knoten erstreckt, werden die Daten dieser Form in allen vier Knoten gespeichert?

Und wenn eine Abrufmethode eine Form als Parameter akzeptiert (x, y, Breite, Höhe), was ist dann tatsächlich los? Wird zuerst angezeigt, auf welche Knoten sich die Form erstrecken würde, wenn sie eingefügt würde, und dann alle Objekte dieser Knoten abgerufen?

Ich habe eine JSfiddle, die mit Formen arbeitet , aber ich bin völlig verwirrt über die Ergebnisse meiner Tests. Ich erhalte doppelte Objekte, die zurückgegeben werden!

Quad Baumformen

Das rote Quadrat entspricht beispielsweise den Parametern, die ich in meine Abrufmethode eingebe. Ich würde denken, da dieses rote Quadrat alle vier Knoten überspannt, sollte es jedes Objekt im Quad-Baum zurückgeben! Aber das tut es nicht und ich habe Probleme zu rationalisieren, was es zurückgibt. Ich habe eine Reihe anderer Tests, die derzeit auskommentiert sind, aber Sie können sie auskommentieren und ausführen, um verwirrendere Ergebnisse zu sehen!

Wie würde ich das tun, wenn ich alle Punkte in einem Quad-Baum zurückgeben möchte? Eine Abrufmethode unter Verwendung einer Form über die gesamte Größe der Grenzen? Beispiel: Abrufen (0, 0, canvas.width, canvas.height)?

Auf die von mir verwendete JavaScript QuadTree-Bibliothek wurde von verschiedenen anderen Quellen verwiesen, daher gehe ich davon aus, dass die tatsächliche Implementierung korrekt und seriös ist.

Ich denke, ein Großteil meiner Verwirrung kann auf ein Missverständnis der Quad-Tree-Terminologie zurückzuführen sein. Warum sagen sie Grenzen statt Bemaßungen, wenn ein "Punkt" auch Breiten- / Höhenparameter hat? Ist es eine Frage der Konvention / Kurzschrift oder sind es völlig andere Konzepte?

Vielen Dank für Ihre Zeit!

user2736286
quelle
Sie werden wie gewohnt nach ihrer Position im Quad-Baum gespeichert. Normalerweise befinden sich diese in der Mitte, können sich aber in der von Ihnen definierten Ecke befinden. Ihre Frage ist möglicherweise ein Duplikat dieser Frage: QuadTree: Nur Punkte oder Regionen speichern?
MichaelHouse
Ich habe diese Frage gelesen, aber ich verstehe die Antworten immer noch nicht vollständig :(. "Sie müssen sie auf dem kleinsten Knoten speichern, der sie vollständig enthält - auch wenn diese die Kapazität überschreitet (verwenden Sie einen Container mit veränderbarer Größe)." - Wenn er sagt der kleinste Knoten, der es VOLLSTÄNDIG enthält, wenn das Objekt sehr groß ist, wäre dieser Knoten dann nicht oft ein Nicht-Blatt-Knoten? Wie bei einem höheren Knoten, der nur aus anderen Knoten besteht? Das scheint nicht richtig zu sein Ich, da dies bedeuten würde, dass der enthaltende Knoten 1 Blatt und die 4 kleineren Knoten darin haben würde.
user2736286
1
@ user2736286 Wenn Sie sich den Code für die quadtree lib ansehen (er ist nicht sehr lang), können Sie sehen, dass Rechtecke in übergeordneten Knoten gespeichert werden, um zu verhindern, dass sie sich über Knotengrenzen erstrecken. Siehe die Verweise auf das _stuckChildrenFeld im Code. Sie können dies auch im Beispiel "Abrufen von Elementen mit Grenzen" sehen. Es hebt immer die Knoten rot hervor, die sich über die Ränder der Knoten erstrecken, auf die Sie geklickt haben, bis zum Stammknoten.
Nathan Reed
@ user2736286 Außerdem scheint die quadtree lib einen Fehler beim Abrufen von Elementen mit Grenzen zu haben. Wenn Sie ihr eine Abfrage korrigieren, die sich über einige Knotengrenzen erstreckt, werden nicht alle Rechtecke in Knoten zurückgegeben, die von der Abfrage berührt werden. Sie können dies auch leicht unter "Abrufen von Elementen mit Grenzen" sehen, indem Sie in der Nähe der Knotenränder klicken.
Nathan Reed
@NathanReed Früher habe ich versucht, den Code zu verstehen, aber ich bin nicht geschickt genug, um ihn ohne konzeptionelle Grundlage zu verstehen. Dank John McDonalds Pseudocode verstehe ich jetzt, wie Rechtecke in Knoten eingefügt werden, aber ich glaube, ich bin immer noch unklar, wie das Abrufen funktioniert. Was das "Abrufen von Elementen mit Grenzen" betrifft, bin ich durch das Beispiel völlig verwirrt. Wenn ich auf ein Rechteck klicke, das sauber in einen der kleinsten Knoten passt, warum werden all diese anderen Rechtecke außerhalb dieses Knotens ebenfalls hervorgehoben?
user2736286

Antworten:

10

Quadtrees speichern und rufen normalerweise Rechtecke ab. Ein Punkt ist ein spezieller Fall, in dem Breite und Höhe Null sind. Die folgende Logik wird verwendet, um nach neuen Rechtecken im Baum zu suchen, beginnend mit dem Stammknoten:

void Store(Rectangle rect)
{
    if(I have children nodes)
    {
        bool storedInChild = false;
        foreach(Node childNode in nodes)
        {
            if(this rectangle fits entirely inside the childNode bounds)
            {
                childNode.Store(rect);   // Go deeper into the tree
                storedInChild = true;
                break;
            }
        }
        if(not storedInChild)
        {
            Add this rectangle to the current node
        }
    }
    else
    {
        Add this rectangle to the current node
    }
}

Beachten Sie, dass Rechtecke in jeder Tiefe gespeichert werden können. Es muss sich nicht um ein Blattquad handeln. Wenn das Rechteck die Grenze direkt auf der Wurzelebene überspannt, speichert das Wurzelquad das Rechteck.

Das rote Quadrat entspricht beispielsweise den Parametern, die ich in meine Abrufmethode eingebe. Ich würde denken, da dieses rote Quadrat alle vier Knoten überspannt, sollte es jedes Objekt im Quad-Baum zurückgeben! Aber das tut es nicht und ich habe Probleme zu rationalisieren, was es zurückgibt.

Beim Abfragen des Quadtree werden nur Rechtecke zurückgegeben, die in der Abfrage enthalten sind. In Ihrem Beispiel erzwingen Sie, dass jedes der 4 untergeordneten Quads genauer betrachtet wird, da das rote Abfrage-Rechteck jedes untergeordnete Quad schneidet. Da die Kinder keine weiteren Kinder haben, wird jedes der Rechtecke in diesen untergeordneten Quads mit dem roten Rechteck verglichen. Da keines der Rechtecke im Baum mit dem roten Abfragerechteck kollidiert, sollte nichts zurückgegeben werden.

Sie sehen wirklich Vorteile von Quadtrees, wenn Sie viele Objekte haben und im Vergleich zu den Abfragebereichen viel Platz für die Objekte vorhanden ist. In diesen Fällen kann ein kleiner Abfragebereich schnell große Teile des Quad-Baums aus der Betrachtung entfernen. Nur Quads, die sich mit dem Abfrage-Rechteck überschneiden, werden jemals genauer betrachtet.

BEARBEITEN

Das Abrufen erfolgt normalerweise wie folgt:

List<Rectangle> Query(Rectangle queryRect)
{
    List<Rectangle> results;
    foreach(Node childNode in children)
    {
        if(queryRect intersects with childNode bounds)
        {
            results += childNode.Query(queryRect);   // Dig deeper into the tree
        }
    }

    foreach(Rectangle I have stored in this quad)
    {
        if(queryRect intersects with rect)  // Your library doesn't do this
        {
            results += rect;
        }
    }

    return results;
}

In Ihrer Bibliothek scheint es jedoch nicht zu prüfen, ob sich die zurückgegebenen Rechtecke mit der Abfrage überschneiden. Sie müssen diese also selbst hinzufügen.

John McDonald
quelle
Nachdem Sie sich Ihre Bibliothek genauer angesehen haben, gibt Ihre Bibliothek eine Liste aller möglichen Kollisionskandidaten für das von Ihnen angegebene Abfragerechteck zurück. Es scheint Ihre Aufgabe zu sein, Ihr Abfragerechteck mit jedem Kandidaten zu vergleichen, um festzustellen, ob es tatsächlich zu einer Kollision kommt. Die meisten Bibliotheken erledigen diesen letzten Schritt für Sie und geben nur die tatsächlichen Kollisionen mit dem Abfragebereich zurück. Alles, was Sie tun müssen, ist, Ihrer retrieveMethode eine Logik hinzuzufügen , um die Liste zu bereinigen. Sie können hier etwas deutlicher sehen, was es tut: mikechambers.com/html5/javascript/QuadTree/examples/…
John McDonald
1
@ user2736286 Falls Sie es nicht aufgegriffen haben, ist es wichtig, die Rekursion in den Abfrage- und Speicherfunktionen zu beachten, die JohnMcDonald geschrieben hat. Es wird nicht viel Sinn machen, wenn Sie diesen Teil nicht bekommen. Bei beiden geht jede Rekursion tiefer in den Baum hinein, dh auf Ästen und schließlich in Blätter.
TASagent
Danke John, dein Pseudocode ist sehr hilfreich. Wenn Sie "if (queryRect überschneidet sich mit childNode-Grenzen)" sagen, bedeutet dies im Grunde, dass das queryRect teilweise oder vollständig in den Grenzen enthalten ist ? Ich möchte nur 100% klar sein. Außerdem habe ich im Beispiel "Element nach Grenzen abrufen" ein Bild des Ergebnisses meines Klicks. Pic Der blaue Punkt ist, wo ich geklickt habe. Warum sind nicht nur die beiden Rechtecke in diesem Knoten beleuchtet? Warum werden weit davon entfernte Rechtecke ebenfalls hervorgehoben? Ich denke, das ist es, was mich wirklich verwirrt.
user2736286
Teilweise oder vollständig. Wenn sich die beiden berühren oder einer vollständig im anderen enthalten ist. Sie möchten das Wiki auf Quadtrees lesen , aber ich habe Ihr Bild aufgenommen und es farblich gekennzeichnet, um die verschiedenen untergeordneten Grenzen darzustellen. Alle blauen Rechtecke schneiden sich mit den Grenzen der ersten untergeordneten Quads, wobei Magenta eine Schicht tiefer und Grün noch eine Schicht tiefer liegt. Rote Rechtecke schneiden sich mit dem angeklickten Quad. Ihre Bibliothek gibt alle Rechte an den untergeordneten Grenzen sowie alle im letzten untergeordneten
John McDonald
Ok, also habe ich mein Bestes gegeben, um den Quellcode der Bibliothek durchzugehen, und ich verstehe endlich das Verhalten von stickChildren und dass all diese zusätzlichen Rechtecke in meinem Bild einfach die steckengebliebenen Kinder sind. Ursprünglich dachte ich, dass bei allen Rects, die sich über mehrere Knoten erstrecken, die Daten nur dupliziert und in jeden kleineren Knoten eingefügt werden. Jetzt ist mir klar, dass stickChildren nicht in Knoten eingefügt wird, die es überspannt, sondern einfach in dem einen Knoten bleibt, der es enthält. Deshalb muss ich auch alle übergeordneten Knoten überprüfen und nicht nur den kleinsten Knoten, der meine Abfrage enthält. Danke für das Bild; es macht jetzt viel mehr Sinn :)
user2736286