已知点间距离，如何通过算法定位三维目标坐标？

初始设定与已有代码 #

已知三维起点为start(0, 0, 0)，目标点r(x, y, z)的x、y、z均为1-100的随机整数。已实现计算两点间距离的calculateDistance函数，相关代码如下：

const r = [];
for (let i = 0; i < 3; i++) {
    r.push(Math.floor(Math.random() * 100) + 1); // 生成随机目标点r
}

const s = [0, 0, 0];
let distance;

function calculateDistance(random, myPoint) {
    distance = Math.abs(
                    Math.floor(
                        Math.sqrt(
                            Math.pow((random[0] - myPoint[0]), 2) +
                            Math.pow((random[1] - myPoint[1]), 2) + 
                            Math.pow((random[2] - myPoint[2]), 2)
                        )
                    )
                    );
    return distance;
}

当前searchPoint实现问题 #

当前尝试编写的searchPoint函数通过遍历调整起点坐标并调用距离函数来寻找目标点，但存在明显缺陷：

function searchPoint(distance) {
    let min = 173,   // 目标点(100,100,100)时的最大可能距离
        tempArr = [],
        closePoints = [],
        prev;

    for (let i = 0; i < s.length; i++) {
        while (s[i] < 100) {  // 遍历起点的x/y/z所有可能值
            prev = min; // 记录上一轮的最小距离值                              
            if (min > distance) {
                min = distance;
            }
    
            if (prev < distance) { // 距离增大则认为偏离目标，中断遍历
                break;
            }

            tempArr.push({distance, point: s[i]});  // 保存距离-坐标对
            s[i]++;
            distance = calculateDistance(r, s);
        }
        closePoints.push(tempArr.filter(obj => obj.distance === min)); // 筛选每个维度的最小距离对应坐标
        tempArr = [];
        min = 173;
    }

    let mappedPoints = closePoints.map(arr => {
        let mid = Math.floor((arr.length - 1) / 2); // 取候选数组中间元素作为近似值
        return arr[mid];
    });
    console.log(mappedPoints);
    mappedPoints.forEach((obj, i) => s[i] = obj.point); 

    console.log(s);
    console.log(calculateDistance(r, s));

    if (calculateDistance(r, s) === 0) {            // 距离为0则判定找到目标点
        console.log('Point was found!!!');
    }
}

该实现的核心问题：

• 当目标点坐标为边界值（如<14或>86）时，候选坐标数组中的目标值不在中间位置，取中间元素会定位错误
• 存在多个候选坐标对应同一最小距离的情况，无法精准定位到目标点

最优解决算法：逐维度二分查找 #

由于三维距离公式中，每个维度的坐标对距离的影响是独立的单调变化（当固定另外两个维度时，调整当前维度坐标，距离会先递减到最小值，再递增），因此可以对每个维度单独使用二分查找来精准定位目标坐标，步骤如下：

1. 对每个维度（x、y、z）依次进行二分查找，固定另外两个维度为当前已确定的最优值
2. 每次查找中，比较中间位置与相邻位置的距离，判断目标坐标在左侧还是右侧区间
3. 逐步缩小查找范围，直到找到使距离最小的坐标（即目标点的对应维度值）
4. 循环处理三个维度，直到整体距离为0

实现代码如下：

function searchPoint() {
    // 逐个维度进行二分查找
    for (let dim = 0; dim < 3; dim++) {
        let left = 0;
        let right = 100;
        let bestCoord = s[dim];
        let minDist = calculateDistance(r, s);

        while (left <= right) {
            const mid = Math.floor((left + right) / 2);
            // 临时修改当前维度坐标
            s[dim] = mid;
            const currentDist = calculateDistance(r, s);

            // 更新最优坐标
            if (currentDist < minDist) {
                minDist = currentDist;
                bestCoord = mid;
            }

            // 判断搜索方向：如果mid右侧距离更小，说明目标在右侧
            s[dim] = mid + 1;
            const rightDist = calculateDistance(r, s);
            if (rightDist < currentDist) {
                left = mid + 1;
            } else {
                // 否则目标在左侧
                right = mid - 1;
            }
        }

        // 将当前维度设为找到的最优坐标
        s[dim] = bestCoord;
        // 如果已经找到目标点，提前结束
        if (calculateDistance(r, s) === 0) break;
    }

    console.log('找到的点:', s);
    console.log('最终距离:', calculateDistance(r, s));
    if (calculateDistance(r, s) === 0) {
        console.log('Point was found!!!');
    }
}

算法优势 #

• 精准定位：二分查找直接锁定使距离最小的坐标，避免了边界值和多候选点的定位错误
• 高效性：每个维度的查找复杂度为O(log 100)，整体复杂度远低于原遍历实现的O(100)
• 鲁棒性：无论目标点处于任何位置（包括边界），都能准确找到对应坐标

内容的提问来源于stack exchange，提问作者Oleksandr Kulibaba