1

我在 mysql 表中存储了 2063 个位置。在我的一个过程中，我需要根据它们与给定原点的距离来排除某些结果。问题是，我需要一次过滤几百个甚至几千个结果。

那么进行距离数学的最佳方法是什么。我应该在运行时做吗

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 之间的距离相同，但这仍然会导致表中出现几百万行。

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

4

3 回答 3

4

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

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

于 2009-05-26T13:07:10.947 回答
1

这个怎么样：

1.遍历所有点：
  2. 如果 abs(ab) < 距离 && abs(ab) < 距离，则：
    3. 做a和b之间的花式距离计算。

即假设大多数点将在您感兴趣的距离定义的“框”之外，您可以通过步骤 2 非常快速地过滤掉大多数点，并且只计算少量点的实际距离。

于 2009-05-26T13:10:58.083 回答
1

由于您的数据位于 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-26T13:13:42.883 回答