具有共线、垂直边段的单调多边形三角剖分

Question

我正在尝试使用众所周知的双通道扫描线算法来实现多边形三角测量，该算法将多边形细分为第一通道扫描线中的单调子组件，然后在第二通道中对这些单调组件进行三角测量。我当前的实现适用于一般情况，但我一生都无法弄清楚如何调整它来处理包含多个重合边缘段的输入（从左到右扫描时具有相同 x 坐标的段，或者从右向左扫描时 y 坐标相等）。

编辑：我刚刚意识到我提出这个问题的方式使它变得相当长和冗长，所以这里有一个快速的TL;DR; 对于任何了解多边形三角测量但不想阅读整个内容的人：以下形状是三角测量算法第二遍的有效输入吗？如果是：如何调整第二遍来处理它，如果否：如何调整第一遍，使其生成可以输入第二遍的单调子组件：

http://www.wouterbijlsma.nl/~wouter/tmp/RTdr6rET9.png

此点以下问题的长版本;-)

该算法的快速概述：

1. 第一遍将输入多边形细分为“单调子组件”。单调子组件是一个多边形，可以分为 2 个连接的链，这些链的坐标要么从左到右排序（当使用垂直扫描线实现算法时），要么从上到下排序（当使用水平扫描时）线）。假设我们使用垂直扫描线：每个单调子组件可以分为上链和下链，在最小和最大 x 坐标处连接，并且当扫描任一链的顶点时，x 坐标为增加。如果子组件是严格单调的，则上链和下链不能具有具有相同x坐标的边缘段（即：垂直边缘段）。

2. 第二遍扫描单调子组件，并通过添加内部边缘将它们细分为三角形。这个想法是，每个子组件从左到右扫描，并且在扫描线击中的每个顶点处，可能会发生以下两种情况之一：a）可以通过添加对角线来对扫描线左侧的未三角化区域进行三角剖分，或 b) 当前顶点无法“看到”扫描线左侧未三角化区域中任何先前扫描过但未处理的顶点。在情况 b) 中，顶点被压入堆栈（“反射链”），并且通过构造，在某个时刻会发生情况 a)，并且反射链的顶点将被一一弹出并与到最后一个扫描线顶点的对角线。

上面的描述缺乏一些细节，但我假设任何知道如何回答我的问题的人都已经理解了该算法，所以我不会在这里详细介绍。

我遇到的问题如下：假设我有一个代表指向左的箭头的多边形，例如如下所示：

http://www.wouterbijlsma.nl/~wouter/tmp/RTdr6rET9.png

当我将这个形状输入到我的算法中时，单调细分过程不会影响该形状：其中有垂直边缘，因此它不是严格单调的，但它是单调的，并且据我了解该算法，它不必在对它进行三角测量之前先对其进行细分（也许这是我出错的地方，因为我的假设很糟糕）。

现在假设我将（未修改的）箭头多边形输入第二遍以对其进行三角测量。如何处理箭头底部的 2 个垂直边缘段？扫描线算法要求多边形的顶点从左到右排序，因此您会假设答案将归结为如何对具有相同 x 坐标的顶点进行排序（例如，按链顺序，或在 y 坐标上，或在多边形边界索引上），但无论我使用什么排序，三角测量总是会失败。

我们将最左边的顶点称为顶点 0，并按逆时针顺序对顶点进行排序。这意味着箭头底部的 4 个顶点是顶点 1、2、5 和 6。我们有三种排序选项：

1. 我用来实现该算法的一些源材料说“在增加 y 坐标的情况下对具有相等 x 坐标的顶点进行排序”，即：1、2、5、6。如果我这样做并扫描它们，第一个三角形就出来了（ 0, 1, 2)，但之后算法将添加一条边 (5, 2)，从而创建一个 4 顶点组件 (0, 2, 5, 6)。不添加边 (0, 5)，因为三角剖分算法规定将边添加到反射链上除第一个之外的所有先前未三角化的顶点（更改此设置会破坏一般情况）。虽然由 4 个顶点包围的多边形区域的形状是三角形，但它显然不是三角形，因为它有 4 个点，而且根据大多数定义，它也不是有效的多边形，因为它具有共线边。

