JavaScrip求最近点对，使用分治法，假设坐标为[[-1,1],[-4,-1].[-3,1].[0,0],[1,2],[2,-2],[4,1]]

在JavaScript中，我们可以使用分治法解决这个问题，首先将给定的坐标集合分为两部分，然后递归地寻找每部分内的最近点对，最后再比较这两部分之间的最近点对。这里有一个简化版的实现思路：

function findClosestPoints(points) {
    if (points.length <= 1) return [];

    // 将点集一分为二
    const mid = Math.floor(points.length / 2);
    const leftPoints = points.slice(0, mid);
    const rightPoints = points.slice(mid);

    // 分别在左、右部分寻找最近点对
    const closestOnLeft = findClosestPairs(leftPoints);
    const closestOnRight = findClosestPairs(rightPoints);

    // 找出整个区间范围内的最优最近点对
    let closestIntersecting = [];
    for (let i = 0; i < closestOnLeft.length; i++) {
        for (let j = 0; j < closestOnRight.length; j++) {
            const dist = calculateDistance(closestOnLeft[i], closestOnRight[j]);
            if (!closestIntersecting || dist < closestIntersecting.distance) {
                closestIntersecting = { pair: [closestOnLeft[i], closestOnRight[j]], distance: dist };
            }
        }
    }

    return closestIntersecting ? [closestIntersecting.pair, closestIntersecting.distance] : null;
}

function findClosestPairs(points) {
    if (points.length <= 1) return [{ point: points[0], distance: 0 }];

    // 假设点集已经按x轴排序
    const sortedPoints = points.sort((a, b) => a[0] - b[0]);

    // 使用二分查找找到跨越中点的最接近对
    let left = 0, right = sortedPoints.length - 1;
    let closestPair = sortedPoints[left], minDist = calculateDistance(sortedPoints[left], sortedPoints[right]);

    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (compareDistances(sortedPoints[mid], closestPair)) {
            closestPair = sortedPoints[mid];
            minDist = calculateDistance(sortedPoints[mid], closestPair);
        } else {
            right = mid;
        }
    }

    return [{ point: closestPair, distance: minDist }];
}

function calculateDistance(p1, p2) {
    return Math.sqrt(Math.pow(p1[0] - p2[0], 2) + Math.pow(p1[1] - p2[1], 2));
}

function compareDistances(p, currentBest) {
    return calculateDistance(p, currentBest) < currentBest.distance;
}

// 测试数据
const points = [
    [-1, 1],
    [-4, -1],
    [-3, 1],
    [0, 0],
    [1, 2],
    [2, -2],
    [4, 1]
];

console.log(findClosestPoints(points)); // 输出最近点对及其距离

这个代码首先将点集分成两半，然后分别找出每部分的最优近似对，最后遍历这两个近似对，找出在整个集合范围内距离最小的对。