## 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 orderAnd 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) -- degenerateThe 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

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.

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

My Haskell solution (see http://bonsaicode.wordpress.com/2013/01/02/programming-praxis-four-points-determine-a-square/ for a version with comments):

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

[...] Question is from here: [...]

My solution in Java is here.

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

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

A Python solution very close to Remco’s approach:

Clojure version; works with Remco example:

Some test cases:

My first submission, C#:

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.

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.

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

Another solution, based on complex algebra.

As Remco Niemeijer said, the current solution is incorrect.

To repair the solution we can do the same check from 3 different points.

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.

Another Java solution.

[...] Question is from here: [...]

C# version:

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

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.

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.

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

#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();

}

[...] The task: [...]

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;

}

}

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

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

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

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

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’

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″);

int x1 = Int32.Parse(Console.ReadLine());

int y1 = Int32.Parse(Console.ReadLine());

int x2 = Int32.Parse(Console.ReadLine());

int y2 = Int32.Parse(Console.ReadLine());

int x3 = Int32.Parse(Console.ReadLine());

int y3 = Int32.Parse(Console.ReadLine());

int x4 = Int32.Parse(Console.ReadLine());

int y4 = Int32.Parse(Console.ReadLine());

if (x1 == x2 && y2 == y3 && x3 == x4 && y4 == y1)

{

Console.WriteLine(“Its a square”);

}

else

{

Console.WriteLine(“Its a not a square”);

}

Console.ReadKey();

}

}

}

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;

}

Link to run program: http://jsfiddle.net/cjAX9/2/

A slightly lengthy, detailed alternative solution in Python