一种基于单调多边形的三角剖分算法

图学学报

一种基于单调多边形的三角剖分算法

出版日期:2013-12-31 发布日期:2015-06-19

An Algorithm of Triangulation Based on Monotone Polygon

Online:2013-12-31 Published:2015-06-19

摘要/Abstract

摘要： 提出了一种基于单调多边形三角化算法，被三角化的多边形可以含有任意
个内孔。先根据边界y(x)方向的局部极值顶点作水平（垂直）分割线，将多边形划分成单连
通y(x)单调多边形，然后再将各单调多边形三角化。算法考虑了各种几何奇异情况，因此比
较稳定。

关键词: 分割线, 单调多边形, 三角剖分, 奇异情况

Abstract: An algorithm of triangulation is proposed based on monotone polygon , which
can contain more inner holes. The horizontal(vertical) sectioning lines on the local extreme
vertices of boundary in direction of y(x) are made, which can divide the polygon into single
connected y(x)-monotone polygons, and then triangulate the monotone polygons. The algorithm
considers various singular geometric conditions, therefore is a stable one.

Key words: sectioning line, monotone polygon, triangulation, singular condition

徐敏，朱二喜，何援军. 一种基于单调多边形的三角剖分算法[J]. 图学学报.

Xu Min, Zhu Erxi, He Yuanjun. An Algorithm of Triangulation Based on Monotone Polygon[J]. Journal of Graphics.

[1]	史永丰，张育浩，程婷，徐保文，林岗山 . 基于空间多边形三角剖分的曲面分割求交算法[J]. 图学学报, 2019, 40(3): 447-451.
[2]	沙春发，卢章平，杨华春，郭健宏. 一种基于三角剖分的产品造型混合方法[J]. 图学学报, 2015, 36(5): 734-739.
[3]	朱二喜，徐敏，何援军. 一种利用Delaunay 三角剖分的碰撞检测算法[J]. 图学学报, 2015, 36(4): 516-520.
[4]	朱二喜，何援军. 一种利用图形内角的多边形布尔运算新算法[J]. 图学学报, 2011, 32(2): 10-19.