我不确定这是什么数学概念来支持我的问题。^^
假设我们有 PointA 作为参考。问题是在给定半径内找到 PointA 周围的点（使用坐标）。我的方法是计算每个点的距离（毕达哥拉斯），然后与给定的半径进行比较。我确信这在复杂性方面会很糟糕。
你可以建议什么算法？一个指出事情的示例代码将不胜感激。谢谢。
问问题
7306 次
4 回答
7
我首先在圆圈周围创建一个盒子，然后首先测试盒子内是否有任何东西。那么你可能一直在避免计算 sqrts 和 squares。选择盒子的一个边缘（比如左边的那个）并计算它的 x 值：
xMin = xOrigin - radius
然后任何满足
xTest < xMin
可以忽略。对所有四个面重复类似的操作。测试失败的那一刻，然后停止在该点上工作。不要做不必要的计算。
这告诉您一个点很近，但不一定在半径内。接下来计算：
abs(sqr(xOrigin - xTest) - sqr(yOrigin - yTest))
如果这小于半径 * 半径（您预先计算以避免使用平方根），那么您在半径内有一个点。
这是我能想到的最好的数据，首先是预先构建数据。
于 2010-10-15T04:38:47.073 回答
3
如果您的点没有被索引，那实际上是一个最佳算法。有n 个点，在没有任何其他索引的情况下，搜索所有点需要 O( n ) 时间。
一种微优化是跳过 sqrt 操作并将坐标增量的平方和与所需半径的平方进行比较。
如果您要对同一个数据集进行多个查询，您可以使用各种索引方案，这些方案需要一些时间来计算 (O(n log n))，但可以加快查找速度 (O(m + log n)，其中 m是找到的点数。）
kd-trees可能是从那里开始的地方。
于 2010-10-15T04:23:34.840 回答
1
您在这里唯一的复杂性是距离的计算。只需筛选并简化该计算，您就是最佳选择。
如果您的“中心”是 A(x,y)，那么对于任何点 B(x1, y1)，请考虑：
1/ 如果 B 在您要求的点 B 的距离 d 内，那么它遵循x-x1 < d和y-y1 < d。首先检查这些条件以过滤任何“低悬的果实”排除。
2/不是计算距离，而是计算距离的平方并将其与最大允许距离的平方进行比较（您显然应该预先计算和参考，而不是每次都重新计算）。这意味着不必为每个点计算平方根。
这些都是很小的优化，但假设这些点是未排序的和随机的，这是你能得到的最好的。
于 2010-10-15T04:45:09.640 回答
1
最好的答案取决于维度的数量。我假设您在 2D 或 3D 空间中工作。
一种简单的方法是制作单元格大小的统一网格，例如“R”。然后将所有点固定到各自的单元格。
每个查询点只与少数几个单元格相交，比如 9 个。然后，您只需要检查相交的单元格。
一种更有效的方法是构建四叉树或 KD-tree（还有很多其他选项，但对于 2D，quadree 或 KD-tree 可以）。
分层结构需要检查圆-矩形相交，但这在 KD-Tree 最近邻算法中有描述（您只需要稍微修改它）。
如果您真的关心性能，可以构建多个网格（移动或旋转）并始终选择单元格最集中在该点上的一个，以便将搜索限制在最少数量的单元格上。
于 2016-02-13T21:59:38.973 回答