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.

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

Received：2023-12-22

Revised：2024-01-20

Online：2024-06-03

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

QIU Liang¹, XU Mingxiao²

(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 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