algorithm - 确定给定半径算法内的点

Question

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

假设我们有 PointA 作为引用。问题是在给定半径内找到 PointA 周围的点(使用坐标)。我的方法是计算每个点的距离(毕达哥拉斯)，然后与给定的半径进行比较。我敢肯定，这在复杂性方面会很糟糕。

您可以推荐什么算法？ 指出问题的示例代码将不胜感激。谢谢。

Answer 1

首先，我会围绕圆圈创建一个框，然后首先测试框内是否有任何东西。那么你可能一直在避免计算 sqrts 和 squares。选择框的一条边(比如左侧的一条边)并计算其 x 值:

xMin = xOrigin - radius

然后任何满足的东西

xTest < xMin

可以忽略。对所有四个面重复类似的操作。测试失败的那一刻，就停止在那个点上工作。不要做不必要的计算。

这告诉您一个点很近，但不一定在半径内。接下来计算:

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

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

这是我能想到的最好的方法，首先对数据进行预结构化。