08
2021
04

简单多边形凸分解

多边形

多边形(polygon)是闭合的折线。每一个点Pi叫做多边形的顶点(vertex),每一条线段叫做多边形的边。

如果不相邻的边不相交,则多边形是简单多边形

如果对于多边形内的任一两点,连接着这两点的线段也在多边形内,则多边形是凸多边形(convex)。

非凸多边形被称为凹多边形(concave)。

多边形分解

顶点的可见性

其中一个关键的概念是顶点之间的可见性。

两个顶点Vi和Vj被称为是互相可见的,如果连接它们的开放线段严格地位于多边形内。也就是说,从一个顶点到另一个顶点之间必须有一个清晰的视线,没有任何的多边形部分会遮挡视线,甚至没有一个顶点会阻挡视线。

当两个顶点是互相可见时,连接它们的线段叫做多边形的对角线(diagonal)。

如果两条共用一个顶点的边之间的夹角(从多边形内测量)小于弧度π,那么这个顶点就被称为凸顶点。这个夹角称为位于顶点上的内角。

如果共用一个顶点的两条边位于同一条直线上,这个顶点就叫做共线顶点。

如果位于一个顶点上的内角大于弧度π,那么这个顶点称为优角

顶点Vi-1和Vi+1之间的可见性

如果Vi是一个优角顶点,那么Vi-1和Vi+1一定不是互相可见的。

如果Vi是一个凸顶点,并且不存在其他的多边形顶点位于三角形(Vi-1,Vi,Vi+1)上,那么Vi-1和Vi+1就是互相可见的。算法复杂度是O(n²),n是顶点个数。

事实上,只需要检测三角形对于优角顶点的包含性就足够了。算法的事件复杂度是O(n*r),n是顶点个数,r是优角个数。

 耳,耳尖

如果(Vi-1,Vi+1)是多边形的一条对角线(注:书上写的是Vi-1,Vi+2,应该是写错了),顶点Vi-1,Vi,Vi+1就构成多边形的一个**耳**,而Vi叫做耳尖(ear tip)。

任意两个顶点之间的可见性

检测(Vi,Vj)(|i-j|≥2)是不是对角线的方法非常简单。这种方法的基本思想是,遍历多边形的所有边,并检测是否存在任何与线段(Vi,Vj)相交的边。不需要检测与指定的线段相邻的边(需要处理相邻的边与指定线段共线的情况)。

如果多边形有一条边与指定的线段相交,那么线段就不是一条对角线。

如果所有的边(与线段相邻的边除外)与线段都不想交,那么存在两种情况,一种是这条线是一条对角线,另一种是这条线位于多边形之外。只需要检测线段的一个端点(比如Vi)的局部表现就够了,只要线段包含于Vi±1-Vi的圆锥之内,这条线段就是一条对角线。

三角剖分(多边形分解为三角形)

设有一个具有顶点Vi(0≤i<n)的简单多边形。这个多边形的三角剖分(triangulation)就是对这个多边形进行三角形分解。每一个三角形的顶点都是原多边形的顶点。如果分解形成的两个三角形相交,那么它们只能相交于顶点或边,而不能相交于内点。

这种处理所形成的的三角形的边必须位于多边形之内,因此这些边必须是对角线。

根据定义,所有用于三角剖分的对角线都必须是不相交的。

多边形的任何三角剖分都必须使用n-3条对角线,并包含n-2个三角形。

通过耳裁剪来实现三角剖分

因为多边形的三角剖分与多边形的对角线相关,因此可以使用分治算法来构建三角剖分。

其思想是,找到一条对角线,沿对角线将多边形分解为两个子多边形,并对每一个子多边形进行递归处理。算法时间复杂度是O(n³)。

使用耳裁剪法,不需要搜索所有的对角线,只需要找到一个耳就够了,将对应的三角形加入列表中,从多边形中删除这个耳,并对减少的多边形进行递归处理。算法时间复杂度是O(n³)。

可以对耳裁剪法进行修改,使其成为时间复杂度为O(n²)的算法。其思想是,首先扫描一遍多边形,并跟踪记录哪些顶点是耳尖。删除一个耳,比如删除耳尖位于顶点Vi的耳,这样,顶点Vi-1和Vi+1是否是耳尖将发生改变,其它顶点是否是耳尖并不会改变(注:这里是按作者的理解写的,和书上写的不一致,中文版翻译的不好,英文原版写的是earness)。因此,每一次删除耳仅需要两次更新,以确定Vi-1和Vi+1是否是剩余的多边形的耳尖。

还有效率更高的三角剖分方法,实现起来比较复杂,这里不再深入讨论了。

效果

获得 Adobe Flash Player

凸分解(凹多边形分解为凸多边形)

多边形的三角剖分是将多边形分解为凸子多边形的特殊情况,对于顶点数为n的多边形,分解得到的子多边形数为n-2。更一般的问题是将多边形分解为凸子多边形,并且使这样的子多边形数量最少。 为了获得最小数量的子多边形,最优的凸分解可能要求制定额外的点和线段,我们提到的凸分解在构建过程中仅使用对角线。

效果

获得 Adobe Flash Player

一种次优但快速的凸分解

Hertel和Mehlhorn(1983)提出了一种快速而简单的次优凸分解算法。

给定一个与对角线相关的凸分解,一条对角线与顶点V有关,如果删除这条对角线将得到一个不凸的多边形(在V点非凸),那么这条对角线叫做这个顶点的基本对角线。否则,这条对角线叫做这个顶点的非基本对角线。显然,一条连接两个凸顶点的对角线是非基本对角线(注:书上写的是“顶点”而非“凸顶点”,翻译错误,英文原文用的是“convex vertices”)。如果一条对角线是顶点V的基本对角线,那么这个顶点V必须是优角顶点。然而,一个优角顶点可以是一条非基本对角线的一个端点。(注:“一条对角线是顶点V的基本对角线”是“这个顶点是优角的顶点”的充分不必要条件)。

这个算法很简单。首先三角剖分多边形,然后删除所有的非基本对角线,一次删除一条。算法的时间复杂度由三角剖分的时间复杂度决定。

一种优化凸分解 

 Keil和Snoeyink在1998年提出了一种优化凸分解算法。这种算法仅适用对角线,并且其渐进运行时间是O(nr²)级的,其中n是多边形的顶点数,r是多边形的优角顶点数。这种算法是基于动态规划(Bellman 1987)的。 算法比较复杂,不再深入讨论了,有兴趣可以阅读参考文献2。

 参考文献: 

 【1】 周长发. 计算机图形学几何工具算法详解. 电子工业出版社 2005.1 

 【2】 Philip J.Schneider David H.Eberly. Geometric Tools for Computer Graphics.

« 上一篇

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。