一种改进的启发式球面点定位算法

将仅适用于平面网格的基于质心坐标的搜索策略进行推广和拓展,提出一种适用于球面网格的改进启发式算法,并详细讨论了不同质心坐标值情况下的下一搜索三角形的选择方法.为进一步提高算法效率,在进行启发式搜索之前通过执行若干顶点比较操作来选择一个较优的初始搜索三角形,同时引进一个近似度阈值来调整初始三角形确定时间与后续目标三角形搜索时间之间的平衡关系.分析表明,改进启发式算法的时间复杂度仅为O(n1/2f)(nf为网格包含的三角形数目).

An Improved Heuristic Algorithm for Locating a Point in Spherical Meshes

A searching strategy based on barycentric coordinates was generated from the planar domain to the spherical one. In order to improve the algorithm performance, a special operation was used to select an appropriate initialization triangle for the searching. The concept of approximation degree threshold was also introduced to balance the time wasted on deciding the initialization triangle to visit and searching the target triangle containing the given point. The analysis shows that the new algorithm can find the target triangle in O(n 1/2 __ f ) time.