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

Question

我试图使用众所周知的2遍扫线算法实现多边形三角剖分，该算法在第一遍扫线中将多边形细分为单调子分量，然后在第二遍对这些单调分量进行三角剖分。我目前的实现适用于一般情况，但我一辈子都想不出如何调整它来处理包含多个重合边缘段的输入（从左到右扫描时具有相等的x坐标或从右到左扫描时具有相等的y坐标的段）。

编辑：我刚意识到我的框架这个问题的方式使它相当长和冗长，所以这里有一个快速的TL；Dr；对于任何了解多边形三角剖分但不想通读整件事的人来说：下面的形状是三角剖分算法第二遍的有效输入吗？如果是：如何调整第二次传递以处理它，如果不是：如何调整第一次传递以使其产生可以输入第二次传递的单调子组件：

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

这一点下面的问题的长版本；-）

一个非常快速的算法概要：

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

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

当我在算法中输入这个形状时，单调细分过程不会触及形状：其中有垂直边，所以严格来说它不是单调的，但它是单调的，就我对算法的理解而言，在三角化之前，它不必被细分（也许这是我出错的地方，因为我的假设是错误的）。

>

我用来实现算法的一些原始材料说“在增加y坐标时对等x坐标的顶点排序”，即:1、2、5、6。如果我这样做并扫描它们，第一个三角形就可以了（0,1,2)，但在此之后，算法将添加一个边（5,2)，这将创建一个4顶点分量（0,2,5,6）。没有边（0,5）被添加，因为三角化算法规定将边添加到反射链上除第一个以外的所有前面的未三角化顶点（改变这一点将打破一般情况）。虽然由4个顶点围成的多边形区域是三角形，但它显然不是三角形，因为它有4个点，而且根据大多数定义，它也不是有效的多边形，因为它有共线边。

我读到的另一篇论文说‘打破联系，这样链序就可以保持’。这意味着我的例子中的4个顶点将被排序为1、2、6、5，因为上下链都是从左到右运行的。如果我按这种顺序扫描它们，我再次得到一个三角形(0，1，2)，但扫描的下一个顶点(6)，将创建一个多边形(0，1，6)，这比第一种情况更糟糕，因为它创建了一条边(1，6)，它在顶点5上运行，但不包含它。扫描顶点5将完全扰乱算法的状态，因为它将创建一个退化的三角形（1,5,6）,一条线，并且扫描尾顶点将无法对多边形的剩余部分进行三角剖分

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

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

我用来实现该算法的主要来源是最初的GJPT-78论文，它介绍了三角剖分算法，它没有公开可用（paywall），所以我不能在这里链接，但网上有很多CS课程材料描述了该算法，我也使用了这些例如：

http://www.cs.ucsb.edu/~suri/cs235/triangulation.pdf https://www.cs.umd.edu/class/spring2012/CMSC754/lects/CMSC754-lects.pdf（见“第六讲”章节）

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

也许我只是有点愚蠢，或者错过了一些非常明显的东西，但我已经在试图解决这个角落的情况下折腾了几天，现在没有结果，这开始变得非常令人沮丧。我假设为基本情况实现算法（包括编写DCEL数据结构、扫描线算法、排序边缘图、确定内部角度和可见性所需的三角学、有效存储和查找顶点分类的数据结构等）几乎是所有工作，之后修复垂直边缘问题将是微不足道的。现在，我花了更多的时间来修复垂直边缘，而不是所有其他的东西，我需要让算法工作在一般情况下（它完美地工作于任何我抛出的多边形，只要它没有垂直边缘）。

谢了！沃特尔

Answer 1

我自己终于想通了，所以我来回答我自己的问题，为了子孙后代；-）

事实证明，使三角剖分算法适用于具有垂直边的多边形的变化是最小的，并且不需要特殊情况来处理它们。我不得不改变以下事情：

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

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

我不得不做的第二个改变是因为我曲解了各种顶点分类。我的假设是一个合并顶点应该总是有两个关联边完全在它的左边，一个分裂顶点完全在它的右边，这是不正确的。如果两条入射边中的一条是垂直的，另一条在顶点的左边，则应归类为“合并”，如果另一条在顶点的右边，则应归类为“分裂”。特别是，我不得不改变以下几行：

// 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.destinathtml" target="_blank">ion.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个共线性点的退化三角形。当对单调子分量进行三角剖分时，每当在与堆栈上的顶点（“反射链”）相同的多边形链上发现一个顶点时，从当前扫描线顶点向所有可见的反射链顶点添加对角线。在我的实现中，可见性是通过查看堆栈顶部顶点的（有符号的）内角来确定的。该检查只查看了角度的符号，其中正角度表示可见（内部小于或等于圆周率弧度，或180度）。问题是关于或相等的部分，如果堆栈顶部的2点加上当前扫描线顶点是共线的，内角正好是π弧度，不应该添加对角线。我不得不把支票改成这样：

BOOL visible = (vi_x_interior_angle > 0.0f);

对此：

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

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