确定给定半径算法内的点

我不确定这是支持我的问题的数学概念。 ^^确定给定半径算法内的点

假设我们有PointA作为参考。问题是在给定的半径范围内找到PointA周围的点（使用坐标）。我的方法是计算每个点的距离（毕达哥拉斯），然后与给定的半径进行比较。我敢肯定，这会让人感到复杂。

你可能会建议什么算法？一个示例代码来指出事情将不胜感激。谢谢。

2010-10-15 jeff

你想要一个函数返回距给定坐标对小于一定距离的整数坐标对吗？或者你有一组浮动的物体，你想知道哪些是在半径内？ – 2010-10-15 04:09:38

你可能想看看这个SO回答：http://stackoverflow.com/questions/1318595/which-data-structure-is-appropriate-to-query-all-points-within-distance-d-from-p – 2010-10-15 04:10:25

如果你的积分没有编入索引，那实际上是一个最佳算法。有个点，并且它将花费O（ n）时间搜索所有它们，在没有任何其他索引的情况下。

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

如果您打算针对同一数据集进行多个查询，则可以使用各种需要一些时间才能计算的索引方案（O（n log n）），但要加快查找速度（ O（m + log n），其中m是找到的点数。）

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

来源

2010-10-15 04:23:34 Anonymous

我想补充一点，如果您确信坐标都小于sqrt（DBL_MAX），那么您只能跳过sqrt操作，这通常是这种情况。计算欧几里得距离的数值稳定方式不会溢出，除非产生的距离溢出。 – 2010-10-15 06:29:54

@匿名我知道这是一个古老的问题..但你会如何索引这些点？谢谢。 – RegUser 2015-06-19 14:38:05

我会先在圆圈周围创建一个盒子，然后首先测试盒子里是否有东西。那么你可能总是避免计算sqrt和square。拾取框（说一个在左侧）的一个边缘并计算其x值：

xMin = xOrigin - radius

然后任何satifies

xTest < xMin

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

这告诉你一个点很接近但不一定在半径内。接着计算：

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

如果小于半径*半径（你预先计算，以避免使用平方根），那么你有半径范围内的点。

这是我第一次预先构建数据时可以得出的最好结果。

来源

2010-10-15 04:38:47

这里唯一的复杂性就是距离的计算。只需筛选并简化计算，您就是最佳选择。

如果您的 '中心' 是A（X，Y），则对任意点B（X1，Y1）考虑：

1 /如果B是B点的您的要求的距离d之内，那么它遵循即x-x1 < d和y-y1 < d。首先检查这些条件以过滤任何'低挂水果'排除。 2 /不是计算距离，而是计算距离的平方，并将其与最大允许距离的平方（应明显预先计算和参考，而不是每次重新计算）进行比较。这意味着不必为每个点计算平方根。

这些都是非常小的优化，但假设点未排序和随机这是最好的，你会得到。

来源

2010-10-15 04:45:09

最佳答案取决于尺寸的数量。我假设你在二维或三维空间工作。

一个简单的方法是制作一个单元格大小均匀的网格，比如r。然后将所有点分别存储到其各自的单元格

每个查询点只与少数几个单元相交，比如说9个。然后您只需要检查相交单元。

更有效的方法是构建四叉树或KD树（除2D，四叉树或KD树之外，还有很多其他选项）。

检查圆形矩形交集对于层次结构是必需的，但是这在KD-Tree最近邻算法中描述（您只需稍微修改它）。

如果您真的关注性能，可以构建多个网格（移位或旋转），并始终选择最靠近该点的单元格，以便搜索限于最少的单元格数。

来源

2016-02-13 21:59:38 Libor

确定给定半径算法内的点

回答

相关问题