Euclidian Distance is the most common usage of distance. This distance is the “ordinary” straight line distance between two points.

Definition of the Euclidian Distance

The Euclidean distance between points p and q is the length of the line segment connecting them.
In Cartesian coordinates, if p = (p1, p2,…, pn) and q = (q1, q2,…, qn) are two points in Euclidean n-space, then the distance (d) from p to q, or from q to p is given by the Pythagorean formula:
d(p,q) = d(q,p) = \sqrt{(q_{1}-p_{1})^{2}+(q_{2}-p_{2})^{2}+...+(q_{n}-p_{n})^{2}} = \sqrt{\sum_{i=1}^{n}(q_{i}-p_{i})^{2}}

The above equation can be quite intimidating, so let’s take a look at some examples:

1-dimensional Distance

Assume two points in a one-dimension plane, point A(3) and point B(1).
Using the above equation we have:
d(A,B) = \sqrt{(A_{1}-B_{1})^{2}} = \sqrt{(3-1)^{2}} = \sqrt{(2)^{2}} = 2

2-dimensional Distance

Assume two points in a one-dimension plane, point A(3,1) and point B(1,7).
Using the above equation we have:
d(A,B) = \sqrt{(A_{1}-B_{1})^{2}+(A_{2}-B_{2})^{2}} = \sqrt{(3-1)^{2}+(1-7)^{2}} = \sqrt{(2)^{2} + (-6)^{2}} = \sqrt{40} = 6.324555

If we want more dimensions, then we just add the difference of the coordinates squared in the equation.

The EuclidianDistance Function

For the first part of our algorithm, we will take two arrays and calculate their Euclidian distance.

var euclideanDistance = function(pointA, pointB){

};

euclideanDistance([32,5], [8,22]);

The next step is to ensure that the arrays have the same length. If one of them has less elements than the other, we have to remove the values of the bigger array in order to match.

var euclideanDistance = function(pointA, pointB){
    // Get the size of the two lists.
    var lengthA = pointA.length;
    var lengthB = pointB.length;
    
    if(lengthA !== lengthB){
    	var counter = 0;
      
      //Truncate pointB
    	if(lengthA  lengthA; i--){
        	pointB.pop();	
          counter +=1;
        }
        console.log("Truncated pointB by "+counter+" elements.");
      }else{
      	//Truncate pointA
      	for(var i = lengthA; i > lengthB; i--){
        	pointA.pop();	
           counter +=1;
        }
        console.log("Truncated pointA by "+counter+" elements.");
      }
    }
};

euclideanDistance([32,5], [8,22]);

At this moment we have implemented a mechanism to bring the two points to the same coordinate system, that is to have the same number of elements in each array. First we get the number of elements in each array. Then we check if the sizes are equal. If an array is greater than the other, then we pop elements until they are the same.

This is achieved by a reverse for-loop. The starting position of our loop is the length of the greatest array. The end position is the length of the other array. Then we use a negative step, and pop elements until the two arrays are equal.

Now that our arrays are of the same length, we can calculate the distance of the objects they represent. Our next step is very simple. We need to calculate the sum of the squared differences of each coordinate. So we iterate the elements of each array with a for-loop, calculate the difference and square the result.

In order to calculate the square of the difference we use the Math.square function, which is a built-in JavaScript function for calculating powers.

var euclideanDistance = function(pointA, pointB){
   	// Get the size of the two lists.
    var lengthA = pointA.length;
    var lengthB = pointB.length;
    
    if(lengthA !== lengthB){
    	var counter = 0;
      
      //Truncate pointB
    	if(lengthA  lengthA; i--){
        	pointB.pop();	
          counter +=1;
        }
        console.log("Truncated pointB by "+counter+" elements.");
      }else{
      	//Truncate pointA
      	for(var i = lengthA; i > lengthB; i--){
        	pointA.pop();	
           counter +=1;
        }
        console.log("Truncated pointA by "+counter+" elements.");
      }
    }
    
    //Calculate the squared sum.
    var sum_squared = 0;
    for(var i = 0; i < pointA.length; i++){
    	sum_squared += Math.pow((pointA[i] - pointB[i]), 2);
    }
};

euclideanDistance([32,5], [8,22]);

The last step is to calculate the square root and we got the distance. We will use the Math.sqrt built-in JavaScript function to calculate the square root. Then we return the result.

var euclideanDistance = function(pointA, pointB){
   	// Get the size of the two lists.
    var lengthA = pointA.length;
    var lengthB = pointB.length;
    
    if(lengthA !== lengthB){
    	var counter = 0;
      
      //Truncate pointB
    	if(lengthA  lengthA; i--){
        	pointB.pop();	
          counter +=1;
        }
        console.log("Truncated pointB by "+counter+" elements.");
      }else{
      	//Truncate pointA
      	for(var i = lengthA; i > lengthB; i--){
        	pointA.pop();	
           counter +=1;
        }
        console.log("Truncated pointA by "+counter+" elements.");
      }
    }
    
    //Calculate the squared sum.
    var sum_squared = 0;
    for(var i = 0; i < pointA.length; i++){
    	sum_squared += Math.pow((pointA[i] - pointB[i]), 2);
    }

    //Calculate the square root of the sum.
    var distance = Math.sqrt(sum_squared);
    
    return distance;
};

euclideanDistance([32,5], [8,22]);

There might be more efficient, beautiful or crafty solutions out there. If you have suggestions on how to improve this code, let me know in the comments. You can find the full code of this post here. You can also find code from other posts in the site’s Github repo here.

Advertisements