多连通多边形三角化找桥算法的研究及实现  

Bridge-finding Algorithm of Multiply-connected Polygons Triangulation

作　　者：邓先礼[1] 胡达[1] 杜小平[1] 

机构地区：[1]中国地质大学研究生院,湖北武汉430074

出　　处：《计算机与现代化》2004年第5期4-6,共3页Computer and Modernization

摘　　要：已有的多边形三角化剖分算法,对多连通任意多边形的处理方法不一,算法大多复杂,可靠性低,而且往往只适合于特定的多边形剖分。本文结合现有的多边形三角剖分算法,提出了一个简洁高效、高可靠性的多连通任意多边形三角化剖分的找桥算法,该算法可用于各种多连通任意多边形的三角化剖分处理,并且成功运用于本单位研制开发的城市三维数码景观系统中,收到了较好的效果。The triangulation of an arbitrary polygon is one of the basic algorithms in computer graphics and has extensive applications.In some triangulation algorithms,it is very complex and not reliable to deal with multiply-connected polygons,so their scope of application is narrow.This paper presents a concise,effective and completely reliable bridge-finding algorithm of multiply-connected polygons according to some existing triangulation algorithms.This algorithm can be applied to the triangulation of an arbitrary polygon and has been successfully used in 3D digital scene system about city.

关 键 词：多连通多边形 找桥算法 三角剖分算法 桥边 效率 可靠性 复杂度 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]