find all inner grid points of a polygon made up from neighbouring grid points

Question

I have list of Points (int x, int y). together they form areas, I check if this area is closed and then I need to get inner area formed by all positions that are inside this area.

example area:

Only idea I had is to convert this area to vector and check every point if it is inside polygon or not, counting intersections of polygon a axis's of point.

But I don't think it would be the most efficient way to do it.

other idea was to first get all points that are outside, I start from corners (if corner is not part of list of points, then is 100% empty), add all neighbor points that are empty and repeat. then all points that aren't outside and aren't in highlighted list are inside.

but again, it feels somehow cumbersome...

Answer 1

To find all inner grid points of grid polygon, one can exploit these observations:

1. for each inner grid point (x,y) also (x,y+0.5) and (x,y-0.5) are inner points.
2. the lines defined by y=n+0.5 have simple intersections with the grid polygon

This leads to the following algorithm:

1. As a prerequisite one needs all non-horizontal (i.e. vertical and diagonal) polygon edges, actually only the x-coords of the centers in ascending order for each (second) mid-row.

2. The grid is scanned at each second horizontal "mid-line", i.e. y=2n+0.5, where n is from a sufficient range of integers s.t. the polygon is "covered", see the blue lines in the scetch.

3. Starting from the left all intersections with the polygon (i.e. the non-horizontal edges) and all inner points of the form (m,2n+0.5) are to be detected, see the red and green circles (this is done by iterating over the x-coors of the edges' centers)
4. Now the vertical grid neighbours (m,2n) and (m,2n+1) of inner points (m,2n+0.5) are inner points, if they are not on the boundary, see the green points in the scetch.

Here is some pseudo code (C++/python inspired :-) ):

list<Point> polygon; // given polygon as list of neighbouring grid points

// get centers of non-horizontal edges organized by line
map<int, set<float> > edgeCentersX; // for each scan line the x-coords of edges in ascending order

p_i = polygon[0]
yMin, yMax =  999999, -999999
for (i=1; i<polygon.size(); ++i)
    p_i1 = polygon[i] // next point after p_i
    if (p_i.x == p_i1.x)
        continue // horizontal edges can be ignored
    yMin_i = min(p_i.y, p_i1.y)
    if (yMin_i % 2 == 1)
        continue // we only need to look at each second mid-row
    if (yMin_i < yMin)
        yMin = yMin_i
    if (yMin_i > yMax)
        yMax = yMin_i
    cx = 0.5*(p_i.x+p_i1.x)
    edgeCentersX[yMin_i].insert(cx) // store edge center (yMin_i+0.5, cx)
    p_i = p_i1

list<Point> innerPoints
for (y=yMin; y<= yMax; y+=2)
    inside = false
    cx_i = edgeCentersX[y][0]
    for (i=1; i<edgeCentersX[y].size(); ++i)
        cx_i1 = edgeCentersX[y][i]
        inside = !inside
        if (!inside)
            continue
        for (x=floor(cx_i)+1; x<cx_i1; ++x)
            pLower = Point(y,x)
            if (!polygon.contains(pLower))
                innerPoints.append(pLower)
            pUpper = Point(y+1,x)
            if (!polygon.contains(pUpper))
                innerPoints.append(pUpper)