一个高效稳定的多边形三角化算法（支持自交和孤岛检测）

传统算法的不足提到多边形三角化算法第一反应一般就是割耳法因为它理解难度低实现难度低。 但割耳法也存在一些问题。第一是割耳法计算复杂度高最坏情况是O(n²)。第二是割耳法不支持自交哪怕自交一点点结果也可能是灾难性的把大片的外部区域也包含进了结果里。有些时候自交出现的概率不高但避免自交的成本很高我们用了割耳法又不得不防止自交。例如带曲线边的多边形三角化即使多边形不自交但三角化前曲线要离散成直线这个离散就有可能带来自交如果曲线接近重合或相切时这个概率会大大增加。自交检测和修复本身也是一个非常复杂的算法因为自交情况太多了不是简单的线线求交就行的。如果自交点出现在线的端点就要根据线的走向去判断如果多个线端点交汇于一点就更复杂了。每次三角化前都来个自交检测和修复对本来就不快的计算复杂度来说又是雪上加霜了。但不检测又可能出错。第三是不支持多个环如果有多个环还需要打断连接成一个环。这又是一个麻烦的算法因为还可能出现环套环各种嵌套的情况。总得来说简单的割耳法好实现但本身计算复杂度高。如果要实现一个健壮的割耳法难度也不低。另一种常用的多边形三角化算法是单调多边形法单调多边形三角化算法要比割耳法效率高O(n log n)。但我相信它是很多人的噩梦它的实现复杂度要比割耳法难许多别说实现了光看懂对一般人来说都有很大挑战。单调多边形法同样不支持自交需要提前处理自交。另外单调多边形法对一些特殊情况也需要处理才能正确执行。例如多个分裂点重合了或者内环的一个端点和外环一个端点重合了等。往往这些处理需要重新搜环不仅降低了效率对本来就高的实现复杂度也是雪上加霜了。我们的算法是基于单调多边形法来改进得到的算法计算复杂度依然为O(n log n)。但它比传统的单调多边形法更直观、更稳定支持多个环任意嵌套不用对多个顶点重合等极端情况做特殊处理能很好的处理自交还能支持孤岛检测等特殊业务。算法流程介绍本节先对算法基本流程做简要介绍后续会分小节详细讲解关键流程。输入顶点列表和边列表顶点记录前后边边记录两个端点输出三角形列表具体流程1.顶点规范化将y轴接近的顶点小于预设精度拉到同一水平线消除浮点数误差带来的影响。2.扫描线分割将顶点用y排序将边用过顶点的扫描线切开为子边两根相邻扫描线间的子边用搜索树管理来提高效率同时也能直接知道每条边的左右子边。因为顶点记录的前后边所以这步的复杂度是可以做到O(n log n)的。3.去自交只需检测两条扫描线间相邻子边的自交即可。去自交的方法是在自交点处增加一条扫描线然后重复上述过程直到无自交为止。4.舍去业务上不需要的边这步的目的是根据业务舍掉一些不需要的边例如不显示孤岛时舍去洞内的所有边。这步只需要基于扫描线间排序好的子边做舍去即可因为这些子边的内外非常明确删除前后都是按外内外内外的顺序排列只需要知道子边来自哪个环就可以处理非常复杂的业务需求。到这里是分水岭。前四步难度比较低做完前四步对分割出来的三角形面数要求不高的情况已经可以直接三角化了因为两个扫描线间的子边组成了一个个的三角形和梯形。但是肉眼可见的三角形会多许多许多。接下来的步骤会使分割的三角形数量最优但实现复杂度会大幅度提高。5.添加分割线这步是通过添加合理的分割线将任意多边形变成单调多边形。和传统的单调多边形法比这里会充分利用上面计算的内外关系使极端情况下更加稳定。这部分比较复杂后面拿出来单独讲解。6.搜单调多边形这部分不是真的做多边形搜索毕竟多边形搜索不够高效而是利用前面的子边顺序从最高最左侧的内部区域左右两边开始一直搜到底最底或左右重合与一点记录左侧和右侧两个列表即可。7.单调多边形三角化这部分是个独立的算法后续单独讲解。到这里多边形三角化整体算法流程就介绍完了后面会对一些关键点做带图例的讲解。扫描线分割这一块非常简单就是用一堆的水平线将多边形切了。如下图所示具体实现时可以按顶点排序从上往下分割。这样做的好处是每条扫描线只需要切割前一条扫描线切剩下的以及前一条扫描线穿过顶点新引入的即可。因为是水平线切割所以切割效率也是非常高的。切割完的结果子边需保存到一个有序的数据结构中按x排序这样方便快速判断内外左右边和查找。自交检测与处理基于前面的分割结果自交只需要判断相邻子边即可如下图所示子边自交自动在自交点处添加一条扫描线并切开相应边即可。对于复杂自交我们可以不断重复上述过程直到自交消失。如下图所示添加分割线来分割为单调多边形首先是哪些顶点需要添加分割线这里我们给出一个更符合拓扑的原则。如果一个顶点是向下的一条边的另一个顶点y坐标大于当前顶点另一条边的另一个顶点y坐标不小于当前顶点那么就判断该顶点是否位于其下方相邻的扫描区域内部。如果位于内部则说明该顶点需要添加分割线。如下图所示同理顶点是向上的则判断其是否位于上方相邻的扫描区域内部。接下来看如何寻找分割线的另一个顶点。以向下的顶点为例它位于它下方扫描区域内部则可以找到它左右两侧子边。沿着这两条子边不断往下找和它们连接的子边直到走到头或者有新的顶点出现在它们内部或边界上。如果找到出现在它们内部或边界上的顶点则该顶点就是要找的点否则走到头的子边端点即为要找的点。如图所示添加边并且将新边也用扫描线割成子边。重复上述过程。搜索单调多边形分割完后我们就得到了一组单调多边形下面就是将他们找出来。找的方式是从最上最左的内部区域的左右两条边开始往下找直到找到两条路径归于一点或者无法继续找为止。如下图所示找的时候要注意保证拓扑正确左侧边和左侧边连右侧边和右侧边连。注意找的结果不是一条条子边而是路过的所有原始顶点不包含边被扫描线切割产生的内部顶点。最后就是将找过的子边都删除然后重复上述过程直到所有子边都找过了。单调多边形三角化上面算法不仅找到了单调多边形还分开了左右顶点。首先基于上述结果把顶和底不闭合的添加一条边闭合一下。然后就执行经典的单调多边形三角化算法就可以了。将一个单调多边形三角化的算法非常简单资料也比较多这里就不占用篇幅了。结果展示最后看一下基于上述算法实现出来的三角化效果为了方便观察原多边形和三角化结果都放出来了如图所示。该算法相关源码已经放到了我们的专属星球中感谢大家支持。星球链接https://t.zsxq.com/bVB9h前200个加入星球的朋友还能在一款产品中使用我们的曲线求交开源库wcurvint和复杂多边形布尔运算开源库wpolybool而无需受强制开源协议限制。