欢迎访问《图学学报》 分享到:

图学学报

• 图形学与可视化 • 上一篇    下一篇

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

  

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

An Algorithm of Triangulation Based on Monotone Polygon

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

摘要: 提出了一种基于单调多边形三角化算法,被三角化的多边形可以含有任意
个内孔。先根据边界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