岛屿群约束数据域三角网剖分

Delaunay Triangulation Based on Nesting Islands Constrained Data

岛屿就是由一条或多条首尾闭合有向的弧段组成的区域,弧段与弧段之间彼此不相交,岛屿间彼此可以多层嵌套也可以相互独立。经过对岛屿间的关系进行分析后,将组成岛屿的弧段分为4种基本类型,并给出分类算法,根据弧段的类型自动识别岛屿的"内部"和"外部",凡是"外部"就约定为岛屿的"空洞"。围成岛屿的弧段就构成了岛屿的约束条件,在岛屿内部先进行弧段上CDT的构造,然后在CDT的基础上构造DT,以实现在岛屿"内部"带有约束条件的三角网剖分,从而可以构造出任意复杂的带岛屿群的三角网,经过编制相关程序验证该算法的效率主要取决于构造DT的效率。

An island is composed of one or more end to end closed arcs without intersection with each other,the relationship between islands could be nested or mutually independent. After the analysis on relationship between islands, we divided the arcs composing an island into four basic types and gave a classification algorithm. The＂ interior＂, ＂exterior＂ and＂ hole＂ of an island could be automatically identified according to the types of arc segments. The arcs composing an island become the island constraints, according to previous method, any complex triangulations are structured. The efficiency of algorithm which was verified by related programs is mainly determined by the efficiency of DT construction.