Add-on: Creating a chain of objects, nearest neighbor approximation

In a previous article I started with a very naive solution to create a chain of objects that have a parent-child relation along the shortest path.

This naive solution works but is so slow that even for 10 objects it starts getting unworkable. So the improved version uses a simplistic nearest neighbor approximation that works well with even thousands of objects. It has one drawback, you have to make sure that the active object is at one of the ends of the collection of selected objects because that is where our algorithm starts. This works quite well for artistic use, but in the future I might still try to add the Chistofides algorithm to make it more general.

Anyway, the code is simple enough and the relevant function is shown below:

def object_list2(objects, active=0):
 """
 Return an approximate shortest path through objects starting at the
 active index using the nearest neighbor heuristic.
 """

 s = time()

 # calculate a kd tree to quickly answer nearest neighbor queries
 kd = kdtree.KDTree(len(objects))
 for i, ob in enumerate(objects):
  kd.insert(ob.location, i)
 kd.balance()

 current = objects[active]
 chain = [current]  # we start at the chosen object
 added = {active}
 for i in range(1,len(objects)):  # we know how many objects to add
  # when looking for the nearest neighbor we start with two neigbors
  # (because we include the object itself in the search) and if
  # the other neigbors is not yet in the chain we add it, otherwise
  # we expand our search to a maximum of the total number of objects
  for n in range(2,len(objects)):
   neighbors = { index for _,index,_ in kd.find_n(current.location, n) }
   neighbors -= added
   if neighbors:  # strictly speaking we shoudl assert that len(neighbors) == 1
    chain.extend(objects[i] for i in neighbors)
    added |= neighbors
    break
  current = chain[-1]

 print("{n:d} objects {t:.1f}s".format(t=time()-s, n=len(objects)))

 return chain

Code availability

The full improved version is available on the same GitHub location. (click 'Raw' to download the Python file)