Wie finde ich in 2D effizient das nächste Objekt zu einem Punkt?

35

Ich habe eine große Spiel-Engine und möchte eine Funktion zum Ermitteln des nächsten Punktes aus einer Liste.

Ich könnte einfach den Satz von Pythagoras verwenden , um jede Entfernung zu finden und die Mindestentfernung zu wählen, aber dazu müssen alle durchlaufen werden.

Ich habe auch ein Kollisionssystem, bei dem ich Objekte in kleinere Objekte auf einem kleineren Gitter verwandle (ähnlich einer Minikarte) und nur dann, wenn Objekte im selben Gitterraum existieren, auf Kollisionen prüfe. Ich könnte das tun, nur den Rasterabstand vergrößern, um auf Nähe zu prüfen. (Anstatt jedes einzelne Objekt zu überprüfen.) Dies würde jedoch zusätzliche Einstellungen in meiner Basisklasse erfordern und das bereits überfüllte Objekt unübersichtlich machen. Lohnt es sich?

Gibt es etwas Effizientes und Genaues, mit dem ich anhand einer Liste von Punkten und Größen feststellen kann, welches Objekt am nächsten ist?

ultifinitus
quelle
Speichern Sie quadratische Versionen von x- und y-Positionen, damit Sie Pythagoras-Theorem ausführen können, ohne das teure sqrt am Ende ausführen zu müssen.
Jonathan Connell
3
Dies wird als Suche nach dem nächsten Nachbarn bezeichnet . Im Internet wird viel darüber geschrieben. Die übliche Lösung ist die Verwendung einer Art Raumteilungsbaum .
BlueRaja - Danny Pflughoeft

Antworten:

38

Das Problem mit einem Quad / Octree bei der Suche nach nächsten Nachbarn besteht darin, dass das nächstgelegene Objekt möglicherweise genau über der Unterteilung zwischen Knoten liegt. Bei Kollisionen ist dies in Ordnung, da es uns egal ist, ob es sich nicht um einen Knoten handelt. Aber betrachten Sie dieses 2D-Beispiel mit einem Quadtree:

Quadtree Beispiel

Hier ist der schwarze Gegenstand dem blauen Gegenstand am nächsten, obwohl sich der schwarze Gegenstand und der grüne Gegenstand im selben Knoten befinden. Die Antwort von ultifinitus kann nur den nächsten Nachbarn garantieren, nur jedes Element in Ihrem Baum wird in den kleinstmöglichen Knoten gestellt, der es enthalten könnte, oder in einen eindeutigen Knoten - dies führt zu ineffizienten Quadtrees. (Beachten Sie, dass es viele verschiedene Möglichkeiten gibt, eine Struktur zu implementieren, die als Quad / Octree bezeichnet werden kann. Strengere Implementierungen funktionieren in dieser Anwendung möglicherweise besser.)

Eine bessere Option wäre ein kd-Baum . Kd-Bäume haben einen sehr effizienten Algorithmus für die Suche nach nächsten Nachbarn , den Sie implementieren können, und können eine beliebige Anzahl von Dimensionen enthalten (daher "k" Dimensionen).

Eine großartige und informative Animation von Wikipedia: kd-tree next-neighbour search

Das größte Problem bei der Verwendung von kd-trees ist, wenn ich mich recht entsinne, dass es schwieriger ist, Elemente einzufügen / daraus zu entfernen, während das Gleichgewicht erhalten bleibt. Daher würde ich empfehlen, einen kd-Baum für statische Objekte wie Häuser und Bäume zu verwenden, der sehr ausgewogen ist, und einen anderen, der Spieler und Fahrzeuge enthält, die regelmäßig ausgewogen werden müssen. Suchen Sie das nächste statische Objekt und das nächste mobile Objekt und vergleichen Sie diese beiden.

Schließlich sind kd-trees relativ einfach zu implementieren, und ich bin sicher, dass Sie mit ihnen eine Vielzahl von C ++ - Bibliotheken finden können. Soweit ich mich erinnere, sind R-Bäume viel komplizierter und wahrscheinlich übertrieben, wenn Sie nur eine einfache Suche nach dem nächsten Nachbarn benötigen.

dlras2
quelle
1
Tolle Antwort, kleines Detail "Nur der nächste Nachbar ist garantiert. Nur jedes Element in Ihrem Baum befindet sich im kleinstmöglichen Knoten." In meiner Antwort habe ich alle Elemente im selben und im Nachbarknoten durchlaufen, sodass Sie eine Schleife über 10 statt über 10 erstellen 10.000.
Roy T.
1
Sehr wahr - ich nehme an, "nur" war ein ziemlich hartes Wort. Es gibt auf jeden Fall Möglichkeiten, Quadtrees für die Suche nach nächsten Nachbarn zu gewinnen, je nachdem, wie Sie sie implementieren. Wenn Sie sie jedoch aus anderen Gründen (z. B. zur Kollisionserkennung) nicht verwenden, würde ich mich an den optimierten kd-tree halten.
dlras2
Ich wollte festhalten, dass ich eine Implementierung gemacht habe, die sich mit dem schwarz-grün-blauen Problem befasst. Überprüfen Sie den Boden.
Clankill3r
18

