Finding the squares in a plane given n points

Question

Given n points in a plane , how many squares can be formed ...??

I tried this by calculating the distances between each 2 points , then sort them , and look for the squares in the points with four or more equal distances after verifying the points and slopes.

But this looks like an approach with very high complexity . Any other ideas ...??

I thought dynamic programming for checking for line segments of equal distances might work ... but could not get the idea quite right ....

Any better ideas???

P.S : The squares can be in any manner . They can overlap , have a common side, one square inside another ...

If possible please give a sample code to perform the above...

Answer 1

First, observe that each square can be uniquely identified with its center and the vector corresponding to one of the diagonals. And moreover, the other diagonal can be easily found out by finding the orthogonal vector of the same length, to the first one, which will be (-b, a) for a vector (a, b). Now, for each pair of points we will encode the unique square that can be formed by treating them as a diagonal, by the pair of coordinates of their mid-point, and the direction of the vector.

Initialize a multiset which stores two pairs of ints, lets call it M. Also initalize the integer variable count with value 0.

Now iterate over all the pairs of points (by a twice-nested loop on the list of points) :

1. Let the current pair of points be p1: (x1, y1) and p2: (x2, y2). Then swap (p1, p2) if x1 < x2.
2. Insert the following pair of int-pairs into multiset M - ((x1+x2, y1+y2), (x1-x2, y1-y2)). The first pair represents the midpoint (actually 2*midpoint coordinates), and the second pair represents the vector corresponding to the diagonal.
3. If y1 > y2, swap (p1, p2). Query the count of the following in M: ((x1+x2, y1+y2), (abs(y1-y2), x1-x2)). Increase the variable count by this answer to this query.

Finally return count ans the answer.

Time Complexity: Using multiset the T.C. is $O(n^2 \log n)$. But can be taken to $O(n^2)$ with hashmaps too.

Note: The swapping above have been performed in order to save the vector of diagonal with a particular orientation, here the orientation has been taken to be such that the x-coordinate of the vector is always positive.

Answer 2

Here is a complete implemention of finding the diagonal points in C++!

• Given points a and c, return b and d, which lie on the opposite diagonal
• If b or d are not integer points, dicard them (optional)
• To find all squares generated by n points, can check out this C++ implementation
• Idea credited to Kevman. Hope it can help!

vector<vector<int>> createDiag(vector<int>& a, vector<int>& c){
    double midX = (a[0] + c[0])/2.0;
    double midY = (a[1] + c[1])/2.0;
    
    double bx = midX - (a[1] - midY);
    double by = midY + (a[0] - midX);
    double dx = midX - (c[1] - midY);
    double dy = midY + (c[0] - midX);
    
    // discard the non-integer points
    double intpart;
    if(modf(bx, &intpart) != 0 or modf(by, &intpart) != 0 or modf(dx, &intpart) != 0 or modf(dy, &intpart) != 0){
        return {{}};
    }
    return {{(int)bx, (int)by}, {(int)dx, (int)dy}};
}

Answer 3

This is just an example implementation in Java - any comments welcome.

import java.util.Arrays;
import java.util.NoSuchElementException;
import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;


public class SweepingLine {


    public static void main(String[] args) {
        Point[] points = {
            new Point(1,1),
            new Point(1,4),
            new Point(4,1),
            new Point(4,4),
            new Point(7,1),
            new Point(7,4)
        };
        int max = Arrays.stream(points).mapToInt(p -> p.x).max().orElseThrow(NoSuchElementException::new);
        int count = countSquares(points, max);
        System.out.println(String.format("Found %d squares in %d x %d plane", count, max, max));
    }

    private static int countSquares(Point[] points, int max) {
        int count = 0;
        Map<Integer, List<Integer>> map = new HashMap<>();

        for (int x=0; x<max; x++) {
            for (int y=0; y<max; y++) {
                for(Point p: points) {
                    if (p.x == x && p.y == y) {
                        List<Integer> ys = map.computeIfAbsent(x, _u -> new ArrayList<Integer>());
                        ys.add(y);
                        Integer ley = null;
                        for (Integer ey: ys) {
                            if (ley != null) {
                                int d = ey - ley;
                                for (Point p2: points) {
                                    if (x + d == p2.x && p2.y == ey){
                                        count++;
                                    }
                                }
                            }
                            ley = ey;
                        }
                    }
                }
            }
        }
        return count;
    }

