2016-08-09 348 views
0

Ich muss die Punkte zweier verschiedener Pfade vergleichen, um festzustellen, ob sie sich ähneln.So vergleichen Sie Punkte zweier verschiedener Pfade (Punktarray)

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/

+0

Sie könnten versuchen, neu zu berechnen beide Pfade, als würden sie von 0,0 ausgehen, indem sie den ersten Punkt des Pfades von allen Punkten im Pfad subtrahieren. Dann sollte die JSON.stringify-Version beider Pfade identisch sein, wenn sie die exakt gleiche Form haben. – Shilly

+0

@Silly sind Sie in der Lage, ein Beispiel zu geben, da ich nicht sehen kann, wie das funktionieren würde, da beide Pfade unterschiedliche Startpunkte haben – thatOneGuy

+1

Bitte definieren Sie 'ähnliche Pfade' genauer. Möchten Sie testen, ob Pfad # 2 eine exakte Übersetzung von Pfad # 1 ist? Oder möchten Sie eine Art Ähnlichkeits-Score berechnen? – Arnauld

Antwort

2

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

+0

Das sieht gut aus, aber ich denke, es gibt ein kleines Problem in der Art. Wenn Sie sich meine Geige und die Funktion orderPoints ansehen. Ich bekomme den Index des kleinsten X-Wertes und benutze das, um das Pfadarray neu aufzubauen. Hoffe ich erkläre das gut, sagen wir habe ein Array 1,2,3,4,5 und Index 3 ist der Punkt an dem ich anfangen möchte, ich ordne mein Array so an wie es 3,4,5,1,2 ist Ich muss die gleiche Reihenfolge beibehalten, damit der Pfad korrekt gezeichnet wird. Ist das sinnvoll ? Wenn Sie sich die Konsolenprotokolle hier ansehen: https://jsfiddle.net/thatOneGuy/b97tvxc1/ müssen die letzten zwei Punkte getauscht werden (denke ich) – thatOneGuy

+0

@thatOneGuy Ich habe gerade eine Notiz über die Art in meiner Antwort hinzugefügt . Bitte lassen Sie mich wissen, wenn das Sinn macht. – Arnauld

+0

Ich denke das macht Sinn. Willst du sagen, dass die Reihenfolge gleich ist? (dh ein anderer Startpunkt, aber die Reihenfolge ist der gleiche) wie ich nicht verstehe, wie es gleich bleibt, wenn das der Fall ist – thatOneGuy

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 
+0

Entschuldigung, ich denke ich habe das falsch erklärt. Ich denke, dass Ihr Code überprüft, ob es die gleiche Form hat, ich brauche es, um zu sehen, ob es in der gleichen Position ist – thatOneGuy

+0

Euh, was meinst du? Position ist, wo es auf dem xy-Gitter no ist? Zwei Pfade haben nur die gleiche Position, wenn alle ihre Punkte gleich sind und wenn sie die gleiche Form haben. Dies überprüft tatsächlich, ob sie die gleiche Form haben, egal wo sie beginnen, solange sie sich im selben Quadranten des xy Gitters befinden. (Es prüft nicht auf gespiegelte Pfade) – Shilly

+0

Ja, aber die Daten für Ihren Code sind in Ordnung, d. H. Das erste Element in Pfad1 entspricht dem ersten in Pfad2 und so weiter. Meins ist ungeordnet und was ich brauche, ist eine Möglichkeit zu überprüfen, welche x- und y-Koordinaten in Pfad 1 denen in Pfad2 entsprechen. So kann ich dann die verschiedenen Punkte in den Punkten – thatOneGuy