6 ms·
Why not just use a kd tree or voroni?
by theoracle101 10y ago
Why not just use a kd tree or voroni?
- jeena 10y agoHow would you learn how to implement that algorythm if you'd just use an existing implementation?
- UK-AL 10y agoImplementing a spatial tree is not the same as implementing Nearest neighbours. It's just a data structure to allow efficient culling.
- AReallyGoodName 10y agoRead the wiki page on it, run through the psuedocode on pen and paper a few times and then implement it. Source: I did this when I wrote a library for reverse geocoding which uses a kd tree. https://github.com/AReallyGoodName/OfflineReverseGeocode https://github.com/AReallyGoodName/OfflineReverseGeocode
- Scea91 10y agoOne reason is that the implementations are much more difficult. In k-d trees you have to deal with the distance from hyperrectangles. It is not something you would write in 30 minutes. Also k-d trees don't scale much in higher dimensions (https://docs.scipy.org/doc/scipy-0.14.0/reference/generated/scipy.spatial.KDTree.html https://docs.scipy.org/doc/scipy-0.14.0/reference/generated/...) so in large dimensional problems (the article says 20 is already large) the naive linear search tends to be actually faster. Voronoi is even worse in dimensions larger than 2.