摘要： 针对目前构建三维地质剖面算法复杂度高、效率低的问题，提出一种基于八叉树的三维地质剖面生成算法。利用八叉树算法对传统的地质剖面生成算法进行改进，使算法在搜索过程中的时间复杂度降低至O(log8(n/M))，在算法中加入轮廓边约束，对搜索到的边进行预处理，以保证边的正确性和有序性。采用八叉树为复杂三维地质体网格模型内的三角形创建空间索引，通过八叉树快速查找出经过剖面的三角形，计算交点并追踪出轮廓边界，通过画廊看守算法对追踪出的边界三角化并构建三维剖面。实验结果表明，该算法具有复杂度低、鲁棒性强的特点，与传统的地质剖面生成算法相比，时间复杂度由O(n2)降低到O(nlbn)。

关键词: 八叉树, 三维地质剖面, 三维地质体网格模型, 空间索引, 画廊看守算法, 时间复杂度

Abstract: Aiming at the high-complexity and low-efficiency of constructing 3D geologic sections, an 3D geological section generating algorithm based on octree is proposed. It is an improvement of the traditional geologic sections generating method, which reduces the time complexity to O(log8(n/M)) in the search process. Besides, it adds boundary constraints for preprocessing, guarantees the correctness and the order of the boundaries, and becomes more robust. The algorithm creates spatial index for triangles on complex 3D geologic body mesh models and searches triangles on geologic sections plane based on octree, then computes the intersection points and traces boundaries of geologic sections. The algorithm constructs 3D geologic sections, and uses gallery guard algorithm to triangulate the traced boundaries. Experimental results prove that this method not only has advantages of high-efficiency and robustness, but also reduces the time complexity from O(n2) to O(nlbn) compared with traditional algorithm.

Key words: octree, 3D geological section, 3D geologic body mesh model, spatial index, gallery guard algorithm, time complexity

中图分类号: 

• TP911.73