2. 我读到的另一篇论文说“打破联系，从而保留链序”。这意味着我的示例中的 4 个顶点将排序为 1、2、6、5，因为下部链和上部链都是从左到右运行的。如果我按这个顺序扫描它们，我会再次得到一个三角形 (0, 1, 2)，但是扫描的下一个顶点 (6) 将创建一个多边形 (0, 1, 6)，这比第一种情况更糟糕，因为它创建一条边 (1, 6)，该边经过顶点 5 但不包含它。扫描顶点 5 将完全扰乱算法的状态，因为它将创建一个退化三角形 (1, 5, 6)、一条线，并且扫描尾部顶点将无法对多边形的其余部分进行三角剖分

3. 按原始多边形顶点顺序排序（沿边界，逆时针）：在这种情况下，这将产生与情况 1）相同的结果，即：1, 2 5, 6，这已被证明是失败的。

我开始认为，也许像这样的箭头形状应该被认为是非单调的，或者（尽管我从未在任何算法描述中看到过这一点）单调三角剖分算法要求输入严格单调。这可能是我所缺少的东西吗？如果是，我需要如何调整单调细分通道来处理（多个、重合的）垂直边缘段？我使用的源材料在细分期间将所有顶点分类为“开始”、“结束”、“合并”、“分割”或“常规”（下/上），但在垂直线段的情况下，这些分类是不明确的：根据对于这些顶点类的定义，垂直线段的顶点部分可以被认为是开始/结束顶点，但也可以被认为是分割或合并顶点。或者也许我确实必须在 y 坐标上对 4 个顶点进行排序，然后创建一个具有 2 个共线边的无效 4 顶点三角形组件，然后通过删除共线边上的顶点来“修复它”？

我用来实现该算法的主要来源是介绍三角测量算法的原始 GJPT-78 论文，它不是公开可用的（付费专区），因此我无法在此处链接它，但是可以在线获取大量 CS 课程材料，其中描述了算法，我也使用了这些例如：

http://www.cs.ucsb.edu/~suri/cs235/Triangulation.pdf https://www.cs.umd.edu/class/spring2012/cmsc754/Lects/cmsc754-lects.pdf（参见“讲座 6”） ' 章节）

我已经读了很多这样的内容。几乎每组幻灯片、论文、博客或任何其他算法描述都特别提到具有相等 x 坐标（或 y 坐标，如果使用水平扫描线）的顶点，但它们都只是说“我们假设没有相等的 x-”坐标”，并且这种限制“很容易修复，仅用于简化表示”或“不是算法的基础”或其他什么。奇怪的是，他们都没有关心详细说明支持这种情况所需的更改或解决方法，或者他们包含一些关于以某种方式对相等的 x 顶点进行排序的模糊语句，但实际上并不能解决问题。

也许我只是有点愚蠢或者错过了一些非常明显的东西，但是我已经花了好几天时间试图解决这个极端情况，但没有结果，而且它开始变得非常令人沮丧。我假设实现基本情况的算法（其中涉及编写 DCEL 数据结构、扫描线算法、排序边缘图、确定内角和可见性所需的三角学、有效存储和查找顶点分类的数据结构等） ）几乎是所有工作，之后解决垂直边缘问题将是微不足道的。现在，我花了更多的时间尝试修复垂直边缘，而不是我需要的所有其他东西，以使算法适用于一般情况组合（它适用于我扔给它的任何多边形，只要它不） t 有垂直边缘）。

谢谢！沃特

Answer 1

我终于自己弄清楚了这一点，所以我会为后代回答我自己的问题;-)

事实证明，使三角测量算法适用于具有垂直边缘的多边形的更改很小，并且不需要特殊情况来处理它们。我必须改变以下事情：

