CODEWITHSUNDEEP
algorithm2dpolygonrectangles
Hubert OG
Hubert OG

Reputation: 19544

Filling a polygon with maximum number of grid squares

I've got a 2d polygon.

enter image description here

I'm placing it on a square grid and marking the squares that are completely inside the shape.

enter image description here

I need to find the placement that maximizes number of marked squares. The polygon orientation is fixed, it can be only translated.

enter image description here

How can I do so?

Upvotes: 4

Views: 1731

Answers (2)

Paul
Paul

Reputation: 154

Let's solve the problem for the case if we can only move our polygon P to the right and the width of the cell equals w.

First of all, notice that it is enough to explore shifts for the distance dP in [0; w), because if we move P to w to the right we get the same situation as if we didn't move it at all.

Let SP to be an amount of cells currently in P. Suppose we moved P for a little. What could happen? Well, some of the vertices of the grid now could be out of P (let's call this set O), and some new vertices could be now in P (set I). How to determine if we lost or acquired any cells? If a cell was in P and had corner, which is in O, then we should decrease SP. If, on the contrary, a cell has corners in I and other corners are already in P, then we should increase SP.

Let's now sort these events (acquiring and losing of vertices) by increasing it's distances from the initial position of P. Thus we formalized the order of our "little steps" in algorithm.

Now we can write some pseudocode:

def signedDistance(vertex, edge):
    p = [ closest point of edge to vertex ]
    return vertex.x - p.x

Events = { (vertex, edge) : 0 <= signedDistance(vertex, edge) < w }
sort(Events, [ by increasing signedDistance ])
EventsEquiv = { E' : E' is subset of Events and
                    for any a, b from E'
                    signedDistance(a.vertex, a.edge) = signedDistance(b.vertex, b.edge) }
S = [ cells in P initially ]
maxS = S
for E' in EventsEquiv:
    for e in E':
        if e is loss: S -= 1
        else if e is acquirement: S += 1
    if S > maxS:
        maxS = S

The method is close to the sweep line.

UPD: To generalize this we need to notice that for any optimal position of P exists another optimal position that P has a grid vertex on an edge. So the solution is to fix some grid vertex G and move P "around" it so P always has G on an edge step by step, where steps are produced by the events occuring, which were described above. Algorithm takes O(|P| / w).

Upvotes: 3

Adrian Kowol
Adrian Kowol

Reputation: 21

The polygon is large, the size of the grid squares small (e.g. 10x10 pixel)?

Then there is one simple bruteforce solution:

  1. Start with one grid, count the squares.

2.1-2.10 Move the grid 1px to the right, count and update best score if nec.

  1. Move the grid 1px up, count and update best score if nec.

  2. repeat aka go to 2.1 until all possible solutions checked...

It's easy to check if a square is within a polygon or not. You could implement an algorithm that goes along the edges...

Upvotes: 1

Related Questions