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

该文提出了一种针对散乱点集的快速生成TIN的算法，该算法首先对散乱点集按扫描线方式排序，然后利用凸壳技术，以排序后的点为着眼点，通过依次扫描各点快速地将有序列集进行三角联网，最后利用拓扑结构快速地将其优化为TIN。在三角网联结过程中由于充分利用了有序点子集的凸壳特性，避免了所有的交点测试，并且加入点联结合理三角形时的判断次数与原始点集的点数无关，只与点集的平面分布结构有关，从而保证了对海量散乱点集生成TIN的效率，该文不算法进行了具体实现，并在实际项目中进行了成功的应用，证明了算法具有可操作性和较强的实用性。

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

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.