将轮廓转换为二维 bool 数组的算法

Question

我想创建表示轮廓(边列表)给出的几何形状的二维数组。形状总是可以被分割成矩形基元并放置在网格上(就像在带有方格纸的笔记本中一样)。我的目标是创建代表网格的 2D bool 数组，哪些字段是:true - 如果网格单元在轮廓内(是形状的一部分)，否则为 false。有谁知道如何实现这一目标？我为此花了几个小时，但仍然一无所获。

Answer 1

让 left(row, column) 为真当且仅当位于 (row, column) 的单元格在其左边界上有一条边(这很容易从边列表中计算出来)。然后:

for each row
    inside = false
    for each column
        if (left(row, column) == true)
            inside = !inside
        isInside[row, column] = inside

isInside 是您的 bool 网格。该算法完全忽略水平边缘并假设形状是封闭的(因此“内部”和“外部”有意义)。如果形状不是封闭的，那么结果就没有意义，因为没有内部和外部。

这是最优的(因为它与输出的大小成线性关系)。