Question

I've got my implementation of a k-d tree working with given points. For example, I can add points to the tree and then find the nearest point to given x, y coordinates, which is great.

I want to extend this to work with rectangles, for example a user gives an x and a y coordinate, a width and a height, I then want to be able to do a range query and nearest neighbour searches on this structure. How would I go about extending the current tree that I had to work with rectangular data?

No correct solution

OTHER TIPS

K-d trees are great for low dimensional point data. For anything consisting out of multiple points (lines, rectangles, etc) I would suggest using an R-tree.

I know a great extension of k-d trees to handle rectangles. It is called Box Sort algorithm and can be found here Box sort. The idea is pretty much the same as k-d trees. The paper has also an implementation in Pascal, but the translation to Java should be straightforward.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top