基于无向图的二维地质建模设计与应用研究-论文.pdf

《基于无向图的二维地质建模设计与应用研究-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第37卷第1期物探化探计算技术v。1．37N。．12015年1月COMPUTINGTECHNIQUESFORGEOPHYSICALANDGEOCHEMICALEXPLORATIONJan．2015文章编号：lO01—1749(2015)01—0123—07基于无向图的二维地质建模设计与应用研究何畏，吴文鹂，陈实，冯斌(中国地质科学院地球物理地球化学勘查研究所，廊坊065000)摘要：为了正确、高效地建立二维地质模型，提出一种基于无向图与树结构的建模流程与环搜索方法。该方法的具体实现流程主要包括三个步骤：①在二维平面人机交

2、互式勾画出曲线，将多个曲线中的线段求交，根据交点分裂为多个子曲线，并建立无向图中点、边、点与曲线、曲线与点的映射；②将曲线构成的无向图转化为曲线图，利用曲线与点、点与曲线的索引和树结构特点搜索曲线图中的环；③计算全部目标环的面积，按面积从小到大对环进行排序，构建任意复杂多边形区域。经算法分析和实验结果表明，设计的二维地质建模流程流畅、正确，提出的曲线树搜索环算法比传统算法时间复杂度小，且能弥补传统算法遗漏环搜索的不足。关键词：环搜索；建模流程；曲线树；无向图；最小面积中图分类号：TP317．4文献标志码：ADOI：lO．

3、3969／j．issn．1001—1749．2015．01．2O提，便捷、流畅的建模流程不仅可以取得事半功倍的0引言效果，并可以供他人借鉴；数据结构体定义是建模的基础[引，合理、正确的数据结构体对建模效率和建模技术是二十世纪末期随着计算机图形学、质量具有重要意义；多边形的获取是在所有环搜索人机交互、视觉设计等领域发展而逐渐兴起的一门完成后，对不同环之间是否存在关联性进行正确管交叉学科，是研究离散数据视觉呈现的方法口]。建理与识别；环的搜索算法是建模的核心，在环搜索过模也是获取图相关信息的过程，虽然图是一种比线程中，根据后

4、续边的确定方法不同，目前国内、外研性表和树更为复杂的数据结构_2]，但是建模可对究人员提出的搜索方法有以下几种l1¨]：研究范围内各种模型的几何、拓扑和属性等信息进1)转角判别法(AlgorithmforRingPursuein行合理表达[5]，并对后续数据处理解释、分析以及工theAngle—Identifiction，ARPAI)。根据和当前边作决策提供可靠的依据，因此建模技术一直是许多相交于同一点的所有边与当前边所成的夹角情况来领域研究的热点也是难点。在二、三维建模中，由于确定后续边。该类判别法原理较简单，但当出现

5、多三维模型体之间具有空间拓扑关系复杂、交互难控个多边形同时包含于同一多边形且公用边界时，容制等特点，基于二维剖面构建三维模型的方法是目易出现环搜索遗漏的情形。前三维建模采用的主要技术_6。2)交点判别法(AlgorithmforRingPursuein二维模型的构建主要包括：建模流程的设计、数theCrossingPoint—Identifiction，ARPCPI)。根据据结构体定义、环搜索算法设计以及复杂多边形获平行于当前边的参考线和所有与当前边相交的线段取等主要技术。建模流程的设计是实现建模的前的交点情况来选定后续

6、边。此类判别法需要做平面收稿日期：2014-03—27改回日期：2O14—1O一17基金项目：国家重大科学仪器设备开发专项(2011YQ050060)；国家“863”高科技研究发展计划重点课题(SS2014AA063110)；中国地质大调查项目(12120113100600)作者简介：何畏(1981一)，男，硕士，工程师，主要研究方向为计算机建模在地学中的应用与物探方法技术研究，E—mail：hewei@igge．cn。124物探化探计算技术37卷内多条线段平行和相交处理，当线段较多时，计算量intlvtl-2-]；／／

7、逻辑坐标较大且搜索正确环的准确率难以保证。}；3)滚圆判别法(AlgorithmforRingPursueinstructRing2D／／-维环结构体theRollingCircle—Identifiction，ARPRCI)。首先{虚拟一个直径足够小，同时与当前边和可选后续边vectorrelrtopt；／／环到点索引，相切的圆，若其与分叉点上的其他分支线段不想交，动态存储每个环中的节点号则该可选边可作为环搜索的后续边。此类判别法和doublerarea；／／环围成平面区交点判别法相似，即当平面范围内线段较多

8、时，线段域的面积间相交计算量大，难以保证搜索出全部正确的环。)；针对上述环搜索过程中存在的不足，本研究从structPolygon2D／／2维多边形结无向图生成树以及目标环的特点人手，研究并设计构体了二维模型构建流程、将无向图转化为曲线树[1{的环搜索算法(AlgorithmforRingPursueintheflo