How do I optimize searching for the nearest point?

Question

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 1

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()

Answer 2

Sorry I haven't read the linked document. This is how I understand your problem: you have some random points (attraction points) and given a node on your tree, you're trying to find the nearest attraction point? You don't say if this is 2D or 3D but here are a couple tips.

• The square root. A simple one to implement, don't use the square root when computing an comparing distances. Simply compare each squared value against each other. Square root calculations are expensive. Avoiding 300k of them can save time.

• Spacial partitioning. The simplest, QuadTree (for 2D) and OcTree (for 3D). These systems will help you search only the attraction points in a certain area, i.e. the area around your tree node of interest.

• More advanced spacial partitioning. The R-Tree this is supposedly the preferred spacial indexing method. If I remember correctly, a few of the major database systems have a version of R-Tree implemented for their databases. And kd trees, are good, and I believe are optimized for retival instead of insertions, so if you had static attraction points, this may be good.

• Even more resources. There's always Wikipedia coming to the rescue.