Nearest point uses a very slow algorithm

[sancarn]

Looking at the source code for nearest point, this uses an incredibly slow algorithm, O(n^2) when wanting to find nearest points of one dataset to another. This should really be implemented as a quadtree or k-tree:

var tree = generateNearestTree(dataset1, dataset2)
var nearestNeighbours = tree.nearestTo(dataset1[0], numberOfNearest) //Array with nearest at index 0

[drewdaemon]

@sancarn I think this is a good idea, but I'm not sure I understand how the existing algorithm is O(n^2). It appears to be a simple loop through the vertices of the geometry which would put it at O(n), n being the number of vertices.

I believe this proposal would put a nearestTo lookup at O(log n). Since building the tree in the first place is O(n log n), it seems to me that this an improvement only if there are to be multiple nearestTo lookups on the same geometry.

If that's right, it might be worth having both options available. Definitely let me know if I missed something.