一种非凸包边界约束不规则三角网生成算法

An algorithm for irregular triangulated networks restricted by non-convex border

数字高程模型(DEM)模拟的大多数地形区域是多种类型区域镶嵌而成的复合体,且子区域的边界一般为非凸多边形,即三角网受到边界的约束。而目前已有的各种Delaunay三角网构网算法生成的不规则三角网的边界都是区域内采样点集的凸包,不能表达复合区域和边界为非凸多边形的区域。本文作者对三角网扩张法作了扩展,使之能够在任意多边形所包围的区域内生成不规则三角网。扩展后的算法具有步骤简单、适合任意多边形边界内生成不规则三角网的优点,而且该算法可用于"分块"式生成数据量较大的三角网,同时保证各"分块"之间完整的邻接关系。

Most of the terrain regions modeled by digital elevation model （DEM） is compounded ones that include multiple categories of surface features, and not all of the borders of these regions are convex, so regions always restricted by their non-convex borders. Now, most extent algorithms for generating Delaunay triangulated networks can only generate borders that are convex hull of sampied points, but can not create borders of compound regions and the region whose border is not convex. The author modifies the triangle-expanding method and makes it be able to generate irregular triangulated networks from discrete sampled points that are restricted by their border of arbitrary polygon. This new method has the advantage of simple steps, arbitrary border polygon, generating by split and correct adjacent relations.