邱亮, 徐明霄,等.利用向量叉积计算与二叉树追踪快速搜索封闭区域[J].河南理工大学学报（自然科学版）,2024,43(6):139-145.

QIU L, XU M X,et al.Using vector cross product calculation and binary tree tracking to quickly search closed areas[J].Journal of Henan Polytechnic University(Natural Science) ,2024,43(6):139-145.

利用向量叉积计算与二叉树追踪快速搜索封闭区域

邱亮1, 徐明霄2

1.中国地质大学（北京） 地球科学与资源学院，北京  100083；2.中国地质大学（北京） 信息工程学院，北京  100083

摘要: 目的 自动填充等值线图的难点是自动搜索出值域相同的各个封闭区域，常用的扫描线填充和区域填充方式存在计算量大、效率不高等问题。  方法 针对此问题，提出利用多边形特征点的向量叉积计算结果与多边形的绘制顺逆方向之间的相关性，判定等值图中断层多边形的走向，基于构成封闭等值区域的等值线及其属性值具有的规律性性质，即等值线属性值是等值或等间距，追踪区域时利用填充边界或断层上的等值线端点创建追踪二叉树。追踪相邻的两个等值线端点所在的封闭区域时，将其中一个端点作为二叉树的根节点，沿边界查找左右相邻的下一条等值线端点，并将找到的端点作为左右子节点，从而实现封闭区域的快速追踪；通过封闭区域面积排序确定不同区域之间相互包含关系，据此构建拓扑相邻关系树，实现封闭区域的顺序覆盖填充，设计出更加简单、快速区分不同封闭区域的区域填充颜色选取方法。  结果 该方法简化了复杂的等值连通区域搜索算法，等值图的颜色变化趋势能保持一致，数据测试对比证明了所提算法的正确性。  结论 该算法通过一系列等值线能一次性得到组成封闭区域边界的点集合，因此，可以实现等值线和等值区域边界的完全吻合，当某些等值线发生变化时，只需更新相关的等值区域即可，提高了等值图件的编辑效率。

关键词:向量叉积计算;封闭区域二叉树追踪;数据解析;拓扑关系

doi:10.16186/j.cnki.1673-9787.2022090061

基金项目:国家自然科学基金资助项目（41702207）；中国地质大学（北京）本科教学质量提升计划建设项目（JGYB202003）

收稿日期:2022/09/24

修回日期:2023/07/07

出版日期:2024-09-24

Using vector cross product calculation and binary tree tracking to quickly search closed areas

QIU Liang1, XU Mingxiao2

1.School of Earth Sciences and Resources，China University of Geosciences，Beijing  100083，China；2.School of Information Engineering，China University of Geosciences，Beijing  100083，China

Abstract:  Objectives The difficulty in automatically filling contour maps lies in automatically identifying each closed area with the same range value.Commonly used methods like scanning line filling and area filling suffer from issues，such as high computational overhead and low efficiency.  Methods To determine the trend of fault polygon in equivalent diagram，a method based on the correlation between the calculation result of vector cross product of polygon feature points and the direction of polygon drawing was presented.Based on regularity characteristics of contour attribute values of constituting closed equivalent areas（namely，the attribute values of contour lines were equal or equidistant），tracking binary trees were created with contour endpoints on filled boundaries or faults when tracking areas.When tracking the closed area where endpoints of two adjacent contour line were located，using one endpoint as the root node of the binary tree，the next adjacent contour line endpoint along the boundary was searched for，the found endpoint was used as the left and right child nodes，and so the method achieved the fast tracking for closed domains.The inclusion relationship between different areas was determined through the area ordering of closed domains.Topological adjacent relation tree was constructed to implement sequential coverage filling of enclosed areas.A more simply and efficiently method to distinguish different enclosed areas and to select the filled colors was proposed.  Results The new method simplified the complex search algorithm for equivalently connected regions.The color change trend of the contour map could remain consistent.The test showed that the proposed algorithms were correct.  Conclusions  The proposed algorithm obtained a set of points that formed the boundary of a closed area in one pass through a series of contour lines.Consequently，the algorithm enabled complete alignment between contour lines and contour area boundaries.When certain contour lines changed，only the relevant contour areas needed to be updated，thereby the editing efficiency of contour maps was improved.

Key words:cross product calculation;binary tree tracking of closed area;data interpretation;topology