| 基于二叉树思想的任意多边形三角剖分递归算法 |
| |
| 引用本文： | 刘强,李德仁.基于二叉树思想的任意多边形三角剖分递归算法[J].武汉大学学报(信息科学版),2002,27(5):528-533. |
| |
| 作者姓名： | 刘强 李德仁 |
| |
| 作者单位： | 武汉大学测绘遥感信息工程国家重点实验室,武汉市珞喻路129号,430079 |
| |
| 基金项目： | 测绘遥感信息工程国家重点实验室开放研究基金资助项目 (0 10 3 0 2 )。 |
| |
| 摘 要： | 提出了一种基于二叉树思想的任意多边形三角剖分递归算法。该算法采用二叉树思想，确定剖分三角形的二叉树状结构，并采用递归算法实现。这算法可适用于任意形状的凹或凸多边形，也适用于包含岛屿的多边形。此外，在考虑边界点高程的基础上，可充分顾及地形特征。该算法完全适用于长距离河流流域的三维面状表达。
|
| 关 键 词： | 三角剖分 二叉树 多边形 三维GIS 递归算法 地理信息系统 |
| 文章编号： | 1000-050X(2002)05-0528-06 |
| 修稿时间： | 2002年4月20日 |
A Recursive Algorithm for Triangulation of Arbitrary Polygons Based on BSP Tree |
| |
| LIU Qiang,LI Deren.A Recursive Algorithm for Triangulation of Arbitrary Polygons Based on BSP Tree[J].Geomatics and Information Science of Wuhan University,2002,27(5):528-533. |
| |
| Authors: | LIU Qiang LI Deren |
| |
| Institution: | LIU Qiang 1 LI Deren 1 |
| |
| Abstract: | 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. |
| |
| Keywords: | triangulation BSP polygon 3D GIS recursive algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
