CODEWITHSUNDEEP
algorithmgeometry
krzych
krzych

Reputation: 2176

Filling rectangle with points pattern

On images below there is some specific pattern. Its best visible on first image. I have points marked with small circes and connected with lines. They make some net pattern. Some points are wrong and does not fit to pattern (marked on first image). The objective is to fill whole rectangle marked with red (rectangle is created from extremal points - points with extremal coordinates in pattern coordinate system).

The question is what approach should be taken to fill rectangle with points, and eliminate wrong points. Situation on second image is extremal but mainly cases are with more points.

Images are only for visualization. I've got vectors with points coordinates. There is no need to detect points.

I will add my solution as soon as I figure out one.

My current approach is to create lines parallel to longer rectangle sides with known pattern offset. Then to look for points with some delta distance near lines, and fill the rest points.

Upvotes: 3

Views: 691

Answers (2)

Wouter van Nifterick
Wouter van Nifterick

Reputation: 24116

Overall, what I would do is first determine the grid, and then it's easy to check if something is on that grid or not.

These are the steps:

  • rotate everything so that you've only got horizontal and vertical lines.

  • Per x value count how many points you have.

  • Per y value count 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 detect the grid size:

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

Now we have an array that contains the score (number of points that match) for 10 different grid sizes. It could look something like this:

gridscores[] = 5,5,0,5,34,5,0,5

XgridSize = index of greatest gridSore

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

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

    foreach point do wrongpoint = (point.x mod XgridSize != 0) or (point.y mod YgridSize != 0)

This works even if there are a lot wrong points. I didn't get into the details on how to rotate and how to find the offset for the grid, but maybe this helps you into the right direction.

Upvotes: 3

Evgeny Kluev
Evgeny Kluev

Reputation: 24677

The points are located along two sets of parallel lines. Easiest way to detect these lines is Hough transform.

After performing Hough transform, you have a 2D histogram, where one dimension (columns) corresponds to line direction, other dimension (rows) - to line offset. Add together elements of the same column and find two maximum values in the resulting vector. Add together elements of the same row for columns, close to one of these maximums, and find periodic pattern in the resulting vector (Fast Fourier transform may help here). Do the same for other maximum.

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

Upvotes: 2

Related Questions