基于无向图的二维地质建模设计与应用研究

摘要

To model two dimensional geology models,correctly and efficiently,they proposed the algorithm of ring pursue and the modeling flow by human-computer interaction.This method was the technology based on undirected graphs and tree’s character,and achieving process has following three steps.Firstly,they draw the outline of curves by human-computer,and intersect sides contained curves,and split these curves into sub-curves according to the intersections,and create the indexes be-tween points and sub-curves.Then,they translate undirected graphs into curve graphs,and pursue rings by using these inde-xes and the character of tree structure.Finally,they compute the area of all obj ective rings,and order rings increasingly and construct polygon area.The results show that the modeling flow designed smooth and correct,and the algorithm is smaller than traditional algorithm in the aspects of time complexity and can make up for deficiency of traditional algorithm to search the missing ring.%为了正确、高效地建立二维地质模型，提出一种基于无向图与树结构的建模流程与环搜索方法。该方法的具体实现流程主要包括三个步骤：①在二维平面人机交互式勾画出曲线，将多个曲线中的线段求交，根据交点分裂为多个子曲线，并建立无向图中点、边、点与曲线、曲线与点的映射；②将曲线构成的无向图转化为曲线图，利用曲线与点、点与曲线的索引和树结构特点搜索曲线图中的环；③计算全部目标环的面积，按面积从小到大对环进行排序，构建任意复杂多边形区域。经算法分析和实验结果表明，设计的二维地质建模流程流畅、正确，提出的曲线树搜索环算法比传统算法时间复杂度小，且能弥补传统算法遗漏环搜索的不足。