Geometry Algorithms – How to Check if 4 Points Form a Square

algorithmsgeometrymath

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.)

Best Answer

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:

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.
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 since AB = AD = BC = CD, this is therefore 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.

Working Example Implementation

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.

Related Solutions

Magic square check for N×N matrix with minimum complexity

It all depends on what n is. If you say that n is the number of ellements per row you cant check if the matrix is magic with less than O(n²). If you say n is the total number of ellements in the matrix you could easily create an algorithm that has the time complexity of O(n).

Here is some psevdo code with time complexity analys

columvalue = rows[0];                    O(1)
diagonalvalue1 = rows[0][0]              O(1)
diagonalvalue2 = rows[0][-1]             O(1)
magicNumber = sum(rows[0]);              O(c)
diagonal count = 1

for r in rows:                           O(r)*(
  diagonalvalue1 += r[0+diagonalcount]         O(1)
  diagonalvalue2 += r[-1-diagonalcount]        O(1)
  diagonalcount  += 1                          0(1)
  rowsum = 0                                   O(1)
  i = 0                                        O(1)
  for n in r:                                  0(c)*(
    rowsum += n                                     O(1)
    columvalue[i] += n                              O(1)
    i += 1                                          0(1)
                                                    )
  if rowsum != magicvalue:                     O(1)
    return False                               O(1)
                                               )

for c in columvalue:                     O(c)*(
  if c != magicvalue:                          O(1)
    return False                               O(1)
                                               )

return diagonalvalue1 == magicvalue and 
       diagonalvalue2 == magicvalue       O(1)

this will give us the time complexity of O(c) + O(r*c) there c = number of colons and r = number of rows. Since O(r*c) >= O(c) we can say that the time complexity is O(r*c) which are the number of ellements in the matrix that are n and this gives us the complexity of O(n)

Algorithm to Detect a Click Within Square Range

A common way to do this is just to compare the coordinates of the mouse click with the coordinates of the square.

Suppose the square has top-left coordinate of x1, y1 and bottom-right is x2,y2.

A mouse click at mx, my is in the square if (mx>x1 and mx<x2 and my>y1 and my<y2).

If all the square are the same size and in a grid, you can give each square a number:

n = y * number of squares in a row + x.

Then to get n from a mouse click:

n = (width of grid in pixels / square width in pixels * number of squares in a row) + (height of grid in pixels / square height in pixels)

Best Answer

Related Solutions

Magic square check for N×N matrix with minimum complexity

Algorithm to Detect a Click Within Square Range

Related Topic