Как сравнить точки двух разных путей (массив точек)

Question

Мне нужно сравнить точки двух разных путей, чтобы увидеть, похожи ли они.

Моя проблема в том, что оба пути имеют разные отправные точки. Эти пути также не являются простыми прямоугольниками, поэтому я не думаю, что могу изменить порядок массива на основе наименьших значений x и y.

Я попытался это:

function orderPoints(points) { 
    var smallestX; 
    var smallestY; 
    var smallestIndex; 

    for (var i = 0; i < points.length; i++) { 
    if (!smallestX) { 
     smallestX = points[i].x; 
     smallestIndex = i; 
     smallestY = points[i].y; 
    } else { 
     if (points[i].x < smallestX && points[i].y < smallestY) { 
     smallestX = points[i].x; 
     smallestY = points[i].y; 
     smallestIndex = i; 
     } 
    } 
    } 

    //reorder array 
    var newArray = []; 
    for (var i = smallestIndex; i < points.length; i++) { 
    newArray.push(points[i]) 
    } 

    for (var i = 0; i < smallestIndex; i++) { 
    newArray.push(points[i]) 
    } 
    //console.log(newArray) 
    return newArray; 
} 

Это не похоже на работу. Я знаю, что эти два пути очень похожи и должны только иметь небольшую разницу. Но разница, которую я получаю, выглядит некорректной, поэтому я думаю, что «начальная точка» обоих точечных массивов неверна. Есть идеи ?

Вот JSFiddle с моим текущим кодом: https://jsfiddle.net/thatOneGuy/5b3646zj/

Answer 1

Принимая ваши последние комментарии во внимание, я думаю, что это то, что вам нужно:

var path1 = [ 
 
    { "x": 1.0265, "y": 2.4715 }, { "x": 5.4865, "y": 2.4715 }, 
 
    { "x": 5.5615, "y": 2.3965 }, { "x": 5.5615, "y": 0.2965 }, 
 
    { "x": 5.4865, "y": 0.2215 }, { "x": 1.0265, "y": 0.2215 }, 
 
    { "x": 0.9515, "y": 0.2965 }, { "x": 0.9515, "y": 2.3965 } 
 
]; 
 
var path2 = [ 
 
    { "x": 5.5615, "y": 0.2965 }, { "x": 5.5615, "y": 2.3965 }, 
 
    { "x": 5.4865, "y": 2.4715 }, { "x": 1.0265, "y": 2.4715 }, 
 
    { "x": 0.9515, "y": 2.3965 }, { "x": 0.9515, "y": 0.2965 }, 
 
    { "x": 1.0265, "y": 0.2215 }, { "x": 5.4865, "y": 0.2215 } 
 
]; 
 

 
function pathDifference(p1, p2) { 
 
    // abort early if the paths have different lengths 
 
    if(p1.length != p2.length) { 
 
    return false; 
 
    } 
 

 
    // sort points in each path 
 
    [ p1, p2 ].forEach(function(p) { 
 
    p.sort(function(a, b) { 
 
     return a.x < b.x || (a.x == b.x && a.y < b.y) ? -1 : 1; 
 
    }); 
 
    }); 
 

 
    // build array of {dx, dy} differences between the 2 paths 
 
    return p1.map(function(p, i) { 
 
    return { dx: p2[i].x - p.x, dy: p2[i].y - p.y }; 
 
    }); 
 
} 
 

 
console.log(pathDifference(path1, path2));

примечание о роде

Вы не можете сортируйте точки, сравнивая только X (или только Y). Давайте рассмотрим следующий пример:

P0 = (7, 9), P1 = (12, 3), P2 = (7, 5) 

Сравнивая координаты X, вы можете четко сказать, что Р1 «после» P0 и P2. Но вам нужно второе правило детерминированного сортировки, когда обе координаты X одинаковы, так что вы можете решить, находится ли P2 до или после P0.

Например:

if X0 < X1 then P0 is before P1 
if X0 > X1 then P0 is after P1 
if X0 == X1 AND Y0 < Y1 then P0 is before P1 
if X0 == X1 AND Y0 > Y1 then P0 is after P1 

Без 2-го критерия, метод .sort() будет случайным образом упорядочить все точки, которые имеют тот же X координат.

(Сравнение X первого и второго Y это просто условность. Делая это наоборот будет работать так же хорошо, до тех пор, как вы используете один и тот же метод для обоих путей.)

Answer 2

Просто пример того, как можно было бы сравнить одинаковые пути с различными начальными точками.

var path1 = [ 
     {'x' : 5, 'y' : 10}, 
     {'x' : 3, 'y' : 8}, 
     {'x' : 9, 'y' : 14}, 
     {'x' : 7, 'y' : 25} 
    ], 
    path2 = [ 
     {'x' : 11, 'y' : 16}, 
     {'x' : 9, 'y' : 14}, 
     {'x' : 15, 'y' : 20}, 
     {'x' : 13, 'y' : 31}   
    ], 
    normalize = function normalize(path) { 
     var centerX = path[0].x, 
      centerY = path[0].y; 
     return path.map(function(point) { 
      point.x -= centerX; 
      point.y -= centerY; 
      return point; 
     }); 
    }, 
    normalizedPath1 = normalize(path1), // [{"x":0,"y":0},{"x":-2,"y":-2},{"x":4,"y":4},{"x":2,"y":15}] 
    normalizedPath2 = normalize(path2); // [{"x":0,"y":0},{"x":-2,"y":-2},{"x":4,"y":4},{"x":2,"y":15}] 
console.log(JSON.stringify(normalizedPath1) === JSON.stringify(normalizedPath2)); // true