确定给定半径算法中的点

Question

我不确定这是什么数学概念来支持我的问题.^^

假设我们将PointA作为参考.问题是在给定半径内找到PointA周围的点(使用坐标).我的方法是计算每个点(毕达哥拉斯)的距离,然后与给定的半径进行比较.我确信这会让人觉得复杂.

您可以建议什么算法？我们非常感谢能够指出问题的示例代码.谢谢.

Answer 1

我首先在圆圈周围创建一个盒子,然后首先测试盒子里面是否有任何东西.然后你可能总是避免一直计算sqrts和square.选择框的一个边(比如左边的那个)并计算其x值:

xMin = xOrigin - radius

然后任何满足的东西

xTest < xMin

可以忽略.对所有四个方面重复类似的事情.测试失败的那一刻,然后停止工作.不要做不必要的计算.

这告诉您一个点接近但不一定在半径范围内.接下来计算:

abs(sqr(xOrigin - xTest) - sqr(yOrigin - yTest))

如果这小于半径*半径(您预先计算以避免使用平方根),那么您在半径内有一个点.

这是我能够首先预先构建数据的最佳方法.

Answer 2

如果你的点没有被索引，那实际上是一个最佳算法。有n 个点，在没有任何其他索引的情况下，搜索所有这些点需要 O( n ) 时间。

一个微观优化是跳过 sqrt 操作，并将坐标增量的平方和与所需半径的平方进行比较。

如果您要对同一数据集进行多次查询，则可以使用各种索引方案，这些方案需要一些时间来计算 (O(n log n))，但使查找速度更快 (O(m + log n)，其中 m是找到的点数。）

kd-trees可能是从这里开始的地方。