javascript - 两个排序的坐标数组之间最近点的索引

Question

我正在研究 javascript 中的优化问题。

我有两个数组:

dataset1 = [[x1,y1],[x2,y2],...,[xn,yn]]

dataset2 = [[z1,w1],[z2,w2],...,[zm,wm]]

dataset1 和dataset2 表示单调函数

x1 < x2 < ... < xn     (x coordinate)

z1 < z2 < ... < zm     (x coordinate)

和

y1 < y2 < ... < yn     (y coordinate)

w1 > w2 > ... > wm     (y coordinate)

因此，两个数据集的第一个坐标总是增加dataset1 的第二个坐标总是增加，dataset2 的第二个坐标总是减少。

我正在寻找一种快速的二元迭代算法来找到最近的两对坐标(两个单调函数的交集)。

有人知道怎么做吗？

Answer 1

据我了解，您有两个单调函数，一个向右增加，一个向右减少。

您的数组是排序点，因此每个数组都从最差的 x 坐标开始。

你可以做的是将第一个数组的每个点与第二个数组的每个点进行比较，并像这样存储一个对象:

//point
{
    pointIncreasing: [xj, yj],
    pointDecreasing: [zi, wi],
    distance : //distance between the points
}

然后计算你检查的距离:

• 两者是否共享相同的 x 或 y 坐标，在这种情况下距离为 Math.abs(xj-zi) 或 Math.abs(yj-wi) .

• 如果它们不共享 x 或 y 坐标，您可以使用毕达哥拉斯定理来计算距离，如 d = Math.sqrt(Math.pow(Math.abs(xj-zi) ,2) + Math.pow(Math.abs(yj-wi),2))

所以最后你会得到一个像这样的函数:

var results = [];
 function populateResults(fun1, fun2){
    for (var j = 0; j < fun1.length; j++){
        for (var i = 0; i< fun2.length; i++){
            var temp = {
                pointI : fun1[j],
                pointD : fun2[i],
                d : null
            }
            // do as said before, add some ifs, calculate distance
            // and do a temp.d = calculatedDistance

            // and add an if calculatedDistance == 0, to stop the
            // loop, because you got your intersection
            results.push(temp);
        }
    }

    results.sort(function(a, b){return (a.d - b.d);});
    // to sort your results array, not sure of order though...
}

然后您只需要获取 results[0] 就可以得到两个最近的点，或者如果 distance == 0 就是交点。

希望这对您有所帮助!