Levenshtein distance is a measure of the similarity between two strings, string 's' (the source) and string 't' (the target). The distance is the sum of deletions, insertions, or substitutions required to transform s into t. By also transforming coordinates to direction numbers which then can be seen as a sequence (string) once can calculate the distance between a shape drawn by the user and a saved, target shape.
getDirection2D will transform a vector into a single number representing a direction which then can be chained into a sequence
function getDirection2D( center, relative )
{
//right side
if( center.x < relative.x )
{
if( center.y > relative.y )
{
return 7;
}
if( center.y < relative.y )
{
return 1;
}
return 0;
}
//left side
else if( center.x > relative.x )
{
if( center.y > relative.y )
{
return 5;
}
if( center.y < relative.y )
{
return 3;
}
return 4;
}
// center
else
{
if( center.y > relative.y )
{
return 6;
}
if( center.y < relative.y )
{
return 2;
}
return -1;
}
}
The Levenshtein distance distance calculation between two strings
function getLevenshteinDistance( a, b )
{
if( a == null || b == null )
{
console.log( "Strings for Levenshtein distance must not be null" );
return null;
}
const m = a.length;
const n = b.length;
var i;
var j;
var matrix = [];
for( i = 0; i <= m; ++i )
{
var line = [];
for( j = 0; j <= n; ++j )
{
line.push( ( ( i != 0 ) ? 0 : j ) )
}
line[ 0 ] = i;
matrix.push( line );
}
for( i = 1; i <= m; ++i )
{
for( j = 1; j <= n; ++j )
{
var cost = ( a.charAt( i - 1 ) == b.charAt( j - 1 ) ) ? 0 : 1;
matrix[ i ][ j ] = Math.min( Math.min( matrix[ i - 1 ][ j ] + 1, matrix[ i ][ j - 1 ] + 1 ), matrix[ i - 1 ][ j - 1 ] + cost
);
}
}
return matrix[ m ][ n ];
}