了解如何用最少数量的矢量线填充多边形

Question

假设我有一个带孔的矢量多边形。我需要通过绘制连接的线段来填充它。当然，由于存在漏洞，我无法使用单个连续的折线来填充它：有时我需要中断我的路径，然后移动到被跳过的区域并在那里开始另一条折线。

我的目标是找到填充整个多边形所需的一组折线。如果我能找到最小集合（也就是说，我可以用最少的中断数填充多边形的方式），那就更好了。

额外问题：对于部分密度填充，我该如何做到这一点？比如说，我不想以 100% 的密度填充，但我想要 50% 的密度（这将要求填充线，假设它们彼此平行并且具有单一单位宽度，则放置在两个单位的距离处）。

我在这里找不到类似的问题，尽管有很多与洪水填充算法相关的问题。

有什么想法或指示吗？

更新：这张图片来自维基百科 显示了一个良好的假设洪水路径。我相信我可以使用位图来做到这一点。不过我有一个矢量多边形。我应该光栅化它吗？

Answer 1

我在这里假设线之间的距离是 1 个单位。
不保证找到最少数量的折线的粗略实现是：

1. 从一组空的折线开始。
2. 确定多边形的 minx 和 maxx。
3. 从 xmin 到 xmax 循环 x，步长为 1。线 L 是 x 处的垂直线。
   • 垂直线 L 与多边形相交（快速算法，易于找到）。这将为您提供一组线段：{(x,y1)-(x,y2)}。
   • 对于所有折线和所有线段，合并线段 + 折线末端（请参阅下面的注释 1）。合并线段和多段线时，请在多段线的末端附加一小段拉伸（以将其连接到线段）以及线段本身。对于无法使用它合并的所有线段，请在全局集中添加新的折线。
4. 最后，如果可能的话，尝试再次合并多段线（两端靠近）。

将新线段合并到现有多段线的最佳算法应该很容易找到（在 y 上散列），或者强力算法可能就足够了：

1. 如果您的多边形没有无数的孔，则每行扫描的新线段数量不应太高，
2. 每一步的全局多段线数量不应该太大，
3. 您仅与每条多段线的末端段进行比较，而不是与整个多段线进行比较。

添加注释 (1)：为了涵盖多边形具有几乎垂直边缘的情况，合并过程不应仅查看 y-delta，而应允许在任何两个 y 范围重叠时进行合并（即表示折线 y 范围重叠线段 y 范围的末端）。