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

已有的多边形三角化剖分算法,对多连通任意多边形的处理方法不一,算法大多复杂,可靠性低,而且往往只适合于特定的多边形剖分。本文结合现有的多边形三角剖分算法,提出了一个简洁高效、高可靠性的多连通任意多边形三角化剖分的找桥算法,该算法可用于各种多连通任意多边形的三角化剖分处理,并且成功运用于本单位研制开发的城市三维数码景观系统中,收到了较好的效果。

Bridge-finding Algorithm of Multiply-connected Polygons Triangulation

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.