Unterschied zwischen quadtree und der kd-Baum

Was ist der Unterschied zwischen einem quadtree und der kd-Baum? Ich verstehe, dass Sie split-Punkte in viele Dimensionen, aber ich verstehe nicht, warum wir Sie verwenden würden, einen über den anderen.
Ich brauche eine Struktur, die ermöglicht es mir, zu zählen, wie viele Punkte (2D-Punkte) sind in einer bestimmten region.
Grundsätzlich bin ich versucht, zu erkennen, Clustern von Punkten.

InformationsquelleAutor Mauricio Galindo | 2012-11-21
  1. 25

    Den Unterschied (algorithmisch) ist: in quadtrees, die Daten erreichen eines Knotens ist aufgeteilt in einen festen (2^d), gleich große Zellen, in der Erwägung, dass in kdtrees, werden die Daten aufgeteilt in zwei Regionen, basierend auf einigen Daten, Analysen (z.B. Mediane von einigen Koordinate). Quadtrees nicht gut skalieren zu hohen Maße, aufgrund der exponentiellen Abhängigkeit der dimension. Die Datenstrukturen unterscheiden sich auch in Ihrer Abfrage, Zeit, Komplexität.

    Da bist du interessiert in 2D-Punkte, die entweder an der Struktur der Daten kann für Sie arbeiten. KD-Bäume sind sehr einfach, die Abfrage reicht, und sind generell bevorzugt über quadtrees. Ich schlage vor, Sie verwenden Sie Sie.

    • Achtung: kd-Bäume, auch die Skala exponentiell in der Anzahl der Dimensionen. Der wesentliche Unterschied ist, kd-Bäume am Ende tiefer, aber schmaler.
    InformationsquelleAutor killogre
Schreibe einen Kommentar