查找由相邻格点组成的面的所有内部格点 [英] find all inner grid points of a polygon made up from neighbouring grid points

问题描述

我有点列表(int x，int y)。 它们一起形成区域，我检查该区域是否闭合，然后需要由该区域内的所有位置形成内部区域。

示例区域：

我唯一的想法是将这个区域转换为矢量，并检查每个点是否在多边形内，计算多边形的交点和点轴。

但我认为这不是最有效的方法。

另一个想法是首先获取所有外部的点，我从角点开始(如果角点不在点列表中，则为100%空)，添加所有空的邻接点，然后重复。 则所有不在外部且不在突出显示列表中的点都在内部。

但又一次，它感觉有点麻烦...

推荐答案

若要查找网格多边形的所有内部网格点，可以使用以下观测：

1. 对于每个内部网格点(x，y)，(x，y+0.5)和(x，y-0.5)也是内点。
2. y=n+0.5定义的线与格网多边形有简单的交点

这将导致以下算法：

1. 作为先决条件，需要所有非水平(即垂直和对角)多边形边，实际上只需要每个(第二个)中间行的中心的x坐标按升序排列。

网格在每隔一秒的水平"中线"处被扫描，即，其中n来自足够的整数范围s.t。该多边形被"覆盖"，请参见拼图中的蓝色线条。
2. 从左侧开始，要检测与多边形(即非水平边)的所有交点和表单(m，2n+0.5)的所有内点，请看到红色和绿色的圆圈(这是通过在边的中心的x坐标上迭代来完成的)
3. 现在内点(m，2n+0.5)的垂直网格邻域(m，2n)和(m，2n+1)是内点，如果它们不在边界上，请参见截图中的绿点。

以下是一些伪代码(受C++/Python启发：-)：

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)

这篇关于查找由相邻格点组成的面的所有内部格点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！