Trouver les carrés dans un avion donné n points

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.

Ceci est juste un exemple de mise en œuvre en Java - tout commentaire Bienvenue.

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

}