Index of the closest points between two sorted arrays of coordinates
I am working on an optimization problem in javascript.
I have two arrays:
dataset1 = [[x1,y1],[x2,y2],...,[xn,yn]]
dataset2 = [[z1,w1],[z2,w2],...,[zm,wm]]
dataset1
and dataset2
represent monotone functions
x1 < x2 < ... < xn (x coordinate)
z1 < z2 < ... < zm (x coordinate)
and
y1 < y2 < ... < yn (y coordinate)
w1 > w2 > ... > wm (y coordinate)
Therefore, the first coordinate of both datasets is always increasing. The second coordinate is dataset1
always increasing, and the second coordinate is dataset2
always decreasing.
I'm looking for a fast binary iterative algorithm to find the two closest pairs of coordinates (intersection of two monotone functions).
Does anyone know how to do this?
source to share
As I understand it, you have two monotone functions, one of which increases to the right and the other increases to the right.
Your arrays are sorted point by point, thus starting at the lowest x
coordinate for each one.
What you can do is compare every point of the first array with every point of the second array and store an object like this:
//point
{
pointIncreasing: [xj, yj],
pointDecreasing: [zi, wi],
distance : //distance between the points
}
And then calculate the distance traveled:
-
Whether the two have the same x or y coordinates, in which case the distance
Math.abs(xj-zi)
orMath.abs(yj-wi)
. -
If they do not share the x or y coordinates, you can use the Pythagorean theorem to find the distance as
d = Math.sqrt(Math.pow(Math.abs(xj-zi),2) + Math.pow(Math.abs(yj-wi),2))
So at the end you will end up with a function like this:
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...
}
And then you just need to take results[0]
, and you have two of your closest points or intersection, if distance == 0
.
Hope this helps!
source to share