Region division and combination method based on depth-first traversal

Abstract

The invention discloses a region division and combination method based on depth-first traversal, which is a method for dividing a concave polygonal region into a plurality of convex polygonal sub-regions so as to reduce the transition flight distance and the turning number among the sub-regions during surveying and mapping of an unmanned aerial vehicle. The method comprises the following steps: firstly, dividing a concave polygon area into a plurality of convex polygonal sub-regions, then establishing a connected graph according to the adjacency relation of the sub-regions, then performing traversal search on the connected graph by utilizing an improved depth-first algorithm, and finding sub-regions capable of being combined so as to form a convex polygon as large as possible. Aiming at the problem of energy consumption of the unmanned aerial vehicle during surveying and mapping, the concave polygonal regions which may be met are reasonably divided and combined, so that the unmanned aerial vehicle can finish a surveying and mapping task more quickly.

Description

technical field [0001] The invention belongs to the technical field of image processing, and in particular relates to an area division method based on depth-first traversal of an adjacency graph. Background technique [0002] With the rapid development of UAV-related technologies, the use of UAVs for surveying and mapping has become an effective means. At present, for some special areas, the use of UAVs for surveying and mapping not only needs to consider terrain environmental factors, but also needs to consider UAVs. energy consumption. At the same time, with the construction of my country's smart ports, a large number of high-tech integration into the port's production management system, basic information is essential for port information management. Modern ports have a wide range and long coastlines. It is no longer appropriate to rely on traditional satellites to obtain port images. Not only because of the poor real-time performance of satellite images, but also because...

AI Technical Summary

Problems solved by technology

[0003] For relatively regular graphics areas, literature (Coombes M, Chen W H, Liu C. Boustrophedon coverage path planning for UAV aerial surveys in wind [C] / / 2017InternationalConference on Unmanned Aircraft Systems (ICUAS).IEEE,2017:1563-1571.) Considering the UAV in the case of wind, it uses the traditional ox farming method to scan a convex polygon area. At the same time, the literature (Cabreira T M, Di Franco C, Ferreira P R, et al. Energy-aware spiral coverage path planning for uav photogrammetric applications[J].IEEE Robotics and Automation Letters,2018,3(4):3662-3668.) points out that adopting inner and outer spiral walking in conventional convex polygonal areas can reduce the energy consumption of UAVs when turning , the above two cases do not consider the concave polygon area

The Chinese patent with the publication number CN 105786957B "A table sorting method based on cell adjacency and depth-first traversal" has solved the problem of table distortion caused by scanning or taking pictures, which is not conducive to cell sorting, but This method does not decompose and merge a concave polygon image

Images