5

我有一个多边形 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 分别对应红色小三角形和红色大多边形。

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

任何想法将不胜感激。

4

1 回答 1

2

首先我们可以假设所有的交点都存在吗？很容易想出以有趣的方式相交的多边形。但是，使用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)

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

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

于 2012-05-08T01:02:02.090 回答