3

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

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

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

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

任何想法或指示？

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

路径示例

4

1 回答 1

1

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

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

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

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

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

于 2012-02-04T13:16:30.913 回答