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