Delaunay三角网中点目标快速定位算法研究

为了提高内插法的构网速度及方便数字地面模型的后续应用,本文对三角形定位算法进行了研究,对基于点-线关系的方向定位算法和基于线-线关系的方向定位算法进行了改进,算法极大地减少了定位目标三角形的时间,由于定位三角形的速度是影响内插构网速度的一个关键因素,从而提高了构网速度。同时对两种算法进行了分析比较,得出最速方向定位算法更健壮,其定位路径唯一,效率更高。

Research on algorithms of point fast position in delaunay triangular net

In order to improve the speed of constructing Delaunay triangulation network for interpolation and application of DTM,this paper researches on the point position algorithm in the network and improves two algorithms.The first is based on relation of inserting point and triangles'edges and the second is based on relations of the line of in-setting point and triangle vertex and the triangle edges.The algorithms reduce the time to locate goal triangle greatly.The speed of locating the triangle which contain given point is an important factor of the efficiency of constructing the network,thus affects the speed of the network construction.This paper analyses and compares the above algorithms and concludes that fastest oriented locating algorithm is robust and efficient because its locating direction is unique.