Problem: Given a list of points on a 2D plane, find all largest grids formed by these points.
A grid, in my definition, is a set of points that "fill a rectangle". Also, there's no need to consider rotated grids in my case.
For example, the points { A, B, C, ... , I } form a grid below:
A B C
D E F
G H I
But if we remove point E, it's no longer a grid because there's a hole:
A B C
D F
G H I
By largest I mean in the following case:
A B C
D E F
Although the points { A, B, C, D } form a grid, the output should be { A, B, C, D, E, F } because it forms a larger grid.
Finally, grids can overlap, so in this case:
A B
C D E
F G
The points {A, B, C, D} and {D, E, F, G} each form a grid.
Context: I want to create a Figma plugin that detects if there are repeated elements, in order to turn them into reusable components. For example in this Figma design, we can turn each column into a component. This grid problem is a part of the algorithm I'm trying to write.
What I've tried:
I first ran the DBSCAN algorithm on the points' x-coordinates and y-coordiantes to find a list of points that align with each other vertically and horizontally respectively, because it allowed for a margin of error when points are not perfectly aligned.
Then I was kind of stuck.
Maybe a way is to loop through each point, treat it as the top-left corner of a potential grid, then search for all possible grid sizes? That sounds pretty inefficient.
Any suggestions are welcome. Thanks a lot!
