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

Question

假设我有一个带孔的矢量多边形。我需要通过绘制连接的线段来填充它。当然，因为有洞，我不能用一条连续的折线来填充它:有时我需要打断我的路径，然后移动到一个被跳过的区域并在那里开始另一条折线。

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

奖励问题:我怎样才能为部分密度填充做到这一点？比如说，我不想以 100% 的密度填充，但我想要 50%(这将需要填充线，假设它们彼此平行并且具有单个单位宽度，则放置在两个单位的距离处).

虽然有很多与 flood-fill 算法相关的问题，但我在这里找不到类似的问题。

有什么想法或建议吗？

更新:这张图片来自Wikipedia显示了一个良好的假设洪水路径。我相信我可以使用位图来做到这一点。但是我有一个矢量多边形。我应该栅格化它吗？

Answer 1

我在这里假设线之间的距离是 1 个单位。无法保证找到最小折线数的粗略实现是:

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

将新段合并到现有多段线的最佳算法应该很容易找到(在 y 上进行散列)，或者蛮力算法可能就足够了:

1. 如果您的多边形没有无数个洞，则每次线扫描的新线段数量不应太高，
2. 每一步的全局折线数量不宜太大，
3. 您只比较每条折线的末端部分，而不是整个折线。

添加注释 (1):为了涵盖多边形具有几乎垂直边缘的情况，合并过程不应只查看 y-delta，但如果有任何两个 y 范围则允许合并重叠(这意味着折线 y 范围的末端重叠段 y 范围)。