Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Assume I have 4 points (they are 2-dimension), which are different from each other, and I want to know whether they form a square. How to do it? (let the process be as simple as possible.)

share|improve this question
2  
I take it you'd need to account for rotated squares? –  Martijn Pieters Nov 23 '12 at 12:59
    
Do you have information about the order of the points at all? I.e. can you tell whether two points are adjacent, or form a diagonal? (this info can be used to simplify the process) –  Daniel B Nov 23 '12 at 13:53
1  
@DanielB No other information. It just like I have a white paper and draw 4 points on it randomly. Then I want to know whether they form a square. –  meshuai Nov 23 '12 at 14:05
2  
Particularly if the points are represented as floating point numbers, it is useful to include a sense of "tolerance" in any of the comparisons suggested below. Exact equality checks can fail for the results of floating point operations, even when we humans would consider them "close enough." –  Stephan A. Terre Nov 29 '12 at 22:40
    
This smells like a homework question. Not that there's anything wrong with that. :/ whathaveyoutried.com –  Jim G. Dec 2 '12 at 23:56
show 2 more comments

9 Answers 9

up vote 50 down vote accepted

Assuming that your square might be rotated against whatever coordinates system you have in place, you can't rely on there being any repetition of X and Y values in your four points.

What you can do is calculate the distances between each of the four points. If you find the following to be true, you have a square:

  1. There are two points, say A and C which are distance x from each other, and two other points, say B and D which are also distance x from each other.

  2. Each point {A, B, C, D} is an equal distance from the two points which aren't x away. i.e.: If A is x away from C, then it will be z away from both B and D.

Incidentally, the distance z will have to be SQRT((x^2)/2), but you don't need to confirm this. If conditions 1 and 2 are true then you have a square. NOTE: Some people are concerned about the inefficiency of square root. I didn't say that you should do this calculation, I just said that if you did you would get a predictable result!

Illustration of Square Rules

The bare minimum of work that you would need to do would be to pick a point, say A and calculate the distance to each of the other three points. If you can find that A is x from one point and z from two other points, then you just need to check those two other points against each other. If they are also x from each other then you have a square. i.e.:

  • AB = z
  • AC = x
  • AD = z

Since AB = AD, check BD:

  • BD = x

Just to be sure, you need to check the other sides: BC and CD.

  • BC = z
  • CD = z

Since AC = BD and AC = BC = CD, therefore this a square.

Along the way, if you find more than two distinct edge distances then the figure cannot be a square, so you can stop looking.


EDIT: Working Example Implementation

Since there is confusion about what the algorithm is, I have created a working example on jsfiddle (see here). In my explanation of the algorithm, I use arbitrary points A, B, C, and D. Those arbitrary points happen to be in a certain order for the sake of walking through the example. The algorithm works even if the points are in a different order, however, the example doesn't necessarily work if those points are in a different order.


Thanks to: meshuai, Blrfl, MSalters and Bart van Ingen Schenau for useful comments to improve this answer.

