KDTree

K-Dimensional tree for searching data

The KDTree facilitates the rapid querying of data stored in a FluidDataSet. It makes querying by distance much more efficient by first analysing a FluidDataSet and creating a data structure known as a k-d tree. As such, before the KDTree can be used you have to fit a FluidDataSet. This constructs the tree that can then be queried.

A common application of the KDTree is for performing nearest neighbour lookups. The interactive example below contains a collection of data points ranging between 0.0 and 1.0 which are then plotted on to a canvas like a scatterplot. Using the coordinates of our mouse in the square, we can search for the point, or group of points closest to our mouse. We can also control the radius constraints of the search, meaning only points within a certain distance, and not just whatever is closest, are returned. Before you use the example you will have to fit the underlying KDTree by pressing the button labelled fit.

Number of Neighbours: 1
1 50
Radius: 0
0 1

You can change the number of neighbours and the radius constraint with the sliders at the bottom. Points that are highlighted with a red square are those that are deemed to be the nearest neighbours, given both the number of neighbours and radius constraint. Even if points fall outside the radius, a line will be drawn to them. Notice how working with both constraints can help you to hone in on different neighbourhoods of points. For example, by using a large number of neighbours (50) and a small radius (0.1) you can ensure that if there are actually 50 very nearby points they will be returned, but only if they are within a tight proximity to the query (your mouse).


Last modified: Sat Nov 27 13 by James Bradbury
Commit: 340e5d Edit File on GitHub