1. 在增加的 y 坐标上对具有相等 x 坐标的顶点进行排序（注意：我使用垂直扫描线，对于水平扫描线，首先对 y 进行排序，然后对 x 进行排序）
2. 将具有入射垂直边的顶点分类为“合并”或“分割”，而不是“常规向上/向下”（也称为“上链/下链”）
3. 当反射链的最后 2 个点与当前扫描线顶点共线时，切勿添加对角线

大多数关于该算法的论文都提到了第一个要求。从下到上排序具有与符号顺时针旋转相同的效果，就像 David Eisenstat 提到的那样。

我必须做出的第二个改变是因为我误解了各种顶点分类。我的假设是，合并顶点应始终将两个入射边完全置于其左侧，将分割顶点完全置于其右侧，这是不正确的。如果 2 个入射边之一是垂直的，而另一个在顶点的左侧，则应将其分类为“合并”，如果另一条边在右侧，则应将其分类为“分割”。特别是，我必须更改以下几行：

// Classify vertex based on the interior angle and which side of the sweep line the two edges are
BOOL reflex_vertex = (interiorAngle < 0);

BOOL both_left = (e_in.origin.coordinates.x < vertex.coordinates.x) && (e_out.destination.coordinates.x < vertex.coordinates.x);
BOOL both_right = (e_in.origin.coordinates.x > vertex.coordinates.x) && (e_out.destination.coordinates.x > vertex.coordinates.x);

if (!reflex_vertex && both_right)
  type = K14SweepLineVertexTypeStart;

else if (!reflex_vertex && both_left)
  type = K14SweepLineVertexTypeEnd;

else if (reflex_vertex && both_right)
  type = K14SweepLineVertexTypeSplit;

else if (reflex_vertex && both_left)
  type = K14SweepLineVertexTypeMerge;

else if ([_lowerChainVertices containsObject:@(vertex.id)])
  type = K14SweepLineVertexTypeLowerChain;

else
  type = K14SweepLineVertexTypeUpperChain;

对此：

// Classify vertex based on the interior angle and which side of the sweep line the two edges are
BOOL reflex_vertex = (interiorAngle < 0);

BOOL both_left = (e_in.origin.coordinates.x <= vertex.coordinates.x) && (e_out.destination.coordinates.x <= vertex.coordinates.x);
BOOL both_right = (e_in.origin.coordinates.x >= vertex.coordinates.x) && (e_out.destination.coordinates.x >= vertex.coordinates.x);

...

最后一项更改是必要的，以防止输出中出现具有 3 个共线点的退化三角形。对单调子组件进行三角测量时，每当在与堆栈上的顶点（“反射链”）相同的多边形链上找到顶点时，就会将对角线从当前扫描线顶点添加到所有可见的反射链顶点。在我的实现中，可见性是通过查看堆栈顶部顶点的（有符号）内角来确定的。此检查仅查看角度的符号，其中正角度表示可见（内部小于或等于pi 弧度，即 180 度）。问题在于或等于部分，如果堆栈顶部的 2 个点加上当前扫描线顶点共线，则内角恰好为 pi 弧度，并且不应添加对角线。我不得不更改支票：

BOOL visible = (vi_x_interior_angle > 0.0f);

对此：

BOOL visible = (vi_x_interior_angle > 0.0f) && ((vi_x_interior_angle + COMPARE_EPSILON) < M_PI);

我使用一个小的 epsilon，如果你的顶点是静态/硬编码的并且垂直边缘的 x 坐标完全相等，那么这并不是真正必要的，但在我的情况下，顶点可能是计算出来的，并且可能有小的舍入误差。如果 3 个点几乎完全共线，则不添加对角线通常会比添加面积几乎为零的三角形产生更好的结果。

除了这三件事之外，不需要任何特殊处理即可使算法适用于您扔给它的任何简单多边形（无自交，无孔）。我有点沮丧，因为我浪费了至少 20 个小时来解决这个问题，但至少我终于让这个愚蠢的事情发挥作用了。只是希望我读到的关于这个特定算法的许多论文中至少有一篇能够更明确地说明我在实现中错过的三件事：-/