find if 4 points on a plane form a rectangle?

Question

Can somebody please show me in C-style pseudocode how to write a function (represent the points however you like) that returns true if 4-points (args to the function) form a rectangle, and false otherwise?

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

Solution 1

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

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 done with finite accuracy: e.g. abs(a-b) < 1E-6)

Solution 2

struct point
{
    int x, y;
}

// tests if angle abc is a right angle
int IsOrthogonal(point a, point b, point c)
{
    return (b.x - a.x) * (b.x - c.x) + (b.y - a.y) * (b.y - c.y) == 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 slightly more complicated 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);
}

Solution 3

1. Find all possible distances between given 4 points. (we will have 6 distances)
2. XOR all distances found in step #1
3. If the result after XORing is 0 then given 4 points are definitely vertices of a square or a rectangle otherwise, return false (given 4 points do not form a rectangle).
4. Now, to differentiate between square and rectangle 
   a. Find the largest distance out of 4 distances found in step #1. 
   b. Check if the largest distance / Math.sqrt (2) is equal to any other distance.
   c. If answer is No, then given four points form a rectangle otherwise they form a square.

Here, we are using geometric properties of rectangle/square and Bit Magic.

Rectangle properties in play

1. Opposite sides and diagonals of a rectangle are of equal length.
2. If the diagonal length of a rectangle is sqrt(2) times any of its length, then the rectangle is a square.

Bit Magic

1. XORing equal value numbers return 0.

Since distances between 4 corners of a rectangle will always form 3 pairs, one for diagonal and two for each side of different length, XORing all the values will return 0 for a rectangle.

Solution 4

• translate the quadrilateral so that one of its vertices now lies at the origin
• the three remaining points form three vectors from the origin
• one of them must represent the diagonal
• the other two must represent the sides
• by the parallelogram rule if the sides form the diagonal, we have a parallelogram
• if the sides form a right angle, it is a parallelogram with a right angle
• opposite angles of a parallelogram are equal
• consecutive angles of a parallelogram are supplementary
• therefore all angles are right angles
• it is a rectangle

• it is much more concise in code, though :-)

  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 to make it work with floating point values, please, do not just blindly replace the int declarations in the headers. It is bad practice. They are there for a reason. One should always work with some upper bound on the error when comparing floating point results.)

Solution 5

The distance from one point to the other 3 should form 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's 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

View more solutions

Comments

[Vlad]

@Larry: your test is only for being a parallelogram

[Vlad]

@Larry: with checking diagonals it's correct now, but your test requires taking 6 square roots.

[Vlad]

@Timmy: in that case one needs to do a more complicated check: if (IsOrthogonal(a, b, c)) return IsRectangle(a, b, c, d); else if (IsOrthogonal(a, b, d)) return IsRectangle(a, b, d, c); else return false;

[Vlad]

I modified the answer accordingly

[Timmy]

what if a and b is a diagonal?

[Harvey]

IsOrthogonal( (10,9), (15,9), (15,6) ) = 0 or False. (15-10)*(15-15)+(9-9)*(9-6)=0. Is there a ! missing?

[Platinum Azure]

I would never have thought of it... after a quick mental check, I do believe it works. +1

[rlbond]

This is a clever solution. It basically finds the circumcircle of the "rectangle" and verifies that all four corners are lie on it.

[Axel Gneiting]

This is VERY inefficient. Use the dot product method provided by Vlad. Squareroots need hundrets of clock cycles. Also the dot product method is more numerically stable.

[Brett Pontarelli]

@Axel & @Curd: Was the solution edited since it original posting? I don't see any square roots. I'm assuming sqr(x) == x*x which means ddi is actually the square of the distance from cx to xi. This should be pretty darn fast.

[milesmeow]

I think this is computationally the most efficient.

[Andras Vass]

You should check for m4 as well, else you may end up with a trapezoid.

[Curd]

@Axel Gneiting and Brett Pontarelli: I started the answer with the two first lines and then immediately added the code. From the beginning the code only contained the calculation of the square of the distances, no square roots (hence the variable name dd, instead of d). If the distances have to be equal, of course the square of the distances have to be equal too. I didn't think that this had to be mentioned.

[Admin]

This is correct, we can prove this using the fact that the line joining the midpoint of a chord and centre of circle is perpendicular to the chord. This method also works for degenerate rectangles.

