基于二叉树思想的任意多边形三角剖分递归算法

提出了一种基于二叉树思想的任意多边形三角剖分递归算法。该算法采用二叉树思想,确定剖分三角形的二叉树状结构,并采用递归算法实现。该算法可适用于任意形状的凹或凸多边形,也适用于包含岛屿的多边形。此外,在考虑边界点高程的基础上,可充分顾及地形特征。该算法完全适用于长距离河流流域的三维面状表达。

A Recursive Algorithm for Triangulation of Arbitrary Polygons Based on BSP Tree

Some triangulation algorithms for simple polygons have been put forward.Nevertheless,they could not be applied perfectly to polygons of buildings,roads and rivers,and so on,in 3D GIS on account of polygonal terrain feature and complexity. A recursive algorithm for triangulation of arbitrary polygons based on binary space partitioning (BSP) tree is proposed in this paper.This algorithm is implemented with the determination of triangle mesh according to BSP structure.Not only various simple convex or concave polygons but also complex polygons with islands may be triangulated with this algorithm.Moreover,terrain feature may be considered based on elevation values of polygonal boundary vertices in the triangulation of long_distance streams. In this algorithm process,firstly,a triangle,which partitions this polygon into two son polygons,is established with two adjacent vertices and another vertex.This triangle is the root node of relevant BSP tree.The two son polygons are at left and right sides of the root triangle respectively.Secondly,when each son polygon is partitioned into two grandson polygons,the left and right son triangles of the root triangle will be established.Then,the son triangle is regarded as a parent triangle.All son and grandson triangles may be established recursively.If a triangle has no son triangle,it is a leaf node.If a leaf triangle is a left son of its parent triangle,right sub_tree will be established recursively.Lastly,after each sub_polygon is completely triangulated,triangulation for this polygon is accomplished,and all triangles compose a BSP tree. As this algorithm is not correlative with the complexity of a polygon,it may be applied to arbitrary planar polygons.Moreover,as the issues of polygons with islands and terrain feature are resolved in this algorithm,triangulation for un_planar polygons,such as roads,rivers,reservoirs,and planned land_use regions may be realized perfectly.