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.

doi:10.16186/j.cnki.1673-9787.2022090061

Received:2022/09/24

Revised:2023/07/07

Published: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