    private static class Point {
        public final int x;
        public final int y;
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

}

Answer 4

Runtime: O(nlog(n)^2), Space: θ(n), where n is the number of points.

For each point p
Add it to the existing arrays sorted in the x and y-axis respectively.
  For every pair of points that collide with p in the x and y-axis respectively
   If there exists another point on the opposite side of p, increment square count by one.

The intuition is counting how many squares a new point creates. All squares are created on the creation of its fourth point. A new point creates a new square if it has any colliding points on concerned axes and there exists the "fourth" point on the opposite side that completes the square. This exhausts all the possible distinct squares.

The insertion into the arrays can be done binary, and checking for the opposite point can be done by accessing a hashtable hashing the points' coordinates.

This algorithm is optimal for sparse points since there will be very little collision points to check. It is pessimal for dense-squares points for the opposite of the reason for that of optimal.

This algorithm can be further optimized by tracking if points in the axis array have a collision in the complementary axis.

Answer 5

I have a O(N^2) time, O(N) space solution:

Assume given points is an array of object Point, each Point has x,y.

1. First iterate through the array and add each item into an HashSet: This action de-duplicate and give us an O(1) access time. The whole process takes O(N) time
2. Using Math, Say vertices A, B, C, D can form a square, AC is known and it's a diagonal line, then the corresponding B, D is unique. We could write a function to calculate that. This process is O(1) time
3. Now Let's get back to our thing. write a for-i-loop and a for-j-inner-loop. Say input[i] and input[j] form a diagonal line, find its anti-diagonal line in the set or not: If exist, counter ++; This process take O(N^2) time.

My code in C#:

    public int SquareCount(Point[] input)
    {
        int count = 0;

        HashSet<Point> set = new HashSet<Point>();
        foreach (var point in input)
            set.Add(point);

        for (int i = 0; i < input.Length; i++)
        {
            for (int j = 0; j < input.Length; j++)
            {
                if (i == j)
                    continue;
                //For each Point i, Point j, check if b&d exist in set.
                Point[] DiagVertex = GetRestPints(input[i], input[j]);
                if (set.Contains(DiagVertex[0]) && set.Contains(DiagVertex[1]))
                {
                    count++;
                }
            }
        }
        return count;

    }

    public Point[] GetRestPints(Point a, Point c)
    {
        Point[] res = new Point[2];

        int midX = (a.x + c.y) / 2;
        int midY = (a.y + c.y) / 2;

        int Ax = a.x - midX;
        int Ay = a.y - midY;
        int bX = midX - Ay;
        int bY = midY + Ax;
        Point b = new Point(bX,bY);

        int cX =  (c.x - midX);
        int cY =  (c.y - midY);
        int dX = midX - cY;
        int dY = midY + cX;
        Point d = new Point(dX,dY);

        res[0] = b;
        res[1] = d;
        return res;
    }

Answer 6

This problem can be solved in O(n^1.5) time with O(n) space.

The basic idea is to group the points by X or Y coordinate, being careful to avoid making groups that are too large. The details are in the paper Finding squares and rectangles in sets of points. The paper also covers lots of other cases (allowing rotated squares, allowing rectangles, and working in higher dimensions).

I've paraphrased their 2d axis-aligned square finding algorithm below. Note that I changed their tree set to a hash set, which is why the time bound I gave is not O(n^1.5 log(n)):

1. Make a hash set of all the points. Something you can use to quickly check if a point is present.

2. Group the points by their X coordinate. Break any groups with more than sqrt(n) points apart, and re-group those now-free points by their Y coordinate. This guarantees the groups have at most sqrt(n) points and guarantees that for each square there's a group that has two of the square's corner points.

3. For every group g, for every pair of points p,q in g, check whether the other two points of the two possible squares containing p and q are present. Keep track of how many you find. Watch out for duplicates (are the two opposite points also in a group?).

Why does it work? Well, the only tricky thing is the regrouping. If either the left or right columns of a square are in groups that are not too large, the square will get found when that column group gets iterated. Otherwise both its top-left and top-right corners get regrouped, placed into the same row group, and the square will be found when that row group gets iterated.

Answer 7

Just a thought: if a vertex A is one corner of a square, then there must be vertices B, C, D at the other corners with AB = AD and AC = sqrt(2)AB and AC must bisect BD. Assuming every vertex has unique coordinates, I think you can solve this in O(n^2) with a hash table keying on (distance, angle).

Answer 8

Let d[i][j] = distances between points i and j. We are interested in a function count(i, j) that returns, as fast as possible, the number of squares that we can draw by using points i and j.

Basically, count(i, j) will have to find two points x and y such that d[i][j] = d[x][y] and check if these 4 points really define a square.

You can use a hash table to solve the problem in O(n^2) on average. Let H[x] = list of all points (p, q) that have d[p][q] = x.

Now, for each pair of points (i, j), count(i, j) will have to iterate H[ d[i][j] ] and count the points in that list that form a square with points i and j.

This should run very fast in practice, and I don't think it can ever get worse than O(n^3) (I'm not even sure it can ever get that bad).

Answer 9

It looks like O(n^3) to me. A simple algo might be something like:

for each pair of points
    for each of 3 possible squares which might be formed from these two points
        test remaining points to see if they coincide with the other two vertices