'Comparing 2D Paths for Similarity

I want to compare two 2D paths (arrays of points) for similarity, and, if possible, get a percentage of how similar the paths are (100% is identical, 0% completely different)

A path in this case is:

  • an ordered array, of zero or greater length, of coordinates (x, y)
  • continuous
  • basically a polyline

Paths may overlap and contain a different number of points. Position and scale doesn't matter, i.e. two otherwise identical paths can be far apart, and one can be smaller than the other, and they will be found to be the same.

The only criteria for similarity is the shape the paths make, and the order of the coordinates i.e. a vertical line drawn top to bottom is different to a vertical line drawn bottom to top (although the order is the least important, solutions are welcome without meeting that criteria).

So in the image below, the green path would be found to be identical to the black one, the blue one would be maybe ~80% similar, and the red path would be maybe <1% similar.

I've searched the web and can't find anything that quite fits my criteria and situation - ideally it's not going to be complex like neural networks.

paths

algorithm2dcoordinatessimilaritypolyline


Solution 1:[1]

I don't know but i have an idea that maybe could work.
Hows about scaling the 2 that going to be compared to the same ratio, overlay them each other and compare the points the path along to the end.
Then you could give Points maybe For the difference of the Points?
Like exact is 1 Point, diff < idk 10? is 0.5 points, and so on.
At the end you then could get the percentage from points reached

I hope i could give an Idea or smth

Solution 2:[2]

I suggest this function to solve the distance (the opposite of similarity that you search for ) between two paths from which you can infer the similarity from (1- distance), but before that you have to find a way to normalize the distance to be in the range [0,1], the logic behind this solution is as follows:

Starting from one of the two sets of points, we have to find the nearest point in the other set for each point in the set we started from, with this we will get the sum of the distances between convergent points. We do the same from the other set of points. https://ibb.co/K7SZZ3P

function distancepathpath(path1, path2) {
    let sum = 0;
    for (const i in path1) {
        let minDist = Number.MAX_SAFE_INTEGER;
        for (const j in path2) {
            let dist = Math.sqrt(Math.pow(path1[i].x - path2[j].x, 2) + Math.pow(path1[i].y - path2[j].y, 2))
            if (dist < minDist) minDist = dist;
        }
        sum += minDist
    }
    for (const i in path2) {
        let minDist = Number.MAX_SAFE_INTEGER;
        for (const j in path1) {
            let dist = Math.sqrt(Math.pow(path1[j].x - path2[i].x, 2) + Math.pow(path1[j].y - path2[i].y, 2))
            if (dist < minDist) minDist = dist;
        }
        sum += minDist
    }
    return sum / (path1.length * path2.length * 2);
}
console.log(distancepathpath(
    [
        { x: 10, y: 9 },
        { x: 2, y: 1 },
        { x: 4, y: 4 }
    ], [
        { x: 3, y: 7 },
        { x: 1, y: 1 },
        { x: 7, y: 4 },
        { x: 10, y: 9 },
        { x: 9, y: 1 },
        { x: 4, y: 6 }
    ]))

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 Nico Eggers
Solution 2 OMAR GHALAMOUN

Related Questions