Find if 4 points on a plane form a rectangle?

Question

Can someone please show me in the C-style pseudo-code how to write a function (represent points that you like) that returns true if 4-point (function arguments) form a rectangle, and false otherwise?

I came up with a solution that first tries to find 2 different pairs of points with equal x-value, and then this is for the y axis. But the code is quite long. Just curious to see what others have come up with.

Answer 1

• find the center of mass of the corner points: cx = (x1 + x2 + x3 + x4) / 4, cy = (y1 + y2 + y3 + y4) / 4
• if the square of the distances from the center to all four corners is

bool isRectangle(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4) { double cx,cy; double dd1,dd2,dd3,dd4; cx=(x1+x2+x3+x4)/4; cy=(y1+y2+y3+y4)/4; dd1=sqr(cx-x1)+sqr(cy-y1); dd2=sqr(cx-x2)+sqr(cy-y2); dd3=sqr(cx-x3)+sqr(cy-y3); dd4=sqr(cx-x4)+sqr(cy-y4); return dd1==dd2 && dd1==dd3 && dd1==dd4; } 

(Of course, in practice, testing for equality of two floating-point numbers a and b should be performed with finite precision: for example, abs (ab) <1E-6)

Answer 2

 struct point { int x, y; } // tests if angle abc is a right angle int IsOrthogonal(point a, point b, point c) { return (bx - ax) * (bx - cx) + (by - ay) * (by - cy) == 0; } int IsRectangle(point a, point b, point c, point d) { return IsOrthogonal(a, b, c) && IsOrthogonal(b, c, d) && IsOrthogonal(c, d, a); } 

If the order is not known in advance, we need a more complex check:

 int IsRectangleAnyOrder(point a, point b, point c, point d) { return IsRectangle(a, b, c, d) || IsRectangle(b, c, a, d) || IsRectangle(c, a, b, d); } 

Answer 3

• translate the quadrangle so that one of its vertices now lies at the origin
• the three remaining points form three vectors from the origin
• one of them should represent the diagonal
• the other two should represent the parties
• using the parallelogram rule , if the sides form a diagonal, we have a parallelogram
• if the sides form a right angle, this is a parallelogram with a right angle
• the opposite angles of the parallelogram are equal
• consecutive parallelogram angles are optional
• therefore all angles are right angles
• it's a rectangle

• this is much more succinct in code, but :-)

   static bool IsRectangle( int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4) { x2 -= x1; x3 -= x1; x4 -= x1; y2 -= y1; y3 -= y1; y4 -= y1; return (x2 + x3 == x4 && y2 + y3 == y4 && x2 * x3 == -y2 * y3) || (x2 + x4 == x3 && y2 + y4 == y3 && x2 * x4 == -y2 * y4) || (x3 + x4 == x2 && y3 + y4 == y2 && x3 * x4 == -y3 * y4); } 

• (If you want it to work with floating point values, don't just blindly replace int declarations in the headers. This is bad practice. They aren’t for some reason. You always need to work with some upper bound on the error when comparing floating point results .)

Answer 4

If points A, B, C and D, and you know the order, then you calculate the vectors:

x = BA, y = CB, z = DC and w = AD

Then we take the point products (x dot y), (y dot z), (z dot w) and (w dot x). If they are all zero, you have a rectangle.

Answer 5

The distance from one point to another 3 should be a right triangle:

 |  /// |
 |  /// |
 |  /// |
 | / ___ / ___ |

 d1 = sqrt( (x2-x1)^2 + (y2-y1)^2 ) d2 = sqrt( (x3-x1)^2 + (y3-y1)^2 ) d3 = sqrt( (x4-x1)^2 + (y4-y1)^2 ) if d1^2 == d2^2 + d3^2 then it a rectangle 

Simplifying:

 d1 = (x2-x1)^2 + (y2-y1)^2 d2 = (x3-x1)^2 + (y3-y1)^2 d3 = (x4-x1)^2 + (y4-y1)^2 if d1 == d2+d3 or d2 == d1+d3 or d3 == d1+d2 then return true 

Answer 6

We know that two stellar lines are perpendicular if the product of their slopes is -1, because the plane is given, we can find the slopes of three consecutive lines and then multiply them to check whether they are really perpendicular or not. Suppose we have lines L1, L2, L3. Now, if L1 is perpendicular to L2 and L2 is perpendicular to L3, then this is a rectangle and the slope is m (L1) * m (L2) = - 1 and m (L2) * m (L3) = -1, then this implies that it is a rectangle. The code is as follows

 bool isRectangle(double x1,double y1, double x2,double y2, double x3,double y3, double x4,double y4){ double m1,m2,m3; m1 = (y2-y1)/(x2-x1); m2 = (y2-y3)/(x2-x3); m3 = (y4-y3)/(x4-x3); if((m1*m2)==-1 && (m2*m3)==-1) return true; else return false; } 

Answer 7

accepting the exact product proposal one more step, check if two vectors made by any 3 point points are perpendicular, and then see if x and y correspond to the fourth point.

If you have points [Ax, Ay] [Bx, By] [Cx, Cy] [Dx, Dy]

vector v = BA vector u = CA

V (point) U / | V || and | == cos (theta)

therefore, if (vu == 0) there is a pair of perpendicular lines.

Actually, I don’t know C programming, but here is meta-programming for you: P

 if (v==[0,0] || u==[0,0] || u==v || D==A) {not a rectangle, not even a quadrilateral} var dot = (v1*u1 + v2*u2); //computes the "top half" of (vu/|v||u|) if (dot == 0) { //potentially a rectangle if true if (Dy==By && Dx==Cx){ is a rectangle } else if (Dx==Bx && Dy==Cy){ is a rectangle } } else {not a rectangle} 

there are no square roots in it, and there is no potential for division by zero. I noticed that people mention these issues in earlier posts, so I thought I was proposing an alternative.

So, computationally, you need four subtractions to get v and u, two multiplications, one addition, and you have to check somewhere between 1 and 7 equalities.

Perhaps I do this, but I vaguely remember reading somewhere that subtractions and multiplications are “faster” calculations. I assume that declaring variables / arrays and setting their values ​​is also pretty fast?

Sorry, I'm completely new to these kinds of things, so I would have liked some feedback from what I just wrote.

Edit: try this based on my comment below:

 A = [a1,a2]; B = [b1,b2]; C = [c1,c2]; D = [d1,d2]; u = (b1-a1,b2-a2); v = (c1-a1,c2-a2); if ( u==0 || v==0 || A==D || u==v) {!rectangle} // get the obvious out of the way var dot = u1*v1 + u2*v2; var pgram = [a1+u1+v1,a2+u2+v2] if (dot == 0 && pgram == D) {rectangle} // will be true 50% of the time if rectangle else if (pgram == D) { w = [d1-a1,d2-a2]; if (w1*u1 + w2*u2 == 0) {rectangle} //25% chance else if (w1*v1 + w2*v2 == 0) {rectangle} //25% chance else {!rectangle} } else {!rectangle}