[Axel Gneiting]

Okay, then I need to appologize. I thought sqr stands for squareroot.

[Carlos Gutiérrez]

@andras - Tested a few parallelograms and all evaluated as false. Are you thinking about a particular case?

[Curd]

Some considerations concerning performance: this solution takes 20 additions/subtractions/divisions by constant 4 and 8 multiplications. It even could be optimized to drop the remaining square distance calculations if the first or second comparison failed. So the numbers above are worst case. Even this worst case is as good as the best case and 3 times better than the worst case of the solution by Vlad.

[Andras Vass]

Suppose we have points x1=3, y1=3; x2=0, y2=0; x3=6, y3=0; x4=9, y4=3; Now d1 = 18; d2 = 18; d3 = 36; It's getting late, though. :-) Would you please check?

[Carlos Gutiérrez]

@andras - You're right, it looks like the test must be repeated using 3 of the points as start point.

[David Meister]

Ah, I just realised that this has that parallel-to-the axis problem. So instead of the if statements at the end it should test if (D == A + v + u). I also noticed that if you get the diagonal as one of your first 3 points it might give a false negative, so if the dot product fails it should redefine u as AD and try again.

[Andras Vass]

Concerning its speed: as it is tagged as an interview question, speed is probably secondary - and this is a clever solution.

[Andras Vass]

If you knew the order, then checking for |x| = |z|, |y| = |w| and one dot product would suffice. (Since opposite sides must be equal in length and then there are quite a few quadrilaterals with opposite sides equal in length.)

[Andras Vass]

@Vlad: Could you please explain the run-time complexity of your method in terms of arithmetic operations for the worst case just like @Curd did?

[Andras Vass]

please, do something about it then.

[Andras Vass]

Worst case: 15 additions/subtractions, 6 multiplications.

[Alexandre C.]

The hard part is to perform the comparison correctly. Simply testing for < 1e-16 is not enough (the sqr functions will ruin accucary). This requires careful analysis (and imho I doubt this question has any meaningful answer without extended precision arithmetic).

[Wolfy]

This does not seem to work for points (1,0),(-1,0),(0,1),(0,-1)

[Curd]

@Wolfy: Why do you think so?!? Center of mass is (0,0) and distance of center of mass to any of the 4 corners is 1.0 therefore test returns true.

[Jack Bashford]

Please ensure that your answer is actually an answer to the OP's question. He asked how to find out if points form a rectangle, not if they form a parallelogram. Also, one right angle does not ensure a rectangle.

[bob wong]

Ummm，one parallelogram with a right angle is a rectangle, so I believe it might work to verify it in the above two steps.

[Jack Bashford]

My bad sorry, I was thinking a different way.

[Ed Bordin]

cool idea but possibly impractical if you need to test equality with a small tolerance to account for float precision. also probably worth adding that the xor trick works because xor is commutative and associative

[Pedro Lopes]

If we have (1, 2), (1, 2), (10, 30), (10, 30), wont this algorithm return True? I believe the previously mentioned points do not form a valid rectangle.

[greybeard]

This seems to assume axis-aligned rectangle (as the question suggests, but doesn't specify explicitly). (Why four points as args if iso-oriented?)

[Curd]

@Pedro Lopes: why such a complicated example? What about (0, 0), (0, 0), (0, 0), (0, 0)? Well, it depends on the definition of rectangle. If rectangles of area 0 should be included it's ok. If not an additional test for area == 0 must be done.

[Pedro Lopes]

@greybeard 4 points are provided as arguments, as asked for in the question. Yes, the assumption here is that it is checking for a axis aligned rectangle. I will update the the answer with that remark

[Pedro Lopes]

@Curd Good point, I was thinking about an axis an aligned rectangle for my example.

[diegoide]

4.b. Why not just check if 4 distances are equal?

[Sumi]

Right triangles entered in order pass through this as rectangles. the isOrthogonal() method needs to be modified.

[Admin]

you don't have to use square root, just make sure the differences in x, y are equal that is all |x_n-center_x| and |y_n-center_y| are equal

[Masoud Darzi]

this is wrong, the last line must be d1^2 == d2^2+d3^2 or d2^2 == d1^2 + d3^2 or d3^2 == d1^2 + d2 ^2