[Tutor] Fastest (x,y) distance calculation

[Raymond Hettinger]

> My Game class has the following method, called by each Mover during its
> thinking phase. (non-pygamers: centerx and centery are the x & y values at
> the center of the rect)
> 
> ###
> class Game:
>     ...
>     def get_nearest_temple(self, pos):
>         distances = [((pos[0] - tmp.rect.centerx) ** 2 +
>                       (pos[1] - tmp.rect.centery) ** 2,
>                       tmp) for tmp in self.temples]
> 
>         return min(distances)[1]
>     ...
> 
> ###
> 
> It's basically taking advantage of the fact that:
>     distance = sqrt((x2 - x1)^2 + (y2 - y1)^2)
> And for integer x & y values, I can square the right side of the equation
> for purposes of distance comoparison.
> 
> I can't think of a better algorithm for getting the nearest object than
> this. Profile tells me this is one of the slower parts of my code. Any
> thoughts/suggestions?

Distance calculations are much cheaper if you store the coordinates
as complex numbers and use abs().

Also consider grouping the temples into neighborhoods so that
the search can be limited to the local and adjacent neighborhoods.
To find your closest grocery store, one doesn't have to search the world.

    

Raymond Hettinger


#################################################################
#################################################################
#################################################################
#####
#####
#####
#################################################################
#################################################################
#################################################################