A Path Planning Method for Multiple Target Points

Abstract

The invention relates to the fields of computer graphics and geographic information science, and specifically discloses a fast search method for a Hamiltonian path based on a TIN triangle network, comprising the following steps: S1, obtaining node sample data; S2, constructing a Thiessen polygon according to the node sample data and TIN triangle network; S3, extracting the outermost edge of the TIN triangle network as the initial boundary, searching for a triangle with a common point with the initial boundary, merging the search results to obtain a ring, and then searching for a triangle with a common point with the inner boundary of the ring, Repeat the above search process until the entire TIN triangular network is searched; S4. Determine whether the degree of all nodes is 2; S5. Merge multiple polygons into one polygon, and the merged polygon is the search result of the Hamiltonian path. A fast search method for a Hamiltonian path based on a TIN triangular network of the present invention has a simple principle, can effectively reduce processing difficulty, cost and time, and improve solution efficiency.

Description

technical field [0001] The invention relates to the fields of computer graphics and geographic information science, in particular to a multi-target path planning method. Background technique [0002] The Hamiltonian path was proposed by the astronomer William Rowan Hamilton to find a path that passes through all other cities exactly once from a given start point to a given end point in a map network with multiple cities. [0003] The traveling salesman problem, namely the TSP problem (Traveling Salesman Problem) is also translated as the traveling salesman problem and the salesman problem. It is one of the famous problems in the field of mathematics. Assuming that a traveling merchant wants to visit N cities, he must choose the path he wants to take. The limit of the path is that each city can only be visited once, and in the end he must return to the original starting city. The goal of path selection is that the required path distance is the minimum value among all paths, ...

AI Technical Summary

Problems solved by technology

[0008] Although the research on the Hamiltonian path problem has made some progress in the era of parallel computing, in view of the fact that the traditional algorithm only optimizes the combination of nodes sequentially, without in-depth consideration of the problem space relationship, so few scholars in the current research have discovered this problem Hidden space constraints are used for path search to prevent the amount of computation from spreading exponentially, so as to reduce the difficulty, cost and time of processing

Images