## Four Points Determine A Square

### January 2, 2013

Today’s exercise is an interview question. It’s not hard, but it’s unusual enough that it took several minutes before I knew what to do.

Consider a list of four points on a plane; the points have integral coordinates, and their order is irrelevant. The four points determine a square if the distances between them are all equal, and the lengths of the two diagonals are also equal. For instance, the following lists are all squares:

```(0,0), (0,1), (1,1), (1,0) -- the unit square (0,0), (2,1), (3,-1), (1, -2) -- square not aligned to axis (0,0), (1,1), (0,1), (1,0) -- unit square, in different order```

And the following lists do not represent squares:

```(0,0), (0,2), (3,2), (3,0) -- rectangle (0,0), (3,4), (8,4), (5,0) -- rhombus (0,0), (0,0), (1,1), (0,0) -- degenerate (0,0), (0,0), (1,0), (0,1) -- degenerate```

The degenerate square that consists of four repetitions of a single point may be considered either square, or not.

Your task is to write a function that determines if four input points determine a square. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 34 Responses to “Four Points Determine A Square”

1. The provided solution is incorrect. Take for example the points (0, 0), (1, 0), (0, 1) and (-1, -1). These will pass the test, but they are certainly not a square.

2. […] today’s Programming Praxis exercise, our goal is to determine whether four given points in a 2D plane make […]

```import Data.List

isSquare :: (Num a, Ord a) => (a, a) -> (a, a) -> (a, a) -> (a, a) -> Bool
isSquare p q r s = and [a == b, b == c, c == d, e == f, a + b == e] where
[a,b,c,d,e,f] = sort [l | (h:t) <- tails [p,q,r,s], l <- map (dist h) t]
dist (x1,y1) (x2,y2) = (x2-x1)^2 + (y2-y1)^2
```
4. Jussi Piitulainen said

Comparison of the lengths of two adjacent line segments determines the possible sides and diagonals. Checking remains. (Remco’s counterexample caught me, too. Nice.)

```(import (scheme))

(define (dd p q)
(let ((u (- (car p) (car q)))
(w (- (cdr p) (cdr q))))
(+ (* u u) (* w w))))

(define (square? p q r s)
(let ((m (dd p q))
(n (dd p r)))
(cond
((= m n) (and (= m n (dd q s) (dd r s))
(= (dd p s) (dd q r))))
((< m n) (and (= m (dd p s) (dd q r) (dd s r))
(= n (dd q s))))
((> m n) (and (= m (dd r s))
(= n (dd p s) (dd r q) (dd s q)))))))
```
5. […] Question is from here: […]

6. javabloggi said

My solution in Java is here.

7. khigia said

from itertools import groupby, combinations

def dist(v):
(x1, y1), (x2, y2) = v
return (x2 – x1) ** 2 + (y2 – y1) ** 2

def is_square(l):
pts = combinations(l, 2)
dists = sorted([dist(v) for v in pts])
return [4, 2] == [len(list(g[1])) for g in groupby(dists)]

def test(l):
print(“List {l}, is_square={sq}”.format(l=l, sq=is_square(l)))

test([(0,0),(0,1),(1,1),(1,0)])
test([(0,0), (2,1), (3,-1), (1, -2)])
test([(0,0), (0,2), (3,2), (3,0)])

8. Paul said

A Python version. This exercise is easy to mess up. Thorough testing is important. The full code including tests is here.

```from  itertools import combinations

def distsq(p1, p2):
x1, y1 = p1
x2, y2 = p2
return (x2 - x1) ** 2 + (y2 - y1) ** 2

def is_square(p1, p2, p3, p4):
# check for double points first
if any(a == b for a, b in combinations((p1, p2, p3, p4), 2)):
return False
dis = [distsq(p1, p) for p in (p2, p3, p4)]
pmin = min(dis)
pmax = max(dis)
if not (pmax == 2 * pmin and dis.count(pmin) == 2):
return False
# find point furthest away and assert that distances of that point to the 2
#  remaining points are the same as pmin
far_pt = (p2, p3, p4)[dis.index(pmax)]
return all(distsq(far_pt, p) == pmin for p in (p2, p3, p4) if p != far_pt)
```
9. cosmin said

