基于八叉树的三维地质剖面生成算法

• 作者: 代强玲 赵龙 闵世平
• 来源期刊: 计算机工程
• 学科: 工学
• 关键词: 八叉树 三维地质剖面 三维地质体网格模型 空间索引 画廊看守算法 时间复杂度
• 年，卷（期）: 2014,（2）
• 所属期刊栏目: 图形图像处理
• 页码范围: 250-256
• 页数: 7页
• 分类号: TP911.73
• 字数: 5213字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-3428.2014.02.054

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	赵龙		3	16	2.0	3.0
2	闵世平		4	34	3.0	4.0
3	代强玲		1	11	1.0	1.0