Quality and filling geometric pattern

Question

There is some geometric pattern in the image above. The distance a is known. The points are not at a distance of the model strictly.

I want:

• calculate the quality of each point (the actual distance between the points is not a ), the best point is suitable for the better quality factor that you should have (I tried to distance myself and 45 degrees)
• eliminate the wrong points (I marked it in red) - this is due to the calculation of image quality

What I have tried so far:

• Take each point with each other
• Calculate the distance and angle between them
• Take only the neighboring points to the current point (the distance between a - delta and a + delta
• Quality is real distance / model Distance * realAngle / modelAngle

Why this failed:

• The good quality of the glasses has greatly diminished with bad points in the neighborhood.
• If a bad point has only one neighbor, and the distance and angle were fine, the quality was fine.

So, the question is: what is the best algorithm for calculating the quality of points in this case and filling out the template. The template should be filled out by averaging the position of the element taking into account the positions of neighbors. The best answer would be pseudo-code or code or a link to some well-known algorithm that may be useful in this case.

The question is slightly related to my previous question. Filling a rectangle with a point pattern , but filling cannot be done with incorrect quality points.

Answer 1

If the error / distortion of the points does not increase when you go from left to right or from top to bottom (that is, the average distance a between adjacent good points is known for sure), you can try the following:

• print each point P _i in the square [0,a[ x [0,a[ , taking the rest of the coordinates x and y when dividing by a (generating Q _i ). Thus, good points will more or less be displayed on one point.
• Among these generated points Q _i, select one point R with the nearest neighbors (for example, sum 1/distance for all distances to other points Q _j , j & ne, i, and choose the one that has the maximum amount).
• Now you can distinguish between good and bad points P _i by superimposing Q _i on R. (The points P _i whose corresponding Q _i is close to R will be good points.)

If the point R (with nearest neighbors) has a coordinate close to 0 or (i.e., R is close to the border of the square [0,a[ x [0,a[ ), it is better to start from the beginning and add a/2 to (each P _i ) before calculating the remainder to bring the point R to the center of the square. (Or you can calculate the minimum distance from various possibilities to leave the square [0,a[ x [0,a[ on one side and return to it on the opposite side.)

Answer 2

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