A Python solution very close to Remco’s approach:

```def dist(a, b):
return (a[0] - b[0])**2 + (a[1] - b[1])**2

def isSquare(a, b, c, d):
lengths = sorted([dist(p[0], p[1]) for p in [(a, b), (a, c), (a, d), (b, c), (b, d), (c, d)]])
return lengths[0] == lengths[3] and lengths[4] == lengths[5]
```
10. kawas44 said

Clojure version; works with Remco example:

```(defn square [x] (* x x))

(defn dist [pt1 pt2]
(+ (square (- (pt1 0) (pt2 0))) (square (- (pt1 1) (pt2 1)))))

(defn dists [coords]
(loop [[xy & coords] coords acc []]
(if-not xy acc
(recur coords (concat acc (map #(dist xy %) coords))))))

(defn is-square? [points]
(and (== 4 (count (set points)))
(<= (count (set (dists points))) 2)))
```

Some test cases:

```(is-square? [[0 0] [0 1] [1 1] [1 0]])
true

(is-square? [[0 0] [0 0] [1 1] [1 0]])
false

(is-square? [[0 0] [1 0] [0 1] [-1 -1]])
false
```
11. itsme86 said

My first submission, C#:

```        private static bool IsItASquare(Point[] points)
{
Tuple<Point, int>[] distances = new Tuple<Point, int>[3];
int ctr = 0;
foreach (Point point in points.Except(new[] { points[0] }))
distances[ctr++] = Tuple.Create(point, point.DistanceSquaredTo(points[0]));
distances = distances.OrderBy(d => d.Item2).ToArray();

if (distances[0].Item2 != distances[1].Item2)
return false;

Point origin = distances[0].Item1;
return origin.DistanceSquaredTo(distances[2].Item1) == origin.DistanceSquaredTo(points[0]) && origin.DistanceSquaredTo(distances[1].Item1) == points[0].DistanceSquaredTo(distances[2].Item1);
}

private class Point
{
public int X { get; private set; }
public int Y { get; private set; }

public Point(int x, int y)
{
X = x;
Y = y;
}

public int DistanceSquaredTo(Point otherPoint)
{
return (int)Math.Pow(Math.Abs(X - otherPoint.X), 2) + (int)Math.Pow(Math.Abs(Y - otherPoint.Y), 2);
}
```
12. Jan Van lent said

