Geek asks and answers

Find all interior grid points of a polygon made up of neighboring grid points

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

example area:

enter image description here

The only idea was to convert this area into a vector and check each point if it is inside the polygon or not, considering the intersection of the polygon as the axis of the point.

But I do not think that this would be the most effective way to do this.

, , , ( , 100% ), , . , , .

, - ...

+5
3

, :

  • (x, y) (x, y + 0,5) (x, y-0.5) .
  • , y=n+0.5,

:

  • (.. ) , - () .

  • " ", .. y=2n+0.5, n - s.t. "", . .

  • , ( ) (m, 2n + 0,5) , . ( - )
  • (m, 2n) (m, 2n + 1) (m, 2n + 0,5) , , . .

AlgoScetch_innerPoints

(++/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)
+4

, . , (.. ).

0

, n .

p: p , p , n (., , ).

List<Point> innerPoints;
for each row
{
    int n = 0; // red polygon points counter
    for each Point p in row
    {
         if(IsRedPolygonPoint(p)) n++;

         bool isInnerPoint = !IsRedPolygonPoint(p) && n % 2 == 1;
         if(isInnerPoint)
         {
             innerPoints.Add(p);
         }
    }
}

, . .

0

More articles:


All Articles