TOC
给定一组在二维空间中的点(数量为 N)，如何快速找出最近的两点?
显然，可以通过遍历所有点之间的距离，然后直接选出这些距离之中的最小值，但是，这种方法需要遍历 n ^ 2 次 （等价于求 N 的 2 组合），也就说时间复杂为 O(n ^ 2).那么有没有更快的方法呢？
这里介绍一种复杂度等于 O(n logn) 的分治算法
起步
先给出一些基础代码，接下来不做解释
// 欧几里得距离
const getDistance = (a, b) => {
const xDiff = (a.x - b.x) ** 2
const yDiff = (a.y - b.y) ** 2
return Math.sqrt(xDiff + yDiff)
}
// 点
class Point {
constructor(x, y) {
this.x = x
this.y = y
}
}
首先，为了简单，我们假设 N = 2 ^ k 其中 K 为正整数，注意当 n = 2 的时候，毫无疑问，这时候的最近点就是这两个点。
在算法的开始，我们需要对所有的点进行两次快速排序 根据 X 位置从小到大排序 和 根据 Y 位置从小到大排序 , 这个排序只需要在一开始进行一次就可以。每次排序的复杂度为 O(n logn), 排序的结果在递归过程中我们会一直使用。
拆分
算法的核心在于将 问题 N 拆分成两个问题，每次问题都等于原来的问题的一半，也就是 n / 2 个点。 考虑在一个二维空间中，我们有 N 个点，接下来创建一条垂线 e 这个 e 刚好把我们的所有点按照 x 轴位置拆分成两半，e 的两边都有 n / 2 个节点。
假设我们对左边部分进行递归获取左边最近点对的距离 取得结果 ld 然后对右边也进行递归获得结果 rd，接下里我们取这两个距离里面最小的那个d = min(ld,rd),并且在 e - d 和 e + d 的位置上画两条垂线，如此一来，我们把我们的空间分成了三份， L + mid + R 也就是左边区域，中间的带状区域，右边的区域，这种情况下，最近点对的出现位置一共有三种可能。
- 两个节点都在左边区域
- 一个节点在左边一个在右边
- 两个节点都在右边
其中1,3假设都已经被我们递归解决，我们的问题就是要解决情况2，事实上，我们只需要检查刚才定义的 宽度为 2d 的 mid 带状区域内的节点，就能找出可能比 d 更小的节点。这是因为一旦超出这个区域，就算 Y 轴完全相等 ，他们之间的距离也一定超过了 d。
内部搜索
接下来我们需要把这个带状区域内的所有节点按照 Y 轴递增排序(这个操作我们一开始已经做过了，所以只需要利用一下进行选择即可，复杂度为 O(n))
从Y 排序最小的节点开始，我们连续检查带状区域内的每个点，计算所有比他其他比它 Y 轴更大的点直接的距离，尝试找出比 d 更小的点对。假设我们需要对节点 p 进行比较，我们考虑这样的一个空间，他是通过8个正方形(d/2 * d/2)组成的一个长方形，p 节点出于这个长方形的底边上，我们只需要判断这个区域内的所有节点即可，原因和上面的带状区域相同，一旦 Y 轴差超过 d ，就算 x 轴之差为0也大于我们的d,所以不可能找出比 d 距离更小的点对。
并且我们针对一个点，事实上只需要最多对比 7 次 就能找出所有可能小于 d 的点对，因为每个小格子内部只可能出现1个节点，因为当个小格子内部的极限距离为 d / sqrt(2),也就是正方形的对角线，但是这个距离显然小于 d, 如果这个正方形内部存在这样一个节点。那么之前对于 d 是 左右区域内最小的点对距离的定义直接被破坏了。所以不可能存在。
完整代码实现
// 欧几里得距离
const getDistance = (a, b) => {
const xDiff = (a.x - b.x) ** 2
const yDiff = (a.y - b.y) ** 2
return Math.sqrt(xDiff + yDiff)
}
class Point {
constructor(x, y) {
this.x = x
this.y = y
}
}
let sortedByXPointList = [] // 根据 X 位置从小到大排序
let sortedByYPointList = [] // 根据 Y 位置从小到大排序
function findRecentPoint(pointList) {
// 假设使用快排 注意 JS 的 sort 函数是一个原地排序并且有副作用的函数 所以用 slice 建立一份浅拷贝
sortedByXPointList = pointList.slice().sort((a, b) => a.x - b.x)
sortedByYPointList = pointList.slice().sort((a, b) => a.y - b.y)
return _findRecentPoint(0, pointList.length - 1)
}
function _findRecentPoint(p, q) {
if ((q - p) <= 1) { // 区域内只有两对节点 所以最近的节点必然为最近节点
return getDistance(sortedByXPointList[p], sortedByXPointList[q])
}
// 区间内的 X 中点
let middle = Math.floor((p + q) / 2)
let leftRecentDis = _findRecentPoint(p, middle)
let rightRecentDis = _findRecentPoint(middle + 1, q)
let d = Math.min(leftRecentDis, rightRecentDis) // 目前的最短距离
let e = sortedByXPointList[middle - 1].x + (sortedByXPointList[middle].x - sortedByXPointList[middle - 1].x) / 2 // 中心点
let insideLeftEdge = e - d
let insideRightEdge = e + d
// 接下来我们检查已 X 轴坐标 e 为中心点 从 e - d 开始 e + d 结束的带状区域内去检测最近点
// 我们从中筛选所有带状区域内的点，并按照 Y坐标 的递增排序进行排序
let insideSortedByYPointList = []
for (let point of sortedByYPointList) {
if (point.x >= insideLeftEdge && point.x <= insideRightEdge) {
insideSortedByYPointList.push(point)
}
}
// 开始对比节点 寻找是否比 d 更短
for (let i = 0; i < insideSortedByYPointList.length; i++) {
for (let j = 1; j <= 7; j++) {
if (!insideSortedByYPointList[i + j]) break
const dis = getDistance(insideSortedByYPointList[i], insideSortedByYPointList[i + j])
if (dis < d) {
d = dis // wow 我们从带状区域中找出来一个更近的
// 这里就简单打印一下
console.log(insideSortedByYPointList[i])
console.log(insideSortedByYPointList[i + j])
}
}
}
return d
}
const t = [new Point(3, 6), new Point(3, 4), new Point(1, 2), new Point(5, 6), new Point(7, 20), new Point(4, 8), new Point(8, 11), new Point(5.5, 5.5)]
console.log(findRecentPoint(t))
复杂度
每次拆解成两个子任务，并且每个子任务的规模为n/2，并且治理部分需要7n次比较
满足主方法 f(n) = 2f(n/2) + 7n = O(n logn) 并且我们有两次快排操作要加上两个O(n logn)
所以最终复杂度依然等于 O(n logn)
引用
- 离散数学及其应用(第三版)