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

Question

我正在尝试使用广为人知的2遍扫描线算法来实现多边形三角剖分，该算法在第一遍扫描线遍历中将多边形细分为单调子分量，然后在第二遍中对这些单调分量进行三角剖分。我目前的实现方式适用于一般情况，但是我无法终生解决如何适应包含多个重合边缘段（从左向右扫动时具有相同x坐标的段）的输入的问题，或者从右向左扫动时等于y坐标）。

编辑：
我刚刚意识到，我对这个问题的框架使它变得冗长而冗长，因此这里有一个快速的TL; DR;。对于那些了解多边形三角剖分但又不想阅读完整内容的人：下列形状是三角剖分算法第二遍的有效输入吗？如果是：如何修改第二遍以进行处理，如果否：如何修改第一遍，以使其产生可被馈送到第二遍的单调子组件：

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

这点以下的问题的长版;-)

该算法的快速总结：


第一遍将输入多边形细分为“单调子组件”。单调子组件是一个多边形，可以将其分为2个连接的链，这些链的坐标从左到右（当使用垂直扫掠线实现算法时）或从上到下（当使用水平扫掠时）线）。假设我们使用一条垂直扫掠线：每个单调子分量然后可以拆分为一条上链和一条下链，以最小和最大x坐标连接，并且在扫描任一链的顶点时，x坐标为增加。如果子组件严格是单调的，则上链和下链不能具有具有相同x坐标的边线段（即：垂直边线段）。
第二遍扫描单调子分量，并通过添加内部边缘将它们细分为三角形。这个想法是，每个子组件都是从左向右扫动的，在扫掠线命中的每个顶点处，可能会发生以下两种情况之一：a）扫掠线左侧的未三角剖分区域可以通过添加对角线进行三角剖分，或b）当前顶点无法“看到”任何先前已扫描但在扫描线左侧未三角化区域中未处理的顶点。在b）的情况下，顶点被推到堆栈（“反射链”）上，并且通过构造，在某些情况下会发生a）情况，并且反射链的顶点将被逐一弹出并与之连接最后扫描线顶点的对角线。


上面的描述缺少一些细节，但是我假设任何知道如何回答我的问题的人都已经知道该算法，因此在这里我将不再赘述。

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

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

当我将这种形状输入到算法中时，单调细分过程使形状保持不变：其中有垂直边缘，因此它不是严格的单调，而是单调的，据我了解的算法，它不必在对其进行三角剖分之前先进行细分（也许这是我做错的地方，因为我的假设很糟糕）。

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

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


我用来实现该算法的一些原始资料说“在y坐标递增时对x坐标相等的顶点进行排序”，即：1、2、5、6。如果执行此操作并对其进行扫掠，则第一个三角形会正常显示（ 0、1、2），但此后算法将添加边（5、2），从而创建4个顶点分量（0、2、5、6）。没有添加边缘（0，5），因为三角剖分算法规定将边缘添加到反射链上除第一个以外的所有先前未三角划分的顶点上（更改此规则会破坏一般情况）。虽然由4个顶点界定的多边形区域为三角形，但显然不是三角形，因为它具有4个点，并且由于具有共线边缘，因此在大多数定义中也不是有效的多边形。
我读过的另一篇文章说：“打破联系，以保持链式秩序”。这意味着在我的示例中，四个顶点将被排序为1、2、6、5，因为上下链都是从左到右排列的。如果按此顺序扫掠它们，我会再次得到一个三角形（0，1，2），但是下一个扫描的顶点（6）将创建一个多边形（0，1，6），这比第一种情况更糟，因为它创建了一条在顶点5上延伸但不包含它的边（1，6）。扫掠顶点5会完全弄乱算法的状态，因为它将创建一个退化的三角形（1、5、6），一条线，而扫掠尾顶点将无法对多边形的其余部分进行三角剖分
按原始多边形顶点顺序排序（沿边界，沿逆时针方向）：在这种情况下，其结果将与情况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

我终于自己弄明白了，所以我会回答我自己的问题，以备后代;-)

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


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


关于该算法的大多数论文都提到了第一个要求。从下到上排序具有与顺时针旋转符号相同的效果，就像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.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个小时来解决这个问题，这让我有些沮丧，但是至少我终于使愚蠢的事情开始了。只是希望我阅读的有关此特定算法的许多论文中至少有一篇更加明确地说明了我在实现过程中遗漏的三件事：-/