如何用等距水平线填充闭合折线？

Question

I need to write and algorithm that fills closed poly-line with horizontal equidistant lines.

我用矩形和圆做了类似的事情，这里是后者的代码片段：

// circle parameters: center(point(0).x, point(0).y), radius
int offsetX = point(0).x + radius;
int offsetY = point(0).y + radius;
for(int i = -radius; i < radius; i += spacing){
    int ry = i;
    int rx = sqrt(double(radius*radius - ry*ry));
    // the parameters are pair of coordinates of the horizontal line
    fl_line(offsetX - rx, offsetY + i, 
            offsetX + rx, offsetY + i);
}

在闭合折线的情况下，额外的难度（对我来说）是水平线的坐标不会从单个方程（圆, 矩形的高度等），而是来自具有相同 "y" 坐标的直线方程，它们不会连续匹配。

问题：

您能否提供一些关于如何继续创建用水平线填充闭合多段线的算法的见解？

Answer 1

这只是扫描线算法的一个特例（专为填充多边形而设计）：http://www.tutorialspoint.com/computer_graphics/polygon_filling_algorithm.htm

使用所需步长（间距）从 yMin（多边形顶部）到 yMax 迭代 y。

对于每个 y，找到与多边形线段的交点，按它们的 x 坐标对它们排序，用一条线连接每一对其他线段

Answer 2

创建所有边的列表，其中最低端点在前。通过增加纵坐标（最低端点）对列表进行排序。

创建一个 "active list" 将包含与当前水平线相交的所有边。

初始化最低边缘下方的当前水平位置，并确保活动列表为空。

以所需的增量向上移动水平方向，直到活动列表再次清空。

移动时，从活动列表中丢弃不再与它相交的边。还要向它添加将开始与它相交的边（边被排序后，您将搜索不超过需要的部分）。

注意一条边可以完全跳过（它可以进入活动列表并立即离开）。

当活动列表是最新的时，计算所有交点并通过从左到右的水平线段连接它们。

请注意，通过在必要时小心插入新边，可以避免在成对连接交叉点之前进行水平排序。鉴于活动列表通常很短，我更喜欢系统地应用插入排序。

假设所有活动列表操作都在列表大小上花费线性时间，总时间就像O(Ne.Lg(Ne) + Ny.L)，其中Ne是边数，Ny水平线的数量和 L 每个水平线的平均交叉点数（通常在 2 到 4 之间）。这将与朴素算法的 O(Ne.Ny) 进行比较。

如何用等距水平线填充闭合折线？

How to fill a closed poly-line with equidistant horizontal lines?

c++

algorithm

computational-geometry

问题：