I came up with the following, which does not require any multiplication (only “+”, “-“, “4*”=”<<2", "==").

def is_square(zs):
"""test if a list of four complex numbers forms a square"""
# could be implemented without multiplication for points with integer coordinates,
# since times four is a bit shift operation
c = sum(zs) # centre (scaled by 4)
ws = [ 4*z – c for z in zs ] # translate to (0, 0) (and scale by 4)
u = ws[0]
v = u*1j # or: v = complex(-u.imag, u.real)
return set([ -u, v, -v ]) == set(ws[1:]) # could be written using lots of nested conditionals

Test cases from Remco Niemeijer’s post.

```def test():
cases = [ ([ (0,0), (0,1), (1,1), (1,0) ], True),
([ (0,0), (2,1), (3,-1), (1,-2) ], True),
([ (0,0), (1,1), (0,1), (1,0) ], True),
([ (0,0), (0,2), (3,2), (3,0) ], False),
([ (0,0), (3,4), (8,4), (5,0) ], False),
([ (0,0), (0,0), (1,1), (0,0) ], False),
([ (0,0), (0,0), (1,0), (0,1) ], False),
([ (0,0), (1,0), (0,1), (-1,-1) ], False) ]
return [ is_square([ complex(*t) for t in p]) == val for (p, val) in cases ]
```

It turns out that similar solutions have been found by others, see for example http://codegolf.stackexchange.com/questions/1487/determine-if-4-points-form-a-square.

13. Jan Van lent said

The function again, I hope with correct layout this time.

```def is_square(zs):
"""test if a list of four complex numbers forms a square"""
# could be implemented without multiplication for points with integer coordinates,
# since times four is a bit shift operation
c = sum(zs)                              # centre (scaled by 4)
ws = [ 4*z - c for z in zs ]             # translate to (0, 0) (and scale by 4)
u = ws[0]
v = u*1j                                 # or: v = complex(-u.imag, u.real)
return set([ -u, v, -v ]) == set(ws[1:]) # could be written using lots of nested conditionals
```
14. Jan Van lent said

Another solution, based on complex algebra.

```# Four complex numbers form a square if and only if they are
# the roots of an equation of the form
#   (z-c)^4 = r^4
# for some complex numbers c and r.
def is_square_1(zs):
c = sum(zs)                              # centre (scaled by 4)
ws = [ 4*z - c for z in zs ]             # translate to (0, 0) (and scale by 4)
p = sum(ws[i]*ws[j] for i in range(4) for j in range(i+1, 4))
q = sum(ws[i]*ws[j]*ws[k] for i in range(4) for j in range(i+1, 4) for k in range(j+1, 4))
return p == 0 and q == 0

# This represents a system of four polynomial equations in 8 real variables
# which all coordinates that form squares satisfy.
# Can be implemented as a single polynomial equation (of degree 6) in 8 real variables:
#   return abs(p)**2 + abs(q)**2 == 0

# more efficient implementation of this idea
def is_square_2(zs):
c = sum(zs)                              # centre (scaled by 4)
ws = [ 4*z - c for z in zs ]             # translate to (0, 0) (and scale by 4)
# p = sum(ws[i]*ws[j] for i in range(4) for j in range(i+1, 4))
s3 = ws[3]
s2 = ws[2] + s3
s1 = ws[1] + s2
t1 = ws[0] * s1
t2 = ws[1] * s2 + ws[2] * s3
p = t1 + t2
if p == 0:
# q = sum(ws[i]*ws[j]*ws[k] for i in range(4) for j in range(i+1, 4) for k in range(j+1, 4))
q = ws[0] * t2 + ws[1] * ws[2] * ws[3]
return q == 0
else:
return False
```
15. As Remco Niemeijer said, the current solution is incorrect.
To repair the solution we can do the same check from 3 different points.

16. Mike said

Here’s an alternative solution in Python.

It works by checking that two sides are each orthogonal to a third side and that the diagonals are orthogonal.

Throws ValueError if pts does not have four unique points.

```def is_square_3(pts):
(ax,ay), (bx,by), (cx,cy), (dx,dy) = sorted(set(pts))

return ((by - ay)*(cy - ay) == -(bx - ax)*(cx - ax) and
(dy - cy)*(cy - ay) == -(dx - cx)*(cx - ax) and
(cy - by)*(dy - ay) == -(cx - bx)*(dx - ax))
```
17. Toby said

Another Java solution.

```    private boolean isShapeSquare(Point a, Point b, Point c, Point d) {
// Get lengths from any one point to the other 3. A square will always
// have two short equal lengths and a longer one which will be 1.4142135623730951
// times longer. Anything else is not a square.

double aB = java.awt.Point.distance(a.x, a.y, b.x, b.y);
double aC = java.awt.Point.distance(a.x, a.y, c.x, c.y);
double aD = java.awt.Point.distance(a.x, a.y, d.x, d.y);
final double RATIO = 1.4142135623730951;

if (aB == aC) { // Two short lengths
if (aB * RATIO == aD) {
return true;
}
} else { // One short and one long
if (aB < aC) { // aB is short
if (aB * RATIO == aC) {
return true;
}
} else { // aC is short
if (aC * RATIO == aB) {
return true;
}
}
}
return false;
}
```
18. […] Question is from here: […]

19. Erdalkiran said

C# version:

```    class Program
{
static void Main(string[] args)
{
var points = GetPoints();

Array.Sort(points);
bool IsSquare = CheckArray(points);
Console.WriteLine(string.Format("Points {0} determine a square!", IsSquare ? "" : "do not"));
}

private static bool CheckArray(Point[] points)
{
if (points.GroupBy(x => new { x.X, x.Y }).Count() != 4)
return false;

double distance = GetDistanceBetweenTwoPoint(points[0], points[1]);
double diagonal = GetDistanceBetweenTwoPoint(points[0], points[3]);

if (distance == GetDistanceBetweenTwoPoint(points[0], points[2]) && distance == GetDistanceBetweenTwoPoint(points[3], points[2]) && distance == GetDistanceBetweenTwoPoint(points[3], points[1]) && diagonal == GetDistanceBetweenTwoPoint(points[1], points[2]))
return true;

return false;

}

private static double GetDistanceBetweenTwoPoint(Point point1, Point point2)
{
return Math.Sqrt(Math.Pow(point1.X - point2.X, 2) + Math.Pow(point1.Y - point2.Y, 2));
}

private static Point[] GetPoints()
{
return new Point[4] { new Point { X = 2, Y = 0 }, new Point { X = 1, Y = -1 }, new Point { X = 0, Y = 0 }, new Point { X = 1, Y = 1 } };
}
}

//...
struct Point : IComparable
{
public int X;
public int Y;
public int CompareTo(object obj)
{
var otherPoint = (Point)obj;

if (this.Y > otherPoint.Y)
return 1;
else if (otherPoint.Y > this.Y)
return -1;

if (this.X > otherPoint.X)
return 1;
else if (otherPoint.X > this.X)
return -1;

return 0;
}
}
```
20. james said

1. Find the two longest lines (between all the points)
2. Confirm that the two longest lines are of equal length
3. Confirm that the angle between the two longest line are 90 degrees

21. james said

Ah saw the counter example.

Another solution:

Find mid point of all points
Check distance from the midpoint to all the points and confirm that they’re equal.

22. Brian said

Python solution:

# n = [(0, 0),(1, 0), (0, 1),(1,1)]

def isSquare(n):
if len(n)!=4:
return False
else:
d=[]
for x in n:
h=[]
for y in n:
h.append(((y[0]-x[0])**2+(y[1]-x[1])**2)**(1.0/2))
d.append(sorted(h))
return d[0]==d[1]==d[2]==d[3]
[/sourcode]

The function also doesn’t need to calculate the square root for the hypotenuse since it’s comparative, but left it in there anyways for math’s sake.

23. Jan Van lent said

@Brian I think this fails for a rhombus with all internal angles bigger than 60 degrees.

24. shubham said

#include
#include
#include
#include

int dist(int x1, int x2, int y1, int y2)
{ int z;
z=(pow((x1-x2),2)+pow((y2-y1),2));
z=sqrt(z);
return z;
}

void main()
{ int x1,x2,x3,x4,y1,y2,y3,y4,z1,z2,z3,z4;
cout<>x1>>y1;
cout<>x2>>y2;
cout<>x3>>y3;
cout<>x4>>y4;
z1=dist(x1,x2,y1,y2);
z2=dist(x1,x4,y1,y4);
if(z1==z2)
{ cout<<"Checking for rhombus or square";
delay(500);

z3=dist(x1,x3,y1,y3);
z4=dist(x2,x4,y2,y4);
if(z3==z4)
{ cout<<"square";
}
else cout<<"rhombus";
}
else cout<<"Not square";
getch();
}

25. Josh said

My unsophisticated C# solution:

public bool IsSquare(Point p1, Point p2, Point p3, Point p4) {
double p1p2 = EuclidianDistance(p1, p2);
double p1p3 = EuclidianDistance(p1, p3);
double p1p4 = EuclidianDistance(p1, p4);
double p2p3 = EuclidianDistance(p2, p3);
double p2p4 = EuclidianDistance(p2, p4);
double p3p4 = EuclidianDistance(p3, p4);

List distances = new List() { p1p2, p1p3, p1p4, p2p3, p2p4, p3p4 };
distances.Sort();

return (distances[0] == distances[3]) && (distances[4] == distances[5]) && (distances[0] <= distances[4]);
}

public double EuclidianDistance(Point p1, Point p2) {
return Math.Sqrt((p2.X – p1.X) * (p2.X – p1.X) + (p2.Y – p1.Y) * (p2.Y – p1.Y));
}

public class Point {
public double X { get; set; }
public double Y { get; set; }

public Point(double x, double y) {
this.X = x;
this.Y = y;
}
}

26. […] Can you determine programmatically if four points create a square? This was (essentially) the programming problem posed at Programming Praxis/. […]

27. fabio said

If you consider the vectors b – a, c – b, d – c, a – d, in the given order, you can check that they form a square by using the equations bx – ax = cy – by, by – ay = cx – bx, dx – cx = ay – dy, and dy – cy = ax – dx. These vectors form a cycle and the equations can perform a check both on the cycle and the reverse one. There are three pairs of possible permutations for the points a, b, c, d which give a cycle. Each pair consists of a cycle and the reverse one. Thus, to verify that the four points form a square, you have to check only three of the permutations of the points, i.e. (a b c d), (a b d c) and (a c b d). A code in C++ is

```#include <iostream>

bool is_square(int ax, int ay, int bx, int by,
int cx, int cy, int dx, int dy) {

auto ck = [] (int ax, int ay, int bx, int by,
int cx, int cy, int dx, int dy) -> bool {
return (bx - ax == cy - by) && (by - ay == cx - bx)
&& (dx - cx == ay - dy) && (dy - cy == ax - dx);
};

return  ck(ax, ay, bx, by, cx, cy, dx, dy)
|| ck(ax, ay, bx, by, dx, dy, cx, cy)
|| ck(ax, ay, cx, cy, bx, by, dx, dy);
}

using namespace std;
int main(int argc, char *argv[]) {
if (argc == 9)
if (is_square(atoi(argv[1]), atoi(argv[2]), atoi(argv[3]), atoi(argv[4]),
atoi(argv[5]), atoi(argv[6]), atoi(argv[7]), atoi(argv[8])))
cout << "Is a square." << endl;
else cout << "Is not a square." << endl;
}
```
28. fabio said

..well, the check above is wrong, the right check is

```		return (bx - ax == cx - dx) && (by - ay == cy - dy)
&& (cx - bx == dx - ax) && (cy - by == dy - ay)
&& abs(bx - ax) == abs(cy - by)
&& abs(by - ay) == abs(cx - bx);
```

where the first two lines check for a rhombus and the last two lines check the angle abc..

29. fabio said

better: the first version of the check works if all the cohordinates are positive while the second one works with both positive and negative cohordinates. The first two lines of code on the second second version of the check verify that the points form a parallelogram (actually the second line is rendundant). The third and the fourth line say that the angle abc is right and that the sides ab and bc are of equal length. I hope that’s all Oo’

30. sharmilli said

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Square
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine(“Enter the co-ordinates in the order x1, y1, x2, y2, x3, y3, x4, y4”);
if (x1 == x2 && y2 == y3 && x3 == x4 && y4 == y1)
{
Console.WriteLine(“Its a square”);
}
else
{
Console.WriteLine(“Its a not a square”);
}
}
}
}

31. spainmc said

JavaScript version anyone? Happens to test against all four points, but as noted three is sufficient.

function Run(name, poly) {
var total = 0;
for (var i = 0; i < 4; i++) {
total += Test(i, poly);
}
if (total === 4) {
alert(name + " is a square");
}
else { alert(name + " is not a square"); }
}
function Test(i, poly) {
var org = poly[i];
poly.splice(i, 1);
poly.splice(0, 0, org);
var dist = GetAllDistSquared(poly);
var max = Math.max.apply(Math, dist);
var min = Math.min.apply(Math, dist);
var comp = Math.abs(dist[0] – dist[1] – dist[2]);
if (comp === max && max != min && 2 * min === max) {
return 1;
}
else { return 0; }
}
function GetAllDistSquared(poly) {
var d1 = GetDistSquared(poly[0], poly[1]);
var d2 = GetDistSquared(poly[0], poly[2]);
var d3 = GetDistSquared(poly[0], poly[3]);
return [d1, d2, d3];
}
function GetDistSquared(p1, p2) {
var dx = p1.x – p2.x;
var dy = p1.y – p2.y;
return dx * dx + dy * dy;
}