Sudhakar Rayavaram
Problem solver (And maker),
Inquisitive (Root to most of my problems),
Software craftsman (Don't ask me for estimates)

Part of TarkaLabs

Technical Advisor for SportIndia

02 Nov 2008
Is it a rectangle?

Couple of days back when I was travelling back to home from office, I overheard two fellow employees discussing over a programming problem… “If four points in a 2D plane (x,y) is given, how to find whether it forms a rectangle or not?”. Question sounds simple right? Well, how would you program this solution? what will be the algorithm? Just give it a shot.

Check out my implementation below… It did not look this small and simple when I started solving it. Tried calculating angles between edges, tried equating edge lengths, tried rotating the skewed rectangles (special case), tried getting B.Sc. Maths degree first… But, all of these are not really needed for the solution… It is enough if you calculate the centroid and make sure all the 4 points are equi-distant from the centroid. Well, square also satisfies this logic and square is also a rectangle :)

I guess it is always hard to come up with a simple solution… You have to put lot of effort to think simple!

 1   public class RectangleValidator {
 2 
 3      public static boolean validate(Point p1, Point p2, Point p3, Point p4) {
 4          // Find the centroid using Euclid's geometric principle
 5          Point centroid = new Point();
 6          centroid.x = (p1.x + p2.x + p3.x + p4.x) / 4;
 7          centroid.y = (p1.y + p2.y + p3.y + p4.y) / 4;
 8 
 9          // Now check if the centroid is equi-distant from all the corners
10          double dist1 = getLength(p1, centroid);
11          double dist2 = getLength(p2, centroid);
12          double dist3 = getLength(p3, centroid);
13          double dist4 = getLength(p4, centroid);
14          return (dist1 == dist2 && dist2 == dist3 && dist3 == dist4 && dist4 == dist1);
15      }
16 
17      private static double getLength(Point p1, Point p2) {
18          // Using pythogoras theorem
19          double xDiff = Math.abs(p1.x - p2.x);
20          double yDiff = Math.abs(p1.y - p2.y);
21          return Math.sqrt((xDiff * xDiff) + (yDiff * yDiff));
22      }
23 
24      public static class Point {
25          Point() {
26          }
27 
28          Point(double x, double y) {
29              this.x = x;
30              this.y = y;
31          }
32 
33          double x;
34          double y;
35      }
36 
37   }