Fitting a grid to points in a 2d space 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.
You could represent the grid with 5 parameters:


(x0, y0) to represent the offset from your image origin to the grid
origin 
(xs, ys) to represent a multiplication factor from your image
plane to your grid plane. If your grid is spaced apart every 100
pixels on your image plane, these values might be 100,100 
theta to
represent the rotation of the grid


You could fit the grid to point in image by varying these 5 parameters and optimize these parameters by calculating a cost function at each step. 

An example cost function would be the total Euclidean distance between known point and grid points. The grid parameters that best overlap your given point should represent an optimal solution in most cases, especially in cases where you have several "correct points" and few of the "outlier points".

For efficiency you could ensure that your x0 value is [0,xs] and your y0 is [0,ys]. Since it sounds like you have a guess for the size of your grid, you could input a decent guess for xs and ys and also constrain these values from changing too much.