javascript - 如何比较两条不同路径的点(点数组)

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坐标，您可以清楚地看出P1在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

如果没有第二个标准，.sort() 方法将对具有相同 X 坐标的所有点进行随机排序。

(先比较 X，然后比较 Y 只是一种惯例。只要对两条路径使用相同的方法，反之亦然。)