[Tutor] Fastest (x,y) distance calculation

[Raymond Hettinger]

> I'm also considering creating some sort of data structure that aids in
> nearest-point calculating. Any suggestions?

Yes.

Divide the world wap in to a n-by-n grid (perhaps with n=20);
build a dictionary that mapping each intersection to a list of the
closesest temples (with the farthest being no more than a grid
step away from the nearest).

Then you search goes something like this:

def find_nearest_temple(self, pos):
     possibles = gridmapping[snap_to_grid(pos)]
     d, t = min([(abs(pos-temple.pos), temple) for temple in possibles])
     return t

In everyday language:  the way to find the closest temple is
to go the information booth at the center of your neighborhood
and ask for list of the closest temples.  Check each to see which
one is closest to your house.  If the temples are evenly distributed, 
you can gain a manyfold improvement in search time.


Raymond Hettinger