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.

About these ads

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 [...]

  3. 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)^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. javabloggi said

    My solution in Java is here.

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

  7. 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)
    
  8. 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]
    
  9. 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
    
  10. 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);
                }
    
  11. 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.

  12. 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
    
  13. 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)
        # 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 False
    
  14. As Remco Niemeijer said, the current solution is incorrect.
    To repair the solution we can do the same check from 3 different points.

  15. 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))
    
  16. 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;
        }
    
  17. 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"));
                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;
            }
        }
    
  18. 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

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

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

  21. Jan Van lent said

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

  22. 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();
    }

  23. 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;
    }
    }

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

  25. 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;
    }
    
  26. 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..

  27. 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’

  28. 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″);
    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();
    }
    }
    }

  29. 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;
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 630 other followers

%d bloggers like this: