二维空间最近点对算法C++实现与测试

"这篇资源是关于二维空间内最近点对算法的C++实现，主要涉及数据结构、排序和搜索算法。作者使用了CLION作为测试环境，并通过随机生成点对来验证算法。" 在计算机科学中，求解最近点对问题是几何算法中的一个经典问题，尤其是在大数据集的情况下。这个问题要求在给定的一组二维点中找到距离最近的两个点。这个任务在图像处理、数据挖掘和计算几何等领域有广泛的应用。 在这个C++实现中，首先定义了一个名为`Point`的结构体，用于存储点的坐标信息，包括`x`和`y`两个成员变量。接着，`getPoint`函数用于生成随机点对，利用`srand`和`rand`函数在`[-100,100)`区间内生成随机坐标，然后除以100得到`[-1,1)`范围内的浮点数，再乘以100使范围扩大到`[-100,100)`。 `Distance`函数采用欧几里得距离公式计算两点之间的距离，即`sqrt((x2-x1)^2 + (y2-y1)^2)`。在寻找最近点对的过程中，首先对点集进行排序，这里使用了自定义的`cmp`函数，按照`x`坐标升序排列。 核心算法是递归的`findClose`函数。该函数使用分治策略来降低问题的复杂度。当点的数量小于2时，直接返回一个较大的默认值，表示没有点对；如果只有2个点，直接计算并返回它们的距离。对于更大的点集，它将点集一分为二，然后分别在两个子集中寻找最近点对。这个过程会递归地进行，直到子集只包含一个点为止。在每次划分过程中，中间值（`mid`）用于比较两个子集中的点对，以确定是否跨越中线的点对可能是全局最近点对。 在递归调用中，`d1`和`d2`分别记录了两个子集的最小距离，`a1`、`b1`、`a2`和`b2`则分别保存了这两个最小距离对应的点对。通过比较这两个子集的最小距离和跨越中线的点对的距离，可以找到全局的最近点对。 这种基于排序的分治算法，通常称为“分而治之”或“平面分割”方法，其时间复杂度为O(n log n)，优于简单的平方根查找方法，后者的时间复杂度为O(n^2)。在处理大量点时，这种优化显得尤为重要。不过，对于更高效的方法，如扫线算法或kd树等数据结构，可以在特定情况下提供更好的性能。