So vergleichen Sie Punkte zweier verschiedener Pfade (Punktarray)

Question

Ich muss die Punkte zweier verschiedener Pfade vergleichen, um festzustellen, ob sie sich ähneln.

Mein Problem ist, beide Wege haben unterschiedliche Startpunkte. Diese Pfade sind auch keine einfachen Rechtecke, daher glaube ich nicht, dass ich das Array basierend auf den kleinsten x- und y-Werten neu anordnen kann.

Ich habe dies versucht:

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; 
} 

Dies nicht zu funktionieren scheint. Ich weiß, dass diese beiden Wege sehr ähnlich sind und nur einen sehr kleinen Unterschied haben sollten. Aber der Unterschied, den ich zurückbekomme, sieht falsch aus, daher denke ich, dass der "Startpunkt" beider Punktarrays falsch ist. Irgendwelche Ideen ?

Hier ist ein JSFiddle mit meinem aktuellen Code: https://jsfiddle.net/thatOneGuy/5b3646zj/

Answer 1

Unter Ihrer neuesten Kommentare zu berücksichtigen, ich denke, das ist, was Sie brauchen:

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

Ein Hinweis über die Art

Sie können nicht sortiere die Punkte, indem du nur X (oder nur Y) vergleichst. Betrachten wir das folgende Beispiel:

Durch den Vergleich von X-Koordinaten können Sie klar sagen, dass P1 'nach' P0 und P2 ist. Sie benötigen jedoch eine zweite deterministische Sortierregel, wenn beide X-Koordinaten identisch sind, so dass Sie entscheiden können, ob P2 vor oder nach P0 liegt.

Zum Beispiel:

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 

Ohne die 2. Kriterium, das .sort() Methode würde zufällig alle Punkte der Reihenfolge, die die gleiche X-Koordinate haben.

(Vergleich X ersten und Y zweite ist nur eine Konvention. Es anders tun um genauso gut funktionieren würde, solange Sie die gleiche Methode für beide Pfade verwenden.)

Answer 2

Nur ein Beispiel, wie man identische Pfade mit verschiedenen Startpunkten vergleichen kann.

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