share|improve this answer
14  
You can short-circuit this process and not worry about how the points are ordered by measuring the distance between them and keeping track of the number of unique distances you find. Once you exceed two (Joel's x and z), the figure isn't a square. –  Blrfl Nov 23 '12 at 13:36
1  
the bare min, I don't think it works. At last, you say "it doesn't matter which one, either BC or CD". But if I just check one of them, the figure perhaps is a special Parallelogram. –  meshuai Nov 23 '12 at 13:46
2  
Another optimisation would be to compare the squared distances, instead of the distances. –  Baqueta Nov 23 '12 at 14:03
3  
@Blrfl: Your test doesn't work. Let ABCD be a diamond with AB=BC=CD=DA=1, AC=1 too (short diagonal), then AD~1.7 (long diagonal)/ You have only two lengths x and z, yet the figure is not a square. –  MSalters Nov 23 '12 at 14:23
2  
@JoelBrown: It is possible to create a trapezium shape with the diagonals AC = BD = x, the sides AB = BC = AD = z and the last side CD = y != z. –  Bart van Ingen Schenau Nov 23 '12 at 14:38
show 17 more comments

Pick three of the four points.

Figure out if it's a right isosceles triangle by checking if one of the three vectors between points is equal to another one rotated by 90 degrees.

If so, compute the fourth point by vector addition and compare it to the given fourth point.

Note that this doesn't require expensive square roots, not even multiplication.

share|improve this answer
    
One of the two good answers. Don't use sqrt unless crucial! You don't need to degrade integer calculations to FP... not to mention worsen the precision of the FP computation. –  K.Steff Nov 23 '12 at 19:16
    
thx. a good one. –  meshuai Nov 24 '12 at 5:46
    
Now that's the right way to do it. Multiplication is indeed not needed here. –  COME FROM Nov 29 '12 at 11:06
add comment

I'm sorry but some answers don't apply.

For the case you measure 3 edges (let's say AB, AC and AD) to find that two have the same size (let's say AC and AD) and one is bigger (let's say AB). Then you would measure CD to see if it's the same size of AB, and you find that it is. Instead of a square, you could have the picture below, and that makes it a wrong solution.

Not a square...

Then you try some other solution: measure all the distances at least once: AB, AC, AD, BC, BD, CD. Then you find that 4 of then are equal, and the other 2 are also equal among themselves. But you could just have a picture like below:

And that's not a square, too...

So, those answers aren't correct, despite the high upvotes they received.

One possible solution: if the two equal measures don't connect the same point. So: if AB and CD are the same lenght, all the other combinations (AC, AD, BC, BD) are also equal, you have a square. If you have the same point making the biggest length (AB and AC is the biggest, and all the others are equal), you have one of the pictures above.

share|improve this answer
    
no, his algorithm said the 2 edges of distances x do not share a point. but you just share C. So, assume A-C is x, then B-D should be another x instead of your B-C. –  meshuai Nov 23 '12 at 15:15
add comment

I think the easiest solution is the following:

  • First, calculate the center of the 4 points: center = (A + B + C + D)/4

  • Then calculate the vector A - center. Let this be v := (x,y)

  • Let v2 be the vector v rotated by 90 degrees: v2 := (-y, x)

  • Now the other points should be center - v, center + v2 and center - v2.

The advantage of this solution is that you don't have to use square roots at all.

share|improve this answer
1  
Yeah. This is the most comprehensible and probably the easiest to implement as well. –  Eric G Nov 30 '12 at 17:39
add comment

Let the four points have coordinate vectors a, b, c, d.

Then lets call their differences w=(a-d), x=(b-a), y=(c-b), z=(d-c).

Then w is orthogonal to a if you can create w from a by a 90-degree-rotation. Mathematically the 90-degree-rotation-matrix in 2-space is ( ( 0, -1 ), ( 1, 0 ) ). Thus, the condition whether w is a 90-degree-rotated a results in

( w_1 == -x_2 and w_2 == x_1 )

If this holds, then you need to check that w == -y and x == -z, or

( ( w_1 == -y_1 and w_2 == -y_2 ) and ( x_1 == -z_1 and x_2 == -z_2 ) )

If those three relations hold, a, b, c, d make an oriented square.

share|improve this answer
1  
I think rectangle can satisfy your conditions, as well. –  meshuai Nov 23 '12 at 15:41
    
No, the first conditionis not met by orthogonal, but not equally lengthed vectors. –  Mark Salzer Nov 23 '12 at 15:44
1  
yeah, I just miss the first one. But the 4 points are not ordered. So, we need more steps, I think, in order to confirm. –  meshuai Nov 23 '12 at 15:58
    
Yes... if no cleverer idea arises, one whould need to loop. I think one needs an outer loop to calculate w, x, y, z from each possible ordering of a, b, c, d, and one inner loop for each possible ordering of the w, x, y, z tuple. –  Mark Salzer Nov 23 '12 at 17:08
add comment

enter image description here

There are some good answers here, but the question asked for the simplest approach. I gave this some quick thought and this is how I would do it.

You can tell if four points represent a square (even if rotated), but finding the average of the four points.

R = (A+B+C+D)/4

Once you have the average, the distance between each point and the average would have to be the same for all four points.

if(dist(R,A) == dist(R,B) == dist(R,C) == dist(R,D) then
   print "Is Square"
else
   print "Is Not Square"

EDIT:

My mistake. That would only tell you if the form points were on a circle. If you also check the distance between points, then it must be a square.

if(dist(R,A) == dist(R,B) == dist(R,C) == dist(R,D) AND
  (dist(A,B) == dist(B,C) == dist(C,D) == dist(R,D) then
   print "Is Square"
else
   print "Is Not Square"

This assumes that points A,B,C,D do not cross (as in have a valid winding order).

share|improve this answer
add comment

Similar to the answer by starblue

Pick any three of the four points.

Look for a right angled vertex among them: By checking if the dot product of any two of the three vectors is zero. If not found, not a square.

Check whether the vertices adjacent to this angle are right angled too. If not, not a square.

Check whether diagonals are perpendicular: If the dot product of the vectors between the first and fourth vertex and the other two vertices (diagonals) is zero, then its a square.

share|improve this answer
    
Good idea, but you still need to check that the 4th vertex is at the right distance from the other points. You only check that it is on the diagonal. –  starblue Dec 1 '12 at 15:49
    
@starblue Right! Otherwise it can form a kite. Updated. –  Max Dec 1 '12 at 18:14
add comment

I think you can do this with simple addition and subtraction and finding min/max. Terms (matches other people's diagram):

  • Point with highest y value => A
  • highest x => B
  • lowest y => C
  • lowest x => D

If 4 points share only 2 x values and 2 y values you have a level square.

Otherwise, you have a square if your points satisfy the following:

  • A.x + C.x = B.x + D.x
  • A.y + C.y = B.y + D.y
  • A.y - C.y = B.x - D.x

Explanation: The line segments A-C and B-D should meet at their midpoints. Thus (A.x + C.x) / 2 is the midpoint of A-C and (B.x + D.x) / 2 is the midpoint of B-D. Multiply each side of this equation by 2 to get my first equation. The second equation is the same thing for Y-values. Diamond-shapes (rhomboids) will satisfy these properties, so you need to check that you have equal sides - that the width is the same as the height. That's the third equation.

share|improve this answer
add comment

this is not an answer according to the standards set, but I hope this helps:

[Copied from the link below so you don't have to open the link] Python 76 characters

def S(A):c=sum(A)/4.0;return set(A)==set((A[0]-c)*1j**i+c for i in range(4))

Function S takes a list of complex numbers as its input (A). If we know both the centre and one corner of a square, we can reconstruct the square by rotating the corner 90,180 and 270 degrees around the centre point (c). On the complex plane rotation by 90 degrees about the origin is done by multiplying the point by i. If our original shape and the reconstructed square have the same points then it must have been a square.

This was taken from : Determine if 4 points form a square

If you like the answer, I say, take some moments out to thank the person, or up-vote his answer on that page.

share|improve this answer
1  
You could summarize the algorithm here. You are linking to another SE site, which is slightly better than pointing to another site, but we want the answer to be on this page, where the question is being asked. Now people have to click again to learn what the answer might be. –  Martijn Pieters Nov 29 '12 at 15:01
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.