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.
Programming Praxis 
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):
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)^2Comparison 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)))))))[…] 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.
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)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]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:
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); }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.
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 conditionalsAnother 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) # calculate sum of all products of two: p = sum(ws[i]*ws[j] for i in range(4) for j in range(i+1, 4)) # calculate sum of all products of three: 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) # calculate sum of all products of two: # 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: # calculate sum of all products of three: # 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 FalseAs 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.
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))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; }[…] Question is from here: […]
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")); Console.ReadKey(); } 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; } }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
#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; }..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