Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Detect square in a List of Points

I want to test if there is a square in a list of Point object or not.

This is my Point class :

class Point {
    private int x;
    private int y;

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

    public int getX() {
        return x;
    }

    public void setX(int x) {
        this.x = x;
    }

    public int getY() {
        return y;
    }

    public void setY(int y) {
        this.y = y;
    }

    public int distanceSquare(Point q) {
        return (x - q.getX()) * (x - q.getX()) +
                (y - q.getY()) * (y - q.getY());
    }
}

I can test if four Point is a Square or not :

static boolean isSquare(Point p1, Point p2, Point p3, Point p4) {
        int d2 = p1.distanceSquare(p2);  // from p1 to p2
        int d3 = p1.distanceSquare(p3);  // from p1 to p3
        int d4 = p1.distanceSquare(p4);  // from p1 to p4

        if (d2 == d3 && 2 * d2 == d4) {
            int d = p2.distanceSquare(p4);
            return (d == p3.distanceSquare(p4) && d == d2);
        }

        if (d3 == d4 && 2 * d3 == d2) {
            int d = p2.distanceSquare(p3);
            return (d == p2.distanceSquare(p4) && d == d3);
        }
        if (d2 == d4 && 2 * d2 == d3) {
            int d = p2.distanceSquare(p3);
            return (d == p3.distanceSquare(p4) && d == d2);
        }

        return false;
    }

But I didn't found the best way to search the square in a list of Point.

Can you help me !!!

like image 619
Mohamed Avatar asked Dec 17 '16 14:12

Mohamed


People also ask

How do you know when points form a square?

To form a square, the distance of two points must be the same from 'p', let this distance be d. The distance from one point must be different from that d and must be equal to √2 times d.

How do you know if four points form a square Leetcode?

Given the coordinates of four points in 2D space p1 , p2 , p3 and p4 , return true if the four points construct a square. The coordinate of a point pi is represented as [xi, yi] . The input is not given in any order. A valid square has four equal sides with positive length and four equal angles (90-degree angles).


1 Answers

Take all pairs of points; for each pair calculate its angle, its length and the middle point. This will take O(n^2) time.
For each set of pairs having the same middle point and the same length sort these pairs by angle, this will take in total O(n^2*log(n)) time. This will help you to find two orthogonal diagonals of the same length having the same middle point (that is the square!).
Total algo time complexity is O(n^2*log(n)).

like image 143
Egor Skriptunoff Avatar answered Sep 23 '22 16:09

Egor Skriptunoff