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

刘强, 李德仁

刘强, 李德仁. 基于二叉树思想的任意多边形三角剖分递归算法[J]. 武汉大学学报 ( 信息科学版), 2002, 27(5): 528-533.
引用本文: 刘强, 李德仁. 基于二叉树思想的任意多边形三角剖分递归算法[J]. 武汉大学学报 ( 信息科学版), 2002, 27(5): 528-533.
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.
Citation: 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.

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

基金项目: 测绘遥感信息工程国家重点实验室开放研究基金资助项目(010302)。
详细信息
    作者简介:

    刘强,博士生。现从事三维GIS开发、应用研究。代表成果:四川省国土资源遥感信息系统;建筑物室内浏览系统。E-mail:liuqiang_em@sina.com

  • 中图分类号: TP309.12;P208

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

  • 摘要: 提出了一种基于二叉树思想的任意多边形三角剖分递归算法。该算法采用二叉树思想,确定剖分三角形的二叉树状结构,并采用递归算法实现。该算法可适用于任意形状的凹或凸多边形,也适用于包含岛屿的多边形。此外,在考虑边界点高程的基础上,可充分顾及地形特征。该算法完全适用于长距离河流流域的三维面状表达。
    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.
计量
  • 文章访问数:  909
  • HTML全文浏览量:  70
  • PDF下载量:  224
  • 被引次数: 0
出版历程
  • 收稿日期:  2002-04-19
  • 发布日期:  2002-05-04

目录

    /

    返回文章
    返回