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

Space Character Problem on IE 6, 7, and 8

Does Netflix work on iOS 5 Beta 4?

AWS encryption chart (SSE-S3 vs SSE-KMS vs SSE-C)