Stack Overflow
Stack Overflow

Questions tagged [kdtree]

A k-d-tree (k-dimensional tree) is a data structure for storing points in multidimensional space. They can be used to efficiently query for whether a point exists, as well as to do Euclidean nearest-neighbor searches and searches inside of hyperdimensional rectangular regions.

457 questions
98
votes
3 answers

What is the difference between a KD-tree and a R-tree?

I looked at the definition of KD-tree and R-tree. It seems to me that they are almost the same. What's the difference between a KD-tree and an R-tree?
zjffdu
  • 25,496
  • 45
  • 109
  • 159
55
votes
11 answers

KDTree Implementation in Java

I'm looking for a KDTree implementation in Java. I've done a google search and the results seem pretty haphazard. There are actually lots of results, but they're mostly just little one-off implementations, and I'd rather find something with a little…
benjismith
  • 16,559
  • 9
  • 57
  • 80
47
votes
4 answers

Difference between scipy.spatial.KDTree and scipy.spatial.cKDTree

What is the difference between these two algorithms?
Benjamin
  • 11,560
  • 13
  • 70
  • 119
35
votes
2 answers

Are Ana-/Catamorphisms just slower?

After writing this article I decided to put my money where my mouth is and started to convert a previous project of mine to use recursion-schemes. The data structure in question is a lazy kdtree. Please have a look at the implementations with…
fho
  • 6,787
  • 26
  • 71
31
votes
2 answers

Nearest Neighbor Search: Python

I have a 2 dimensional array: MyArray = array([6588252.24, 1933573.3, 212.79, 0, 0], [6588253.79, 1933602.89, 212.66, 0, 0], etc...) The first two elements MyArray[0] and MyArray[1] are the X and Y coordinates of…
Dlinet
  • 1,193
  • 3
  • 15
  • 22
30
votes
1 answer

Difference between quadtree and kd-tree

What is the main difference between a quadtree and kd-tree? I understand they split points in many dimensions, but I do not understand why we would use one over the other. I need a structure that allows me to count how many points (2D points) are in…
Mauricio Galindo
  • 638
  • 1
  • 10
  • 16
22
votes
1 answer

Is there any way to add points to KD tree implementation in Scipy

I have a set of points for which I want to construct KD Tree. After some time I want to add few more points to this KDTree periodically. Is there any way to do this in scipy implementation
gizgok
  • 7,303
  • 21
  • 79
  • 124
18
votes
3 answers

How does the KD-tree nearest neighbor search work?

I am looking at the Wikipedia page for KD trees. As an example, I implemented, in python, the algorithm for building a kd tree listed. The algorithm for doing KNN search with a KD tree, however, switches languages and isn't totally clear. The…
davea
  • 181
  • 1
  • 1
  • 4
17
votes
2 answers

nearest neighbor - k-d tree - wikipedia proof

On the wikipedia entry for k-d trees, an algorithm is presented for doing a nearest neighbor search on a k-d tree. What I don't understand is the explanation of step 3.2. How do you know there isn't a closer point just because the difference…
oob
  • 1,948
  • 3
  • 26
  • 48
16
votes
1 answer

Speed of K-Nearest-Neighbour build/search with SciKit-learn and SciPy

I have a large set of 2-dimensional points and want to be able to rapidly query the set for the k-Nearest-Neighbours of any point in the 2-d space. Since it's low-dimensional, a KD-Tree seems like a good way to go about it. My initial data set will…
StackG
  • 2,730
  • 5
  • 29
  • 45
16
votes
2 answers

KDTree for longitude/latitude

Are there any packages in Python that allow one to do kdtree-like operations for longitude/latitudes on the surface of a sphere? (this would need to take into account the spherical distances properly, as well as the wraparound in longitude).
astrofrog
  • 32,883
  • 32
  • 90
  • 131
15
votes
2 answers

KDTree Splitting

I am currently writing a KDTree for a physics engine (Hobby project). The KDTree does not contain points. Instead it contains Axis Aligned bounding boxes which bound the different objects in the environment. My problem is deciding on how to split…
shaleve
  • 153
  • 1
  • 1
  • 4
14
votes
3 answers

How to find the nearest neighbors for latitude and longitude point on python?

Input: point = (lat, long) places = [(lat1, long1), (lat2, long2), ..., (latN, longN)] count = L Output: neighbors = subset of places close to the point. (len(neighbors)=L) Question: Can I use kd-tree for quick nearest-neighbors lookup for points…
Andrei
  • 1,313
  • 4
  • 18
  • 35
13
votes
3 answers

How do I traverse a KDTree to find k nearest neighbors?

This question concerns the implementation of KNN searching of KDTrees. Traversal of a KDTree to find a single best match (nearest neighbor) is straightforward, akin to a modified binary search. How is the traversal modified to exhaustively and…
user2647513
  • 576
  • 1
  • 4
  • 13
13
votes
3 answers

kd-tree vs octree for 3d radius search

I'm trying to figure out which structure would be better for doing several radius search of points, a kd-tree or an octree? It was already mentioned in this question but there was no answer. It seems to me that since octrees have fixed sizes for the…
paghdv
  • 554
  • 1
  • 4
  • 14
1
2 3
…
30 31