快速多边形区域三角化算法与实现.PDF

第 25 卷第 10 期 计 算 机 应 用 研 究 Vol. 25 No. 10 2008 年 10 月 Application Research of Computers Oct. 2008 快速多边形区域三角化算法与实现 * 1, 2 1, 2 1 1 毕 林 , 王李管 , 陈建宏 , 冯兴隆 ( 1. 中南大学 资源与安全工程学院, 长沙 410083; 2. 长沙迪迈信息科技有限公司, 长沙 410083) 摘 要: 多边形区域三角化的基本思想是: 首先将简单多边形分解为多个单调多边形, 然后对每个单调多边形 进行三角化。快速多边形区域三角化算法先由多边形顶点的位置特征分为不同的类型, 并沿指定方向对顶点进 行排序, 然后顺序取出各顶点, 根据顶点类型, 确定准单调多边形的产生、增长或结束, 最后对所产生的多个单调 多边形进行三角化。该算法充分利用多边形的顶点、边的拓扑关系, 计算量少、实现简单 , 适用于带有洞、岛的任 意简单多边形, 速度较快。 关键词: 多边形; 单调多边形; 拓扑关系; 线性时间复杂度; 三角化 中图分类号: TP391. 72 文献标志码 : A 文章编号: 1001- 3695( 2008) 10- 3030- 04 Fast triangulation algorithm for polygon regions and implementation 1, 2 1, 2 1 1 BI Lin , WANG Li-guan , CHEN Jian-hong , FENG Xing-long ( 1. School of Resources Safety Engineering, Central South University, Changsha 410083, China; 2. Digital Mine Co. Ltd, Changsha 410083 , China) Abstract: The basic idea of triangulation for simple triangle was described as follows: the polygon was subdivided into mono- tonous polygons and then triangulated. The algorithm classified all the vertexes by its location characteristics, and sorted them along the appointed axis, and then selected the vertexes orderly to decide the creation, expansion or formation of a monotonous polygon by its type, at last triangulated the formative monotonous polygon. In the algorithm, the topology of the vertexes and edges made full use of so as t