What is the most efficient way to work with distances between two coordinates?

Question

I have 2063 locations stored in a mysql table. In one of my processes I need to exclude certain results based on how far away they are from a given point of origin. The problem is, I will need to filter a couple of hundred, maybe a couple of thousand results at a time.

So what would be the best way to do the distance math. Should I do it at run time

1. Find all points connecting to my point of origin
2. loops through the connecting points
3. calculate the distance between the point of origin and the connecting point
4. exclude the connecting point if the distance if too great

or should I create a look up table with the distances between each and every point already figured out. I can avoid duplicate rows since the distance between p1 and p2 would be the same as the distance between p2 and p1, but that would still result in a couple of million rows in the table.

Or.. is there an even better way of doing it?

Answer 1

You could use MySQL's spatial extensions to calculate the distance and even create an R-tree index on the data to optimize the lookup of point within some range.

See the docs for MySQL spatial extensions for details: http://dev.mysql.com/doc/refman/5.1-maria/en/spatial-extensions.html

Answer 2

Since your data is in a mysql table, you really want a solution that SQL will be able to help you with.

I will assume that each location has an x and y coordinate. Store these as separate entries in the table.

You can quickly narrow your field of search to a box centered on your point of interest. eg

WHERE X > (MyPosX - Range) AND X < MyPosX + Range) 
AND Y > (MyPosY - Range) AND Y < MyPosY + Range)

Once you have a smaller set of items that are likely to be in range, you can use a more iterative approach

Edit: Avoid square root calculations when working out the actual distances though, as these are expensive. eg instead of

sqrt(x*x + y*y) < distance

try

(x*x + y*y) < distance*distance    
// distance*distance is a constant and can be calculated once