I have this problem where I have multiple points in a 2D space. A subset of these points makes up a rectangular grid. Some points of the grid might be missing. The shape and number of points the grid consists of are known. Also, the other points not making up the grid are few. The general location and rotation of the grid are also known. But we don't know the exact location or rotation. What would be a good, and most important, efficient way to find this grid?
A perfect grid:
The grid can appear as shown below with a missing point:
Or with for example a rotation and being split in two as shown below:
In the actual problem, the grid is larger but always rectangular, also we can assume the gird is located around the center of the data.
The points come from an image where there is monospaced text. The missing points and noise are due to glare in this image. The points are the centers of the (by preprocessing) found characters (so not exact). The text in the image always consists of the same number of characters and lines. The idea is reconstructing this grid to be able to find the lost characters. We do not know what points are characters and what points are not, but I am aware this could be approximated by analyzing the "blobs" we find in the image.