What's the most efficient way to work with distances between two coordinates?
I have 2063 locations stored in a mysql table. In one of my processes, I need to exclude certain outcomes based on how far from a given point of origin. The problem is I will need to filter out a couple hundred, maybe a couple thousand results at a time.
So what would be the best way to do math from a distance. Should I do this at runtime
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 lookup table with the distances between each point already calculated. I can avoid duplicating rows as the distance between p1 and p2 will 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 to do this?
a source to share
You can use MySQL spatial extensions to calculate distance, and even create an R-tree index on the data to optimize your search for a point within a range.
See the docs for MySQL spatial extensions for details: http://dev.mysql.com/doc/refman/5.1-maria/en/spatial-extensions.html
a source to share
How about this:
1. Loop through all points:
2.If abs (ab) & lt distance && abs (ab) & lt distance then:
3. Do the fancy distance calculation between a and b.
those. assuming most points will be outside the range defined by the distance you are interested in, you can filter out most points very quickly from step 2 and only calculate the real distance for a much smaller number of points.
a source to share
Since your data is in a mysql table, you really need a solution that SQL can help you with.
I am assuming each location has an x and y coordinate. Save them as separate entries in the table.
You can quickly narrow your search down to a box focused 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 can be in range, you can use a more iterative approach.
Edit: Avoid square root calculations when working out actual distances, although they are expensive. for example, instead of
sqrt(x*x + y*y) < distance
try it
(x*x + y*y) < distance*distance
// distance*distance is a constant and can be calculated once
a source to share