Nearest Neighbour Search in 3D Visualization
This application is designed to aid people with understanding nearest neighbour searches with K-D trees, Octrees and random projection trees in 3D. Your browser needs to support WebGL for the 3D rendering to work (supported on most modern browsers).
1. Pick the number of points to be generated:
2. Pick an algorithm:
3. Choose algorithm parameters:
Algorithm output:
Help
Algorithms
K-D tree is an algorithm that splits the data into 2 on one axis at each level. At each level, an axis is chosen, for example usingg the formula "axis = depth % 3". Then a random point in the current partition is taken and the partition is divided into 2 on the given axis. If the number of points in a partition is below a treshold, no more splits will occur. Nearest neighbour search works very similarly to octree's NN search.
Octree is a 3D version of quadtrees. The tree is built by checking the number of points in the current octant (a cube) and if it's bigger than a treshold, the octant will be split into 8 equal octants and the process is repeated recursively. For nearest neighbour search, the octant closest to searchable point is found. If it contains any points, it is set as current best. Then the algorithm recursively backtracks up the tree and checks other octants to see if they are in the radius to possibly contain closer neighbours. If so, the neighbouring octants are also checked. Once there are no octants that haven't been checked and could potentitally contain the nearest neighbour, the algorithm finishes.
Random Projection tree is built by picking 2 random points and building a perpendicular plane right between them. Then all points are split into 2 partitions depending on which side of the plane they are. This is repeated until each partition contains less than a given treshold number of points. Nearest neighbour search works by recursing down the stree to the partition containing the point. Then the point in that partition is set as current best and the algorithm goes back up the tree while checking at each level if any other partitions are in the radius to possibly contain better candidates. If so, those partitions are also checked. When there are no partitions left to check, the algorithm finishes with current best being the nearest neighbour.
Parameters
Max number of points in a space partition - All 3 algorithms split the space into subpartitions. This is the maximum number of points that are allowed in any one smallest leaf partition, otherwise the partition will be split into more subpartitions.
Do steps automatically - When ticked, after pressing generate the algorithm will do the visualization steps automatically at the given interval.
Automatic step interval - Time between automatic steps when "do steps automatically" is ticked.
Do next step - Can be used to do the next step in the algorithm if "do steps automatically" is unticked.
3D Nearest Neighbour Search by Andreas Sepp, Marko Täht, Diana Algma, Raul-Martin Rebane is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License .
