algorithm - 获取简单的多边形

Question

我有一个多边形 C，如下所示:

C = 10     0
     2     0
     2     2
     0     2
     2     0
     0     0
     0    10
    10    10

其中第一列表示 x 的坐标，第二列对应多边形 C 的 y 坐标。正如你在上图中看到的，这不是一个简单的多边形(这个多边形包含一个由白色指定的孔)，所以我想从 C 中获取所有不包含孔的简单子(monad)多边形。在这种情况下，输出应如下所示:

    C1 =  0     2
          2     0
          0     0

    C2 =  2     0
          2     2
          0     2
          0    10
         10    10
         10     0

其中C1和C2分别对应红色小三角和红色大多边形。

问题是如何生成这个子多边形？

任何想法将不胜感激。

Answer 1

首先我们可以假设所有交点都存在吗？很容易想出以有趣的方式与自身相交的多边形。但是使用类似 http://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm 的东西您应该能够找到并添加所有交叉路口。

接下来我将做一个简化的假设，即我们永远不会反向遍历线段。 (您可以通过多种方式处理该病态病例。)

处理完这些细节后，接下来我们需要定位所有可以由这些点定义的最小多边形，无论它们最终是否被算作内部或外部。 (为方便起见，我们将在无穷远处添加一个“点”，并将外部视为多边形。)为此，我们首先获取每个点，并按逆时针顺序列出它直接连接的点。 (平行于 x 轴的方向是 0 度，与 y 轴的方向是 90 度，x 轴的负方向是 180 度，然后当你向下走得更远时我们环绕。)所以对于你的例子，我们会得到一些东西像这样:

( 0,  0): ( 2, 0), ( 0, 2)
( 2,  0): (10, 0), ( 2, 2), ( 0, 2), ( 0, 0)
(10,  0): (10,10), ( 2, 0)
( 0,  2): ( 0, 0), ( 2, 0), ( 2, 2), ( 0,10)
( 2,  2): ( 2, 0), ( 0, 2)
( 0, 10): ( 0, 2), (10,10)
(10, 10): (10, 0), ( 0,10)

现在每个简单的多边形都将击中其中两个点之间的每个点，反之亦然，我们可以取其中一个间隙(包括环绕)并在每个角轻松生成关联的多边形尽可能逆时针转动(即从我们到达的那一点到之后的那一点，可能是环绕)。对于每条线段，多边形将位于右侧。当我们拥有每一个点和差距时，我们知道我们拥有所有这些。因此，在上述情况下，我们将从 ( 0, 0) 和以下点 ( 2, 0) 开始，然后我们查看 ( 2, 0) 发现( 0, 0) 后面跟着(10, 0), 转到(10, 0) 并发现 ( 2, 0) 后面是 (10,10) 并以此方式进行追踪:

( 0, 0), ( 2, 0), (10, 0), (10,10), ( 0,10), ( 0, 2), ( 0, 0)

(请注意，由于方向的原因，这跟踪了外部区域。)

现在我们从 ( 0, 0) 和备用起点 ( 0, 2) 开始，做同样的操作得到:

( 0, 0), ( 0, 2), ( 2, 0), ( 0, 0)

(这是小内三角。)

对于( 2, 0)，我们还没有到达( 2, 2)。让我们开始吧。

( 2, 0), ( 2, 2), ( 0, 2), ( 0,10), (10,10), (10,0), ( 2, 0)

(这是大的不规则多边形。)

对于 ( 2, 0) 我们还没有到达 ( 0, 2) 所以让我们这样做:

( 2, 0), ( 0, 2), ( 2, 2), ( 2, 0)

(这是白色的小三角形。)

然后枚举我们可能想要经过的所有可能的有向线段，会发现我们已经涵盖了所有这些。所以这些是我们的多边形。现在我们要弄清楚里面是什么，外面是什么。有一个简单的技巧。找到一个 y 值可能最低的点(如果有平局，任何一个都可以)。例如，假设我们选择了 ( 2, 0)。逆时针排列的连接点是(10, 0), ( 2, 2), ( 0, 2), ( 0, 0)。它们分别是外部、内部、外部、内部……此外，一旦给定多边形的一条边被标记为外部或内部，其所有有向边都是相同的。因此我们很容易得到:

outside:
  - (10, 0), ( 2, 2), ( 0, 2), ( 0, 0)
  - ( 2, 0), ( 0, 2), ( 2, 2), ( 2, 0)

inside:
  - ( 2, 0), ( 2, 2), ( 0, 2), ( 0,10), (10,10), (10, 0), ( 2, 0)
  - ( 0, 0), ( 0, 2), ( 2, 0), ( 0, 0)

你的答案将只是内部多边形。

(小优化，我们根本不需要画外面的多边形。我们可以取第一条我们发现方向的线段，画出一条里面的线段，然后到它的一个角，确定方向接触那个角的线段，并开始绘制其他内部多边形。如果我们正确地跟踪，我们最终会得到它们。)