Geometric pattern quality and filling

Question

On the image above there is some geometrical pattern. Model a distance is known. Points are not in model distance strictly.

I want to:

• calculate each point quality (real distance between points is not a) the better point fits to pattern better quality coeficient it should have (I've tried to take distance and 45deg angle)
• eliminate wrong points (I've marked it with red) - it's connected with pattern quality computing

What I've tried so far:

1. Take each point with each other
2. Calculate distance and angle between them
3. Take only points neighbour to current point (which distance is between a - delta and a + delta
4. Quality is realDistance/modelDistance * realAngle/modelAngle

Why it failed:

• Good points quality was strongly decreased with bad points in neighbourhood
• If bad point has only one neighbour and the distance and angle was ok its quality was ok.

So the question is: what is the best algorithm to calculate points quality in this case, and fill pattern. Pattern should be filled by averaging position of element taking in account neighbours positions. The best answer will be pseudocode or code or reference to some known algorithm which can be helpful in this case.

Question is a little bit related with my previous question Filling rectangle with points pattern but the filling could not be done with wrong quality points.

Answer 1

The good points seem to be aligned along a grid. The grid lines can be found using a line fitting algorithm using RANSAC. RANSAC line fitting is a probabilistic algorithm. You will have to repeat it until you find a line that is almost horizontal or vertical. Take the points on/near this line out and go for the next grid line. Depending on your problem characteristics you will stop looking for new grid lines if too few points are left or too few points are on/near one line. The remaining points are the bad ones. When you take the intersections of the found grid lines and there is no point (from all the original ones) near the intersection, then you can fill in a point here.

Answer 2

If the error/distortion of the points does not get bigger when you go from left to right or top to bottom (i.e. the average distance a between neighbouring good points is known exactly enough), you can try the following:

• bring each point P_i into the square [0,a[ x [0,a[ by taking the remainder of x and y coordinates when dividing through a (generating Q_i). Thus the good points will more or less be mapped onto one point.
• Among these generated points Q_i choose one point R with the closest neighbours (e.g. sum up 1/distance for all distances to other points Q_j, j≠ i, and choose the one with maximal sum).
• Now you can distinguish between good and bad points P_i by looing at the distances Q_i to R. (Points P_i whose corresponding Q_i is close to R will be good points.)

If the point R (with the closest neighbours) has a coordinate close to 0 or a (i.e. R is close to the border of the square [0,a[ x [0,a[), you better start from the beginning and add a/2 to the corresponding coordinate (of each P_i) before computing the remainder, in order to bring the point R more to the center of the square. (Or you manage to compute the minimal distance of the different possibilities of leaving the square [0,a[ x [0,a[ on one side and come back into it on the opposite side.)