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}]
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