GIS中基于拓扑结构和凸壳技术的快速TIN生成算法  

An Algorithm of Speedily Building TIN Based on Topological Structure and Convex Shell in GIS

作　　者：章孝灿[1,2] 黄智才[1] 章孝灿[1,2] 潘云鹤[2] 戴企成 

机构地区：[1]浙江大学空间信息技术研究所,杭州310027 [2]浙江大学人工智能研究所,杭州310027 [3]浙江大学城市规划系,杭州310027

出　　处：《计算机学报》2002年第11期1212-1218,共7页Chinese Journal of Computers

基　　金：本课题得到渐江省重点基金(981103124)资助

摘　　要：该文提出了一种针对散乱点集的快速生成TIN的算法.该算法首先对散乱点集按扫描线方式排序,然后利用凸壳技术,以排序后的点为着眼点,通过依次扫描各点快速地将有序点集进行三角联网,最后利用拓扑结构快速地将其优化为TIN.在三角网联结过程中由于充分利用了有序点子集的凸壳特性,避免了所有的交点测试,并且加入点联结合理三角形时的判断次数与原始点集的点数无关,只与点集的平面分布结构有关,从而保证了对海量散乱点集生成TIN的效率.该文还对算法进行了具体实现,并在实际项目中进行了成功的应用,证明了算法具有可操作性和较强的实用性.An algorithm speedily building TIN of scattered point set is presented. When it acts firstly all the scattered points are sorted in scan manner. Secondly the sorted points are scanned in turn and are triangulated rapidly using convex shell technology. Finally triangles are optimized into TIN by topological structures fleetly. For the fully utilizing the characters of convex shell only part of the vertices should be tested. Because the testing times of a newly added point is decided by the plane structure of the point set, and is nothing to do with the number of points in o-riginal point set, high efficiency of building TIN from mass scattered point set can be sure. The algorithm has been taken into practice successfully.

关 键 词：GIS 拓扑结构 凸壳 快速TIN生成算法 地理信息系统 不规则三角网 散乱点集 地形信息 地图生成 计算机 

分 类 号：P208[天文地球—地图制图学与地理信息工程]