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.