邱亮，徐明霄.利用向量叉积计算与二叉树追踪快速搜索封闭区域[J].河南理工大学学报(自然科学版)，doi:10.16186/j.cnki.1673-9787. 2022090061.

QIU L, XU M X．Using vector cross product calculation and binary tree tracking to quickly search closed areas [J]. Journal of Henan Polytechnic University (Natural Science), doi:10.16186/j.cnki.1673-9787. 2022090061.

利用向量叉积计算与二叉树追踪快速搜索封闭区域(网络首发)

邱亮¹，徐明霄²

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

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

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

中图分类号：TP391.7

doi:10.16186/j.cnki.1673-9787. 2022090061

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

收稿日期：2023-12-22

修回日期：2024-01-20

网络首发日期：2024-06-03

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

QIU Liang, XU Mingxiao

(School of Earth Sciences and Resources , China University of Geosciences, Beijing 100083, China;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 including 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 are 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, program uses one endpoint as the root node of the binary tree, search for the next adjacent contour line endpoint along the boundary, and use the found endpoint as the left and right child nodes. 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 select the fill colors has been 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 algorithm obtains a set of points that form the boundary of a closed area in one pass through a series of contour lines. Consequently, the algorithm enables complete alignment between contour lines and contour area boundaries. When certain contour lines change, only the relevant contour areas need to be updated, thereby improving the editing efficiency of contour maps.

Key words: cross product computation; binary tree tracking closed areas; data interpretation; topology

CLC：TP391.7