Given four points, determine if it is a square, rectangle or none of them

Sunday fun day, here is a simple algorithm to find if given 4 points are forming up a square, rectangle or nothing!


Example square: [{"x":0, "y":2}, {"x":0, "y":4}, {"x":2, "y":2}, {"x":2, "y":4}]
Example rectangle: [{"x":0, "y":2}, {"x":0, "y":4}, {"x":3, "y":2}, {"x":3, "y":4}]
Example neither: [{"x":0, "y":3}, {"x":0, "y":5}, {"x":2, "y":2}, {"x":3, "y":4}]

function printItIsRectangleOrSquareOrNeither (points) {
  var distances = [];
  //1. Calculating distances between points O((n*(n-1))/2) ~O(n2)
  distances = calculateDistances(points);
  //2. Sorting distances heapsort, introsort O(nlogn)
  distances = sortDistances (distances);
  //3. Go over the sorted lengths and apply rules O(n)
  printResults (distances);
}
function printResults (distances) {
  if (distances[0] == distances[1] && distances[2] == distances[3] && distances[4] == distances[5]){
    if (distances[0] == distances[2]) {
      console.log('square');
    } else {
      console.log('rectangle');
    }
  } else {
    console.log('neither');
  }
}
function sortDistances (distances) {
  return distances.sort();
}
function calculateDistances (points) {
  var distances = [];
  for (var i = 0; i < points.length; i++) {
    for (var j = i+1; j < points.length; j++) {
      // Find distance, distance formula sqrt(pow(x1-x2,2) + pow(y1-y2,2))
      var pointA = points[i];
      var pointB = points[j];
      var distance = Math.sqrt(Math.pow(pointA.x - pointB.x, 2) + Math.pow(pointA.y-pointB.y, 2));
      distances.push(distance);
    }
  }
  return distances;
}

Comments

Popular posts from this blog

Configure hosts File in Android

Is Wharton Business Foundations Specialization Good?

iTunes cannot restore the iPhone because Find My iPhone is on and applications are gone!