Fer*_*ndo 5 c graph depth-first-search closest-points
我知道这可能是重复的,但它似乎是"最近点对"算法的变体.
给定单位平方中的一组N个点(x,y)和距离d,找到所有点对,使得它们之间的距离最多为d.
对于大N,蛮力方法不是一种选择.除了"扫描线"和"分而治之"的方法,还有一个更简单的解决方案吗？这对点是无向图的边缘,我需要遍历它并说它是否连接(我已经使用DFS做过,但是当N = 100万时它永远不会完成!).
欢迎任何伪代码,评论或想法,谢谢!
编辑:我在Sedgewick上发现了这本书(我正在查看代码):
当N足够大时,程序3.18使用链接列表的二维数组来将程序3.7的运行时间提高约1/d2.它将单位正方形划分为大小相等的网格.然后,对于每个方格,它构建一个落入该方格的所有点的链表.二维阵列提供了立即访问靠近给定点的点集的能力; 链表提供了灵活性,可以存储它们可能落下的点,而不必提前知道每个网格方格中有多少点.
小智 2
我们实际上是在寻找以 (x,y) 为圆心、以 d 为半径的圆内部的点。
包围圆的正方形是以 (x,y) 为中心、边长为 2d 的正方形。这个方格之外的任何一点都不需要检查，就出局了。因此，如果abs(xa - x) > d 或abs (ya -yb) > d，则点a (xa, ya) 就出局。
同样，由该圆包围的正方形也是一个中心为 (x,y) 且对角线为 2d 的正方形。这个正方形之外的任何点都不需要检查，它就在。因此，如果 abs(xa - x) < (d * 1.412) 或 abs(ya -yb) < ( d * 1.412）。
这两个简单的规则结合起来大大减少了要检查的点的数量。如果我们按 x 对点进行排序，过滤可能的点，按 y 排序，我们就会找到真正需要计算完整距离的点。
| 归档时间： |
|
| 查看次数： |
837 次 |
| 最近记录： |