Fill a rectangle with a dot pattern

Question

There is a specific pattern in the figures below. It is best seen in the first image. I have points marked with small circuses and connected with lines. They create a grid. Some points are erroneous and do not match the pattern (marked on the first image). The goal is to fill the entire rectangle marked in red (the rectangle is created from extreme points - points with extreme coordinates in the coordinate system of the picture).

The question is which approach should be used to fill the rectangle with points and eliminate the wrong points. The situation in the second image is extreme, but mostly cases have more points.

Images are for visualization purposes only. I have vectors with coordinates of points. No need to define points.

I will add my solution as soon as I find out.

My current approach is to create lines parallel to the longer sides of the rectangle with a known pattern offset. Then find the points with some delta distance near the lines and fill in the remaining points.

Answer 1

All in all, what I would do is first identify the grid, and then easily check if something is in that grid or not.

These are the following steps:

• rotate everything so that you have only horizontal and vertical lines.

• The per x value calculates how many points you have.

• The percentage value calculates how many points you have.

pseudo code:

xcount is array of int ycount is array of int for x=0 to width-1 do for y=0 to height-1 do foreach point do if point.x = x then xcount[x]++ if point.y = y then ycount[y]++ 

For your last image, the result would be something like this:

 x-count:1,0,0,0,3,0,2,0,1,0,0,0,4,0,0,0,3,0,0,0,4 y-count:2,0,0,0,6,0,0,0,4,0,1,0,3,0,1,0,1 

• Now, to determine the size of the grid:

  match = 0 for i = 1 - 10 do foreach xcount do if xcount mod i = 0 then matches [I] ++

Now we have an array containing an estimate (the number of matches) for 10 different mesh sizes. It might look something like this:

 gridscores[] = 5,5,0,5,34,5,0,5 XgridSize = index of greatest gridSore 

• 34 is undoubtedly the best match, and it is at index 5, so the grid size is 5.

• Now that you know the size of the grid, you can easily find which points are not in this grid:

  for each point wrongpoint = (point.x mod XgridSize! = 0) or (point.y mod YgridSize! = 0)

This works even if there are many wrong points. I did not describe in detail how to rotate and how to find the offset for the grid, but perhaps this will help you in the right direction.

Answer 2

Points are located along two sets of parallel lines. The easiest way to detect these lines is to Convert hough .

After completing the Hough transform, you have a two-dimensional histogram, where one dimension (columns) corresponds to the direction of the line, and the other dimension (rows) to the offset of the line. Add together the elements of one column and find the two maximum values ​​in the resulting vector. Add the elements of the same row for the columns close to one of these maxima, and find the periodic pattern in the resulting vector ( A quick Fourier transform can help Here). Do the same for another maximum.

As a result, you have a direction, a period, and an offset for each of the two sets of parallel lines. To fill the rectangle with the corresponding points, just get the intersection of these sets of lines.