获取简单的多边形

Question

我有一个多边形C如下:

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

其中第一列表示x的坐标,第二列对应于多边形C的y坐标.如上图所示,这不是一个简单的多边形(此多边形包含一个由白色指定的孔),所以我想从C中得到所有不包含洞的简单子多边形.在这种情况下,输出应如下:

    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)

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

（小优化，我们根本不需要绘制外部多边形。我们可以将我们发现的方向的第一条线段，描绘出内部的线段，然后走到它的一个角，识别线段的方向触摸那个角，然后开始绘制其他内部多边形。如果我们正确跟踪，我们最终会得到它们。）