js寻找最近点对，使用分治法，代码实例

JavaScript中使用分治法解决最近点对问题（如Fermat's Two Point Problem），通常涉及将问题分解成较小的部分，然后递归地解决它们，最后合并结果。一个常见的方法是使用K-D Tree，但如果你只是想了解基本的分治思路，可以尝试使用暴力搜索结合剪枝策略。

这是一个简单的分治法解决方案，它不是最优的，但它能说明核心思想：

function findClosestPairs(points, k) {
    // 基线情况：如果k=0或没有点，返回空数组
    if (k === 0 || !points.length) return [];
    
    // 如果只有两个点，直接计算距离并返回
    if (points.length === 2) {
        const [a, b] = points;
        return [[a, b], distance(a, b)];
    }
    
    // 将点集随机分成两半，分别找最近点对
    const mid = Math.floor(points.length / 2);
    let leftPairs = findClosestPairs(points.slice(0, mid), Math.ceil(k / 2));
    let rightPairs = findClosestPairs(points.slice(mid), Math.floor(k / 2));

    // 合并结果
    return merge(leftPairs, rightPairs, points);
}

function merge(left, right, allPoints) {
    let result = [];

    // 比较每组左侧点对中的第一个点和右侧点对中的所有点
    for (const pair of left) {
        const [closestA, _] = pair;
        let closestDistance = Infinity;

        for (const point of right) {
            const dist = distance(closestA, point[1]);
            if (dist < closestDistance) {
                closestDistance = dist;
                result.push([closestA, point[1]]);
            }
        }

        // 更新剩余右侧点对中的最远点，避免重复比较
        for (let i = 0; i < right.length; ++i) {
            const dist = distance(closestA, right[i][1]);
            if (dist > closestDistance) {
                right[i] = [right[i][1], right[i][0]];
            }
        }
    }

    return result.concat(right);
}

// 辅助函数：计算两点之间的欧氏距离
function distance(pointA, pointB) {
    return Math.sqrt(Math.pow(pointA.x - pointB.x, 2) + Math.pow(pointA.y - pointB.y, 2));
}

// 示例用法
const points = [{x: 1, y: 3}, {x: 3, y: 1}, {x: 5, y: 5}, {x: -1, y: -2}];
const k = 2;
const closestPairs = findClosestPairs(points, k);
console.log("Closest pairs:", closestPairs);

请注意，此解决方案的时间复杂度较高，不适合大规模数据。对于实际应用，建议使用更为高效的K-D Tree或其他优化算法。