找出由相邻网格点组成的多边形中的所有内部网格点

Question

我有一组点的列表（int x，int y）。它们在一起形成了一个区域，我会检查这个区域是否封闭，然后需要获取由所有位于此区域内的位置形成的内部区域。

示例区域： 我唯一想到的方法是将该区域转换为向量，并检查每个点是否在多边形内部，计算与点的轴交叉的多边形的交点数量。但我认为这不是最有效的方法。

另一个想法是先获取所有在外部的点。我从角落开始（如果角落不是点列表的一部分，则为空），添加所有空的邻居点并重复。然后，在高亮列表中既不在外部也不在内部。

但是，这种方法似乎很繁琐...

- aacid

---

听起来很像凸包。 - Bernhard Barker

@Dukeling 谢谢，看起来这可能是解决方案，我会仔细研究它。 - aacid

@AlexeyFrunze 它可以有洞。 - aacid

1. 我实际上需要其中的点列表。
2. 对不起我的英语不好，我是指所有的点都连接在一起形成一个闭合的圆。

- aacid

那么，您可以将标题编辑为“查找由相邻网格点组成的多边形的所有内部网格点”。 - coproc

Answer 1

寻找网格多边形的所有内部网格点，可以利用以下观察结果：

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

这导致以下算法：

1. 作为前提条件，需要所有非水平（即垂直和对角线）多边形边缘，实际上只需要每个（第二个）中间行的升序中心的 x 坐标。 2. 在每个第二个水平 "中间线"，即 y=2n+0.5 处扫描网格，其中 n 是足够范围的整数，使得多边形被 "覆盖"，请参见 scetch 中的蓝色线。 3. 从左侧开始，检测与多边形的所有交点（即非水平边缘）和所有形式为 (m,2n+0.5) 的内部点，参见红色和绿色圆圈（这是通过迭代边缘中心的 x 坐标完成的）。 4. 如果垂直网格邻居 (m,2n) 和 (m,2n+1) 不在边界上，则内部点 (m,2n+0.5) 的垂直网格邻居 (m,2n) 和 (m,2n+1) 也是内部点，参见 scetch 中的绿色点。

以下是一些伪代码（受 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)

- coproc

---

谢谢！看起来很有趣，今晚会和 Graham扫描算法(如Dukeling所建议的)一起测试一下，看哪个更好用。你的解决方案看起来更简单，我会看看它是否适用于所有情况。 - aacid

Answer 2

皮克定理 可能是你正在寻找的公式。它可以简单地计算由网格点（即具有整数坐标的角落）组成的多边形的面积。

- coproc

---

抱歉，我可能表达问题不清楚。我不需要进行数学计算以获取面积，我需要得到一个包含点的列表，这些点在图形内部。 - aacid

好的，而且内部点的数量恰好是Pick公式的一个输入参数 :-) 所以你最终会面临相同的问题。 - coproc