algorithm - How do I optimize searching for the nearest point?

For a little project of mine I'm trying to implement a space colonization algorithm in order to grow trees.

The current implementation of this algorithm works fine. But I have to optimize the whole thing in order to make it generate faster. I work with 1 to 300K of random attraction points to generate one tree, and it takes a lot of time to compute and compare distances between attraction points and tree node in order to keep only the closest treenode for an attraction point.

So I was wondering if some solutions exist (I know they must exist) in order to avoid the time loss looping on each tree node for each attraction point to find the closest... and so on until the tree is finished.

Answer

Spatial hashing, quadtrees or octrees can be used to find candidates for the nearest neighbour quickly: and then you can use the loop on that candidate set to get the actual nearest neighbour.

Initial Premature Optimization

• sqrt(n) > sqrt(y) if n > y and n > 0 and y > 0



• sqrt(n) < sqrt(y) if n < y and n > 0 and y > 0


• sqrt(n) = sqrt(y) if n = y and n > 0 and y > 0


• x*x + y*y > 0

This means you don't need to find the square roots of the distance squared (so compare dx*dx + dy*dy + dz*dz instead of sqrt(dx*dx + dy*dy + dz*dz)).

Spatial Hashing

1. Get the items in the bucket that contains the item you are interested in, as well as the buckets surrounding it (in 3D that would mean you would need to get the items in 9 buckets).


2. Eliminate the original item from the set.


3. Loop through those items and find the nearest neighbour.

Quadtree

Consider the following diagram of a 2D quadtree.

Basically "the check" means:

// numberOfPointsSeen is the number of points seen in quads so far.
if numberOfPointsSeen > 0 then
   return nearestNeighbourUsingLoop(numberOfPointsSeen)
else
   continueToNextConcentricSquare()

If you organise your quadtree so that each quadnode can only contain one item (this might not make sense in terms of memory usage though):

if currentQuadContainsItem then
   return itemInCurrentQuad
else
   continueSearching()