sqrt() ist monoton oder ordnungserhaltend für nicht negative Argumente, also:

sqrt(x) < sqrt(y) iff x < y

Und umgekehrt.

Wenn Sie also nur zwei Entfernungen vergleichen möchten, aber nicht an deren tatsächlichen Werten interessiert sind, können Sie einfach die sqrt()-Stufe aus Ihrem Pythagoras-Zeug herausschneiden:

pseudoDistanceB = (A.x - B.x + (A.y - B.y
pseudoDistanceC = (A.x - C.x + (A.y - C.y
if (pseudoDistanceB < pseudoDistanceC)
{
    A is closest to B!
}
else
{
    A is closest to C!
}

Es ist nicht so effizient wie das Oct-Tree-Ding, aber es ist einfacher zu implementieren und erhöht die Geschwindigkeit zumindest ein wenig

HumanCatfood
quelle
1
Diese Metrik wird auch als euklidischer Quadratabstand bezeichnet .
moooeeeep
10

Sie müssen eine räumliche Partitionierung durchführen. In diesem Fall erstellen Sie eine effiziente Datenstruktur (normalerweise ein Octree). In diesem Fall befindet sich jedes Objekt in einem oder mehreren Räumen (Würfeln). Wenn Sie wissen, in welchen Räumen Sie sich befinden, können Sie O (1) nachschlagen, welche Räume Ihre Nachbarn sind.

In diesem Fall können Sie das nächstgelegene Objekt finden, indem Sie zunächst alle Objekte in Ihrem eigenen Raum durchlaufen und nach dem nächstgelegenen suchen. Wenn niemand da ist, kannst du deine ersten Nachbarn überprüfen, wenn niemand da ist, kannst du ihre Nachbarn überprüfen, etc ...

Auf diese Weise können Sie leicht das nächste Objekt finden, ohne alle Objekte in Ihrer Welt durchlaufen zu müssen. Wie üblich erfordert dieser Geschwindigkeitsgewinn ein wenig Buchhaltung, aber er ist wirklich nützlich für alle Arten von Dingen. Wenn Sie also eine große Welt haben, lohnt es sich definitiv, räumliche Partitionierung und einen Octree zu implementieren.

Siehe auch den Wikipedia-Artikel: http://en.wikipedia.org/wiki/Octree

Roy T.
quelle
7
@ultifinitus Um dies hinzuzufügen: Wenn Ihr Spiel 2D ist, können Sie QuadTrees anstelle von Octrees verwenden.
TravisG
1

Vielleicht versuchen Sie , Ihre räumlichen Daten in einer RTree Organisation, die Art wie ein btree für Sachen im Raum und ermöglicht Abfragen wie „nächste N Nachbarn“ etc ... http://en.wikipedia.org/wiki/Rtree

Patrick Hughes
quelle
0

Hier ist meine Java-Implementierung, um aus einem QuadTree den nächstgelegenen zu erhalten. Es befasst sich mit dem Problem, das dlras2 beschreibt:

enter image description here

Ich denke, die Operation ist wirklich effizient. Es basiert auf der Entfernung zu einem Quad, um zu vermeiden, dass in Quads weiter gesucht wird als in der aktuell nächstgelegenen.

// . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

public T getClosest(float x, float y) {

    Closest closest = new Closest();
    getClosest(x, y, closest);

    return closest.item;
}

// . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

protected void getClosest(float x, float y, Closest closestInfo) {


    if (hasQuads) {

        // we have no starting point yet
        // so get one
        if (closestInfo.item == null) {
            // check all 4 cause there could be a empty one
            for (int i = 0; i < 4; i++) {
                quads[i].getClosest(x, y, closestInfo);
                if (closestInfo.item != null) {
                    // now we have a starting point
                    getClosest(x, y, closestInfo);
                    return;
                }

            }
        }
        else {

            // we have a item set as closest
            // we should check if this quad is
            // closer then the current closest distance
            // let's start with the closest from index

            int closestIndex = getIndex(x, y);

            float d = quads[closestIndex].bounds.distToPointSQ(x, y);

            if (d < closestInfo.dist) {
                quads[closestIndex].getClosest(x, y, closestInfo);
            }

            // check the others
            for (int i = 0; i < 4; i++) {
                if (i == closestIndex) continue;

                d = quads[i].bounds.distToPointSQ(x, y);

                if (d < closestInfo.dist) {
                    quads[i].getClosest(x, y, closestInfo);
                }

            }

        }

    }
    else {

        for (int i = 0; i < items.size(); i++) {

            T item = items.get(i);

            float dist = distSQ(x, y, getXY.x(item), getXY.y(item));

            if (dist < closestInfo.dist) {
                closestInfo.dist = dist;
                closestInfo.item = item;
                closestInfo.tree = this;
            }

        }
    }

}

// . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


class Closest {

    QuadTree<T> tree;
    T item;
    float dist = Float.MAX_VALUE;

}
clankill3r
quelle
ps Ich denke immer noch, dass es besser ist, einen kd-Baum oder so etwas zu verwenden, aber das könnte den Leuten helfen.
Clankill3r
Schauen Sie sich auch diese an: bl.ocks.org/llb4ll/8709363
clankill3r