基于BFS算法的地质剖面图封闭区域查找填充方法

摘要

本发明提供了一种基于BFS算法的地质剖面图封闭区域查找填充方法，属于地质剖面图绘制技术领域；本发明在传统BFS算法的基础上，采用多次路径搜索方法，查找根据勘察数据管理系统生成的初始地质剖面线组成的封闭区域，能够有效避免对于嵌套封闭区域的查找遗漏问题；本发明拓展了由地质剖面线组成的交点的邻接表数据结构，能够根据邻接表中记录的信息，自动查找封闭区域并填充对应纹理，对于地质剖面图的绘制更加方便、快捷、准确，能够大幅提高工程师绘制地质剖面的效率，并实现真正的基于数据的云端地质剖面图交付。

说明书

技术领域

本发明属于地质剖面图绘制技术领域，尤其涉及一种基于BFS算法的地质剖面图封闭区域查找填充方法。

背景技术

目前常用的地质剖面图绘图软件为美国Autodesk公司开发的AutoCAD软件，该软件为桌面端单机软件，可以为工程师自动查找地质剖面图中由数条多段线形成的所有封闭区域，并由工程师人为指定填充封闭区域中的地质材料花纹，最终绘制成完整的地质剖面图。

但是，随着地质行业信息化和数字化进程的推进，越来越多的工程师需要在网页端或云端由勘察数据管理系统自动生成地质剖面图，而不是采用类似AutoCAD一样的桌面端软件进行手动绘制地质剖面图，因此，亟需开发一种适用于自动绘制地质剖面图的高效封闭区域查找方法，以便勘察数据管理系统可以自动从由计算机或人为绘制的任意多条段线中识别地层位置并进行地质材料填充。

发明内容

针对现有技术中存在不足，本发明提供了一种基于BFS算法的地质剖面图封闭区域查找填充方法，在传统BFS算法的基础上，利用多次路径搜索方法来搜索封闭区域，有效避免封闭区域遗漏问题，能够根据拓展的邻接表信息自动填充纹理，对于地质剖面图的绘制更加方便、快捷、准确。

本发明是通过以下技术手段实现上述技术目的的。

一种基于BFS算法的地质剖面图封闭区域查找填充方法，包括如下步骤：

将绘制好的地质剖面线输入勘察数据管理系统，利用改进的BFS算法查找地质剖面线形成的封闭区域并记录封闭区域信息，根据记录的封闭区域信息输出封闭区域并对封闭区域填充地质材料纹理，最终由勘察数据管理系统输出地质剖面图。

进一步地，所述利用改进的BFS算法查找封闭区域的过程为：利用Bentley-Ottmann算法获取地质剖面线形成的交点，判断交点对应的地质材料属性，利用获取的所有交点构建无向图，拓展无向图所有交点的邻接表数据结构，采用多次路径搜索方法查找封闭区域并输出，同时将查找过程中的封闭区域信息记录在邻接表中。

进一步地，所述交点邻接表具有5种数据结构，分别为：GEO、COLOR、P、D、M，其中GEO表示交点的地质材料，COLOR表示交点的颜色，P表示该交点的父交点，D表示该交点到源交点的距离，M表示链表结构。

进一步地，所述多次路径搜索方法为：在无向图中选取源交点并将其着上灰色，从源交点向外第一次搜索，将第一次搜索到的所有交点全部着上灰色，分别以第一次搜索到的交点作为新的源交点向外第二次搜索，将第二次搜索到的所有交点全部着上灰色，其中，重复搜索到的交点着上黑色，未搜索到的交点为白色，循环上述过程直至所有交点都被搜索到，获取第一轮封闭区域；依次取搜索过程中所有的相遇点组成的点集中的相遇点作为新的源交点进行搜索，获取第二轮封闭区域；当第二轮封闭区域中新的相遇点和作为源交点的相遇点已经在第一轮封闭区域中同时出现过，则不输出该封闭区域，否则输出该封闭区域。

进一步地，所述封闭区域信息记录过程为：当源交点搜索到的临近交点为灰色时，在该临近交点的M数据结构中增加关于源交点的记录；同时记录该临近交点的其他4种数据结构信息，其中，GEO数据结构信息与地质材料属性保持一致。

进一步地，所述封闭区域由一组依次排序的交点集合构成，集合中的交点通过从父交点回溯路径找到源交点，形成主路径，该交点链表结构中的其他交点形成其他主路径，多条主路径有一个相同的源交点，该源交点与主路径共同构成封闭区域。

