使用两个坐标之间的距离来处理最有效的方法是什么？

我有2063个位置存储在一个MySQL表中。在我的一个过程中，我需要根据距离给定源点有多远来排除某些结果。问题是，我需要一次筛选几百个，也许几千个结果。使用两个坐标之间的距离来处理最有效的方法是什么？

那么做距离数学的最好方法是什么？我应该在运行时间做它

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

或者我应该创建一个查找表，每个点和每个点之间的距离已经计算出来。我可以避免重复行，因为p1和p2之间的距离与p2和p1之间的距离相同，但是仍然会导致表中有几百万行。

或者..还有更好的方法吗？

来源

2009-05-26 gargantuan

尝试静态查找表...生成的可执行文件的大小应该是有趣的：d〜2063！ * 8个字节（对于每个结果的浮点数） – workmad3 2009-05-26 13:12:48

您可以使用MySQL的空间扩展来计算距离，甚至在数据上创建R-tree索引以优化某个范围内点的查找。

了MySQL空间扩展的文档的详细信息： http://dev.mysql.com/doc/refman/5.1-maria/en/spatial-extensions.html

来源

2009-05-26 13:07:10

如何：

 
1. Loop through all points: 
    2. If abs(a-b) < distance && abs(a-b) < distance then: 
    3. Do the fancy distance calculation between a and b.

即假设大多数点将在您感兴趣的距离定义的“框”之外，您可以用步骤2快速筛选出大多数点，并且只计算实际距离以获得更少的点数。

来源

2009-05-26 13:10:58 Makis

+1假设您的意思是在计算真实距离之前计算dx && dy kenny 2009-05-26 13:15:54

由于您的数据位于mysql表中，因此您确实需要SQL可以帮助您的解决方案。

我会假设每个位置都有一个x和y坐标。将它们作为单独的条目存储在表中。

您可以快速缩小您的搜索范围到一个以您的兴趣点为中心的框。如

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

一旦你有一个更小的集合有可能在范围之内的项目，你可以用一个更迭代的方法

编辑：避免平方根计算的工作出实际距离时虽然这些都很贵。例如，而不是

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

尝试

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

来源

2009-05-26 13:13:42

使用两个坐标之间的距离来处理最有效的方法是什么？

回答

相关问题