индекс ближайших точек между двумя отсортированными массивами координат

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).

• Если они не разделяют х или у координат вы можете использовать теорему Пифагора для нахождения расстояния, как 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.

Надеюсь, это поможет!