进一步地，所述封闭区域输出过程包括两种情况：封闭区域交点个数为奇数时，该封闭区域内相遇点的D数据结构信息与其链表结构中的交点的D数据结构信息相同，相遇点沿着各自的主路径同时回溯，找到相同的源交点，构建并输出封闭区域；封闭区域交点个数为偶数时，该封闭区域内相遇点的D数据结构信息值大于其链表结构中的交点的D数据结构信息值，相遇点沿主路径回溯后返回一级，再次与其链表结构中的交点同时回溯路径，找到相同的源交点，构建并输出封闭区域。

进一步地，在所述填充地质材料纹理过程中，由GEO数据结构信息不为空的交点获取每条钻孔中心线和封闭区域的交点数量；交点数量为1时，取该交点为R，再分别取钻孔中心线上上方最远一个交点为T，下方最远一个交点为B；上方没有交点则T = R，下方没有交点则B = R；T点位于封闭区域内时，取R点为地质材料标记点；B点位于封闭区域内时，则取B点为地质材料标记点；交点数量大于1时，取钻孔中心线和封闭区域最下方的交点为地质材料标记点；R、T、B均表示交点编号。

进一步地，所述地质材料标记点为G

{G

{ G

进一步地，所述钻孔界点表示钻孔中心线上的地层分界点。

本发明具有如下有益效果：

（1）本发明将BFS算法应用到了地质剖面图绘制领域，在传统BFS算法的基础上，针对地质剖面图的实际情况，即嵌套封闭区域的存在，采用多次路径搜索方法来搜索封闭区域，能够有效避免现有的一次搜索方法造成的封闭区域遗漏问题，使得查找结果更加精准。

（2）传统的BFS算法只是简单地对无向图中所有的点进行搜索，而本发明在此基础上拓展出了无向图中交点邻接表数据结构，在邻接表中加入了用于表征交点地质材料、交点颜色、父交点、交点到源交点距离的5种数据结构，在搜索封闭区域的过程中将封闭区域信息录入邻接表中，便于根据录入信息回溯路径，查找封闭区域，同时方便自动填充对应地质材料纹理。

（3）本发明基于钻孔中心线和封闭区域的交点数量获取地质材料标记点集合，综合考虑该集合以及钻孔界点的GEO属性情况来进行地质材料纹理的填充判断，能够保证填充更加精准。

（4）采用本发明所提供的方法能够大幅提高工程师绘制地质剖面的效率，并实现真正的基于数据的云端地质剖面图交付。

附图说明

图1为本发明所述无向图G = (V, E)结构示意图；

图2为本发明所述无向图的扩展邻接表结构示意图；

图3为本发明所述嵌套封闭区域示意图；

图4为本发明所述交点数为奇数的封闭区域示意图；

图5为本发明所述封闭区域Ⅴ（x, y, m）内x点和y点的邻接表示意图，其中，图5（a）为x点邻接表示意图，图5（b）为y点邻接表示意图；

图6为本发明所述交点数为偶数的封闭区域示意图；

图7为本发明所述封闭区域Ⅶ（r, u, k, t）内r点邻接表示意图；

图8为本发明所述封闭区域查找填充方法流程图。

具体实施方式

下面结合附图以及具体实施例对本发明作进一步的说明，但本发明的保护范围并不限于此。

本实施例中所提及的英文字母“a”、“b”、“c”、“d”、“e”、“f”、“g”、“h”、“i”、“x”、“y”、“n”、“s”、“j”、“k”、“t”、“u”、“v”、“p”、“r”、“R”、“T”、“B”均表示交点的编号，“Q”表示相遇点的集合，仅是为了便于描述本发明，因而不能理解为对本发明的限制；本实施例中提及的“灰色”、“黑色”仅是为了便于描述本发明，因而不能理解为对本发明的限制；对于本领域的普通技术人员而言，可以根据具体情况理解上述术语在本发明中的具体含义。

利用本发明所述的基于广度优先搜索（Breadth-First-Search，BFS）算法的地质剖面图封闭区域查找填充方法具体过程如图8所示：

步骤1：将由计算机或人为绘制的地质剖面线数据输入至勘察数据管理系统；

步骤2：利用改进的BFS算法对地质剖面线进行封闭区域查找，并输出封闭区域；

步骤2.1：利用Bentley-Ottmann算法获取步骤1中生成的地质剖面线中多条线段的交点；在获取交点的同时，判断交点对应的地质材料属性，便于后期对封闭区域地质材料的判断，具体过程为：针对钻孔中心线，取钻孔中每层层底点的地质材料属性为当前层的地质材料，取钻孔孔顶点的地质材料属性为第一层地质体的材料；所有其他线段和钻孔中心线相交得到的交点，取其竖直向下遇到的第一个钻孔中心线上的点的地质材料属性为该交点的地质材料属性；对于不是和钻孔中心线相交得到的交点，则该交点的地质材料属性为空。

步骤2.2：利用获取的所有交点构建如图1所示的无向图G = (V, E)，便于封闭区域查找，其中，V表示交点，即图1中的圆圈；E表示两个交点的连线。

步骤2.3：针对无向图中的交点，拓展邻接表数据结构；给无向图中的每个交点均拓展如图2所示的带有5种数据结构的邻接表，5种数据结构具体为：GEO、COLOR、P、D、M，其中，GEO表示交点的地质材料，与步骤2.1中的各个交点的地质材料属性一致；COLOR表示交点的颜色，用于标记搜索轨迹；P表示该交点的父交点；D表示该交点到源交点的距离；M表示链表结构，用于记录已发现的封闭区域信息。

步骤2.4：利用改进的BFS算法查找封闭区域；

以图3的无向图为例进行封闭区域的查找：将图3中所有的交点依次用a、b、c、d、e、f、g、h、i表示；确定一个源交点a，并将a点着上灰色，从该交点向外搜索，寻找从a点出发所能到达的所有交点，将第一次搜索到的交点（b、c）全部着上灰色，即b点、c点为灰色；再分别以b点、c点作为新的源交点开始第二次搜索，寻找从这些新的源交点出发所能到达的所有交点，并将第二次搜索到的交点（a、e、d）也全部着上灰色，其中，重复搜索到的交点着上黑色，即a点为黑色，e点、d点为灰色；再分别以e点、d点作为新的源交点开始第三次搜索，并将第三次搜索到的交点（c、h、f、b、g）也全部着上灰色，其中，重复搜索到的交点着上黑色，即c点、b点为黑色，h点、f点、g点为灰色。不断循环上述过程直至所有的交点都被搜索到，搜索完成后找到i点和f点两个相遇点，由这两个相遇点回溯路径，可以查找到封闭区域Ⅰ(i, h,e, c, a, b, d, g)和封闭区域Ⅱ(f, e, c, a, b, d)，但是遗漏了封闭区域Ⅲ（f, e, h,i, g, d）。

在实际应用过程中，经常会出现如图3所示的封闭区域嵌套的现象，仅仅采用上述查找方法很容易造成遗漏封闭区域的问题，因而本发明基于BFS算法，进行多次路径搜索方法来解决上述问题：

在以a点作为最初起始交点搜索完毕后，将所有相遇点组成一个点集Q，图3中的点集Q包含i点和f点，依次取点集Q中的相遇点作为新的源交点进行搜索，搜索时若发现新的相遇点和作为源交点的相遇点已经在已有封闭区域中同时出现过，则不输出此封闭区域，否则输出此封闭区域。图4中，以f点为源交点搜索时，能够获得a点和i点两个相遇点，同时获得封闭区域Ⅱ(f, e, c, a, b, d)和封闭区域Ⅲ（f, e, h, i, g, d）；而a点和f点已经在已有的封闭区域Ⅱ中同时出现过，因此不再输出封闭区域Ⅱ，而i点和f点从来没有在任何已有封闭区域中同时出现过，因此输出封闭区域Ⅲ；对于i点，也以同样的方式进行搜索；通过上述多次路径搜索方法，能够将图中的所有封闭区域都搜索出来，确保不会遗漏。

步骤2.5：将封闭区域信息记录至交点的邻接表中；

采用步骤2.4中改进的BFS算法遍历所有的交点后，需要根据遍历信息找到封闭区域所在位置并输出封闭区域，两个灰色交点相遇构成相遇点是形成封闭区域的典型特征，在搜索过程中，搜索到灰色交点时，即灰色交点相遇时，需要在该灰色交点邻接表中记录封闭区域信息；在实际搜索中，有两种灰色交点相遇的情况：第一种为封闭区域交点个数为奇数的情况；第二种为封闭区域交点个数为偶数的情况。

对于封闭区域交点个数为奇数的情况，以图4为例进行说明，将图4中的交点分别用s、m、n、x、y来表示，s点为源交点，第一次搜索找到m点，第二次搜索找到s点、n点、x点、y点；第三次搜索时，从n点出发搜索，发现临近交点x已经为灰色，则在x点的邻接表M数据结构中增加一条关于n点的记录，同时记录x点的COLOR数据结构信息、P数据结构信息、D数据结构信息，用于构建封闭区域Ⅳ（x, n, m）；接着从x点开始向外搜索，同时，对于已经变黑的n点不再探索，继续发现灰色的y点，在y点的邻接表M数据结构中增加一条关于x点的记录，同时记录y点的COLOR数据结构信息、P数据结构信息、D数据结构信息，用于构建封闭区域Ⅴ（x, y, m）。记录信息后的x点的邻接表如图5（a）所示，y点的邻接表如图5（b）所示。

对于封闭区域交点个数为偶数的情况，以图6为例进行说明，j点为源交点，第一次搜索找到k点，第二次搜索找到j点、t点、u点、v点；第三次搜索时，从t点出发开始搜索，发现白色交点r，则r点颜色变为灰色，然后分别从u点、v点出发进行搜索，搜索到已经为灰色的交点r，则在r点的邻接表M数据结构中增加两条关于u点、v点的记录，同时记录r点的COLOR数据结构信息、P数据结构信息、D数据结构信息，分别用于构建封闭区域Ⅶ（r, u, k, t）和封闭区域Ⅵ（r, v, k, t）。记录信息后的r点的邻接表如图7所示。

步骤2.6：输出封闭区域；

封闭区域由一组依次排序的交点集合构成，对于任意一交点，可以通过其父交点逐步找到源交点，从而形成一条主路径，该交点链表结构中的每个交点也同样能够构成其他的主路径，这些主路径必然会有一个相同的源交点，这个源交点与主路径共同构成封闭区域；对于封闭区域交点数量为奇数和偶数的情况，需要采用不同的封闭区域输出方法。

封闭区域交点数量为奇数时，该封闭区域内相遇点邻接表中的D数据结构信息与其M数据结构中的交点的D数据结构信息相同，以图4为例进行说明：图中，D[y] = D[x]=2，其中，D[y]表示y点到源交点的距离，D[x]表示x点到源交点的距离；y点的主路径为y→P[y]→P[P[y]]，即y→m→s，x点的主路径为x→P[x]→P[P[x]]，即x→m→s，其中，P[y]表示y点的父交点，P[x]表示x点的父交点；y点和x点同时沿主路径回溯，找到第一个相同的源交点m，能够构建并输出封闭区域Ⅴ（x, y, m）；利用上述方法可以构建并输出其他交点数量为奇数的封闭区域。

封闭区域交点数量为偶数时，该封闭区域内相遇点邻接表中的D数据结构信息值大于其M数据结构信息中的交点的D数据结构信息值，以图6为例进行说明：图中，D[r]=3，D[u]=2，D[r] > D[u]，其中，D[r]表示r点到源交点的距离，D[u]表示u点到源交点的距离；r点的主路径为，r→P[r]→P[P[r]]→P[P[P[r]]]，即r→t→k→j，u点的主路径为u→P[u]→P[P[u]]→，即u→k→j；r点先沿主路径回溯，再返回一级，沿路径t→k→j回溯，与u点的主路径同时回溯，找到相同的第一个源交点k，能够构建并输出封闭区域Ⅶ（r, u, k, t）；利用上述方法可以构建并输出其他交点数量为偶数的封闭区域。

步骤3：对查找结束后的封闭区域进行地质材料填充；

通过步骤2.5输出所有封闭区域后，需要采用相应的地质材料纹理对封闭区域进行填充，地质材料纹理的选用取决于构成封闭区域交点的地质材料（GEO）信息，地质材料（GEO）信息通过步骤2.1中的各个交点的地质材料属性获得；根据所有GEO数据结构信息不为空的交点，得到每条钻孔中心线和某一封闭区域的交点数量；

对于交点数量只有1个的情况，取该交点为R，然后分别取该钻孔中心线上上方最远一个交点为T，下方最远一个交点为B，若上方没有交点则T = R，若下方没有交点则B = R；若T点位于封闭区域内，则取R点为地质材料标记点；若B点位于封闭区域内，则取B点为地质材料标记点。对于交点数量大于1个的情况，取该钻孔中心线和封闭区域最下方的交点为地质材料标记点。地质材料标记点记为G

封闭区域内的所有地质材料标记点形成一个点集{G

（1）{G

（2）{ G

步骤4：勘察数据管理系统输出经步骤3填充地质材料纹理的地质剖面图。

所述实施例为本发明的优选的实施方式，但本发明并不限于上述实施方式，在不背离本发明的实质内容的情况下，本领域技术人员能够做出的任何显而易见的改进、替换或变型均属于本发明的保护范围。