# 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.

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.

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

• The quadtree / octree solution seems to be the one I will implement. But as I understand it, the starting point HAS TO BE at the center of a quad. In my case I have to test the closest treenode for every random attraction point... so if I want my attraction point to be at the center of a quad, I will have to set up a new quad tree for each attraction point. Won't it cost too much? Or maybe I missunderstood something :/ – lvictorino Apr 13 '12 at 7:51
• @Rootosaurus yeah you are misunderstanding it. All your points would be contained in the octree and you check each neighbouring cube in order. Because your points are not moving you can actually pre-calculate the entire tree: my explanation might suck a little so I really recommend some Googling and you will quickly see how they apply to your scenario (they are usually used for collision detection to avoid the O(N^2) you are seeing). – Jonathan Dickinson Apr 13 '12 at 10:51
• Pretty good answer, but I'm still wondering, how exactly to you explore quads in a concentric order? – jokoon May 19 '16 at 23:31

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.

• Since this is a generation algorithm for leaves on a tree, it is very likely to be 3D. – Myrddin Emrys Apr 12 '12 at 14:44
• In fact I'm trying to find the nearest tree node for every attraction points, not the nearest attraction point for every tree node... – lvictorino Apr 13 '12 at 7:52
• Works either way, it's up to you what you put into the partitioning trees. – MichaelHouse Apr 13 '12 at 8:00