1. Zuhause
  2. Frage und Antwort
  3. Nächster Nachbar Suche in D3

Nächster Nachbar Suche in D3

2012-09-25 8 views
7

Ich habe eine 2-dimensionale k-d tree in Javascript (check it out on GitHub) implementiert, und ich verwende es für Nearest-Neighbor-Suche neben D3.Nächster Nachbar Suche in D3

Ich habe gelernt, dass es gibt a quadtree implementation in D3, aber auch festgestellt, dass die API-Dokumentation ist spärlich und Google-Suchen sind nicht fruchtbar. Ich würde lieber eine weit gereiste Bibliothek als mein eigenes neu erfundenes Rad benutzen, wenn möglich.

Wie führen Sie einen nächsten Nachbarn suchen mit D3 Quadtree? Mit dem nächsten Nachbarn, meine ich:

  • Füllen Sie die Quadtree mit 2-dimensionalen Punkten
  • Suche nach dem Quadtree-contained Punkt am nächsten an einen neuen Punkt, die nicht unbedingt in der Quadtree existiert

Quelle

2012-09-25 Jacob Marble

+0

Aus Neugier und nichts Oder wofür verwenden Sie einen JS KD Tree? –

+0

@Sajjan Ich habe s in einem und auf mousemove der Kreis, der der Mausposition am nächsten ist, wird hervorgehoben. Es ist sehr glatt und skaliert gut, da die Suche nach dem nächsten Nachbarn in einem zweidimensionalen K-D-Baum O (log n) ist. –

+0

Cool! Wäre es möglich, Ihren Code zu teilen (außer natürlich, es ist proprietär oder privat), ich denke, ich könnte viel daraus lernen. –

Antwort

4

Die Bürstendemonstration findet nicht den nächsten Nachbarn, sondern findet Quadtree-Punkte in einem gegebenen Rechteck. (Versuchen Sie ein leeres Rechteck Bürsten und es muss nicht unbedingt seine nächsten Nachbarn besuchen.)

ich ein Beispiel gegabelt, die effizient die nächsten Nachbarn in der Quadtree zu einem beliebigen Punkt findet - siehe http://bl.ocks.org/patricksurry/6478178

Quelle

2013-09-07 22:50:03 patricksurry

Verwandte Themen

 Verwandte Themen