Find 4 points which form a square with the biggest area

Question

I have set of points on the coordinate plane. I need to find the 4 points which form a square with the biggest area.

I'm new in JavaScript so I'd like to get any suggestions about code style, patterns, code idioms, etc. Thank you in advance!

"use strict";

/*
 * Point
 */

(function() {
    function numbersEqual(a, b) {
        return Math.abs(a - b) < Number.EPSILON;
    }

    function Point(x, y) {
        this.x = x;
        this.y = y;
    }

    Point.distance = function(a, b) {
        return Math.sqrt((a.x - b.x) ** 2 + (a.y - b.y) ** 2);
    }

    Point.equal = function(a, b) {
        return numbersEqual(a.x, b.x) && numbersEqual(a.y, b.y);
    }

    Point.pointsFormsQuadrangle = function(a, b, c, d) {
        if (Point.equal(a, b) || Point.equal(a, c) || Point.equal(a, d))
            return false;

        if (Point.equal(b, c) || Point.equal(b, d))
            return false;

        if (Point.equal(c, d))
            return false;

        const center = new Point((a.x + b.x + c.x + d.x) / 4, (a.y + b.y + c.y + d.y) / 4);

        const ac = Point.distance(a, center);
        const bc = Point.distance(b, center);
        const cc = Point.distance(c, center);
        const dc = Point.distance(d, center);

        return numbersEqual(ac, bc) && numbersEqual(bc, cc) && numbersEqual(cc, dc);
    }

    Point.pointsFormsSquare = function(a, b, c, d) {
        if (!Point.pointsFormsQuadrangle(a, b, c, d))
            return false;   

        const ab = Point.distance(a, b)
        const ac = Point.distance(a, c);
        const ad = Point.distance(a, d);
        const triangle = [ab, ac, ad].sort((a, b) => a - b);

        return numbersEqual(triangle[0], triangle[1]);
    }

    window.Point = Point;
})();

/*
 * Square
 */

(function () {
    function Square(a, b, c, d) {
        this.a = a;
        this.b = b;
        this.c = c;
        this.d = d;
    }

    Square.prototype.area = function() {
        const findSquareDiagonalLength = (a, b, c, d) => {
            const ab = Point.distance(a, b);
            const ac = Point.distance(a, c);
            const ad = Point.distance(a, d);

            return Math.max(ab, ac, ad);
        };

        const d = findSquareDiagonalLength(this.a, this.b, this.c, this.d);
        return d * d / 2;
    }

    window.Square = Square;
})();

/*
 * Solution
 */

function formSquaresFromPoints(points) {
    let squares = [];

    for (let a = 0; a < points.length; a++)
        for (let b = a + 1; b < points.length; b++)
            for (let c = b + 1; c < points.length; c++)
                for (let d = c + 1; d < points.length; d++)
                    if (Point.pointsFormsSquare(points[a], points[b], points[c], points[d]))
                        squares.push(new Square(points[a], points[b], points[c], points[d]));

    return squares;
}

function sortSquaresByArea(squares) {
    squares.sort((a, b) => {
        if (a.area() > b.area())
            return 1;
        else if (a.area() < b.area())
            return -1;
        else
            return 0;
    });

    return squares;
}

const POINTS = [
    new Point(1, 1),
    new Point(1, 3),
    new Point(3, 1),
    new Point(3, 3),
    new Point(1, 6),
    new Point(6, 1),
    new Point(6, 6),
    new Point(1, 9),
    new Point(9, 1),
    new Point(9, 9),
    new Point(4, 5),
    new Point(4, 8),
    new Point(7, 8),
    new Point(7, 5),
    new Point(6, 3),
    new Point(5, 3),
    new Point(5, 1)
];

const sortedSquares = sortSquaresByArea(formSquaresFromPoints(POINTS));
const squareWithBiggestArea = sortedSquares[sortedSquares.length - 1];

console.log(squareWithBiggestArea); // Gives: {(1, 1), (1, 9), (9, 1), (9, 9)}

Answer 1

I have some nitpicks to talk about before getting in a bigger thing :

• distance should be named distanceTo, equal should be areEqual.

• OOP wise, the function pointsFormsQuadrangle shouldn't be in the class Point, because it breaks single responsibility principle, you could extract it to someplace else.

Nitpicks are over.

In pointsFormsSquare, you call pointsFormsQuadrangle. The verifications that you do, to assert that you have a square, are the following :

• No points are the same.
• All the distances to the center of your points are equal.
• You check if two sides of the quadrangle are equal (I believe).

The two last parts are the important one and they seem to work pretty well. But is it the most efficient way to figure out if something is a square? Probably not. Computing the euclidean distance is kind of expensive. There a lots of solution on internet that don't rely on computing distances 7 times.

Finally, the function formSquaresFromPoints probably iterates over way more points than it should. At the moment you have 3 points, you can start excluding the possibility that they form a square. If you know for sure that the 3 points can't possibly form a square, you'll try combinations with every other points with no reason, because it's already impossible for them to make a square. You don't test with many points right now, so maybe it doesn't matter. I'm not sure I explained myself correctly on this point, but don't hesitate to ask questions if you didn't understand.

I can't comment much on the "Javascriptness" of your code because I'm not good enough with this language, but it looks clean.

Answer 2

You're coding javascript the "old" way. With es6 you have a lot of new features available. Take a look at them.

---

Don't use self-invoking anonymous functions i.e. IIFEs

/// bad
(function(){
  // code here
})();

Use blocks

/// good
{
   // code here
}

---

Give meaningful names to your variables and methods. Functions should not have more than 2 parameters. If they do, you need to put them in an object.

/// bad
... pointsFormsQuadrangle = function(a, b, c, d){}

/// good
static FormsQuadrangle([point1, point2, point3, point4]){

}

---

Use the class syntax instead of function/prototype.

class Utils {
  static NumbersEqual(a, b){
    return Math.abs(a - b) < Number.EPSILON;
  }
}

class Point {
  constructor(x, y) {
    this.x = x;
    this.y = y;
  }

  distance(point) {
    return Math.sqrt((this.x - point.x) ** 2 + (this.y - point.y) ** 2);
  }

  equal(point) {
    return Utils.NumbersEqual(this.x, point.x) && Utils.NumbersEqual(this.y, point.y);
  }

  static FormsQuadrangle(a, b, c, d) {
    if (a.equal(b) || a.equal(c) || a.equal(d)) return false;

    if (b.equal(c) || b.equal(d)) return false;

    if (c.equal(d)) return false;

    const center = new Point((a.x + b.x + c.x + d.x) / 4, (a.y + b.y + c.y + d.y) / 4);

    const ac = a.distance(center);
    const bc = b.distance(center);
    const cc = c.distance(center);
    const dc = d.distance(center);

    return Utils.NumbersEqual(ac, bc) && Utils.NumbersEqual(bc, cc) && Utils.NumbersEqual(cc, dc);
  }

  static FormsSquare(a, b, c, d) {
    if (!Point.FormsQuadrangle(a, b, c, d))
      return false;

    const ab = a.distance(b)
    const ac = a.distance(c);
    const ad = a.distance(d);
    const [tr1, tr2] = [ab, ac, ad].sort((a, b) => a - b);

    return Utils.NumbersEqual(tr1, tr2);
  }
}