CN105138859B - Three-dimensional panorama roams method for searching and system - Google Patents

Abstract

The invention discloses a three-dimensional panoramic roaming pathfinding method and system, which belong to the technical field of path planning. The method includes: obtaining a three-dimensional panoramic image and information related to nodes in the three-dimensional panoramic image; using JSON (JavaScript Object Notation) The data exchange format describes the data structure of the information related to the node and obtains an undirected graph; according to the data structure and the undirected graph, an obstacle list and a key node list are established; nodes in the three-dimensional panorama Set a start node and a target node in ; use the A* algorithm combined with the obstacle list and the key node list to calculate the path between the start node and the target node. With this pathfinding method, when there is an obstacle between the starting node and the target node, the path can be cut into two or more sections for pathfinding, and the number of traversed nodes can be significantly reduced, thereby improving the path search efficiency.

Description

Three-dimensional panoramic roaming pathfinding method and system

technical field

The present invention relates to the technical field of path planning, in particular to a three-dimensional panoramic roaming pathfinding method and system.

Background technique

At present, the three-dimensional panorama roaming (Panorama) technology, which is an important part of virtual reality (Virtual Reality), has broad market application prospects, and has great influence on the construction and development of smart cities, smart campuses, exhibitions, tourism, real estate, urban planning and other fields. Significance. When using the existing A* (A-star) algorithm as a shortest path algorithm for path navigation and path planning in the three-dimensional panoramic roaming, since the A* algorithm depends on the heuristic function, if the starting node and the target node If there are obstacles between them, the A* algorithm needs to traverse more nodes, resulting in low path search efficiency and resource consumption. It can be seen that, in the 3D panoramic roaming, there is a need for a 3D panoramic roaming pathfinding method that can improve the path search efficiency in the case of obstacles between the starting node and the target node by improving the A* algorithm.

Contents of the invention

In view of this, the object of the present invention is to provide a three-dimensional panoramic roaming pathfinding method and system, to improve the path search efficiency in the case of obstacles between the starting node and the target node in the three-dimensional panoramic roaming using the existing A* algorithm lower question.

The first embodiment of the present invention provides a method for 3D panoramic roaming pathfinding, including: acquiring a 3D panorama and information related to nodes in the 3D panorama; The data structure of node-related information and obtain an undirected graph; according to the data structure and the undirected graph, establish an obstacle list and a key node list; set the starting node and the node in the three-dimensional panorama A target node: using the A* algorithm combined with the obstacle list and the key node list to calculate a path between the starting node and the target node.

The second embodiment of the present invention provides a three-dimensional panorama roaming pathfinding system, including: an acquisition module, used to acquire a three-dimensional panorama and information related to nodes in the three-dimensional panorama; a description module, used to exchange JSON data The format describes the data structure of the information related to the nodes and obtains an undirected graph; a building module is used to create a list of obstacles and a list of key nodes according to the data structure and the undirected graph; a setting module is used to Set a starting node and a target node in the nodes in the three-dimensional panorama; a calculation module is used to calculate the starting node and the target node using the A* algorithm combined with the obstacle list and the key node list The path between the target nodes.

In the 3D panorama roaming pathfinding method and system provided by each embodiment of the present invention, the undirected graph is obtained by describing the data structure of the information related to the nodes in the acquired 3D panorama in the JSON data exchange format, and thus establishing obstacles list and key node list, then use the A* algorithm combined with the established obstacle list and key node list to calculate the set The path between the start node and the destination node. Compared with using the existing A* algorithm for path navigation and path planning in the three-dimensional panoramic roaming, since the obstacle list and the key node list are pre-established in the invention, and the A* algorithm is combined on this basis, it can be used at the beginning When there is an obstacle between the node and the target node, the path is cut into two or more sections for pathfinding, which significantly reduces the number of traversed nodes, thereby improving the efficiency of path search.

In order to make the above and other objects, features and advantages of the present invention more comprehensible, preferred embodiments will be described in detail below together with the accompanying drawings.

Description of drawings

In order to more clearly illustrate the technical solutions in the embodiments of the present invention or the prior art, the following will briefly introduce the accompanying drawings required in the embodiments. Obviously, the accompanying drawings in the following description are only some of the present invention. Embodiments, for those of ordinary skill in the art, other drawings can also be obtained based on these drawings without any creative effort. The above and other objects, features and advantages of the present invention will be more clearly illustrated by the accompanying drawings. Like reference numerals designate like parts throughout the drawings. The drawings are not intentionally scaled according to the actual size, and the emphasis is on illustrating the gist of the present invention.

FIG. 1 is a flowchart of a three-dimensional panoramic roaming pathfinding method provided by the first embodiment of the present invention;

2 is a flowchart of a specific pathfinding algorithm in the three-dimensional panoramic roaming pathfinding method provided by the first embodiment of the present invention;

FIG. 3 is a schematic structural diagram of a three-dimensional panoramic roaming pathfinding system provided by a second embodiment of the present invention.

detailed description

The technical solutions in the embodiments of the present invention will be clearly and completely described below in conjunction with the accompanying drawings in the embodiments of the present invention. Obviously, the described embodiments are only some, not all, embodiments of the present invention. Based on the embodiments of the present invention, all other embodiments obtained by persons of ordinary skill in the art without making creative efforts belong to the protection scope of the present invention.

Before describing specific embodiments, some functions that need to be used in 3D panoramic roaming pathfinding are briefly described. When performing path search, an evaluation function represented by the following formula (1) needs to be used:

f(m)=g(m)+h(m) (1)

Among them, m represents the current node, g(m) represents the actual distance between the starting node and the current node, h(m) represents the shortest path between the current node m and the target node (ignoring obstacles), f(m) represents the current node m evaluation function.

Usually, the Manhattan distance can be used to calculate the actual distance between the current node m and the target node end. The Manhattan distance calculation is expressed by the following formula (2):

h(m)＝l×(|mx-endx|+|my-endy|) (2)

Among them, l represents the moving weight, mx, my, endx, endy respectively represent the plane abscissa and ordinate of the current node m and the target node end.

The actual distance between the current node m and the target node end can also be calculated by using the distance formula between two points. In the case of plane coordinates, a distance length formula represented by the following formula (3) can be employed:

Among them, mx, my, endx, and endy represent the abscissa and ordinate of the current node m and the target node end respectively.

In the case of spatial coordinates, a distance length formula represented by the following formula (4) may be employed:

Among them, mx, my, mz, endx, endy, and endz represent the three-dimensional coordinates of the current node m and the target node end respectively.

In addition, if the map is large, you can also choose to use the distance formula between two points on the earth, which includes the Great-circle distance formula represented by the following formula (5) and the Haversine formula represented by the following formula (6):

Among them, R is the radius of the earth, θ _m and θ _end represent the latitudes of the current node m and the target node end respectively, with Respectively represent the longitude of the current node m and the target node end.

In the 3D panorama roaming pathfinding method and system provided by each embodiment of the present invention, the undirected graph is obtained by describing the data structure of the information related to the nodes in the acquired 3D panorama in the JSON data exchange format, and thus establishing obstacles list and key node list, then use the A* algorithm combined with the established obstacle list and key node list to calculate the set The path between the start node and the destination node. Compared with using the existing A* algorithm for path navigation and path planning in the three-dimensional panoramic roaming, since the obstacle list and the key node list are pre-established in the invention, and the A* algorithm is combined on this basis, it can be used at the beginning When there is an obstacle between the node and the target node, the path is cut into two or more sections for pathfinding, which significantly reduces the number of traversed nodes, thereby improving the efficiency of path search.

first embodiment

FIG. 1 is a flow chart of a method for finding a path for a three-dimensional panoramic roaming provided by the first embodiment of the present invention. Please refer to FIG. 1 , the 3D panoramic roaming pathfinding method provided by the first embodiment of the present invention may include the following steps S11 to S15.

In step S11, a 3D panorama and information related to nodes in the 3D panorama are acquired.

Specifically, a camera can be used to take a 360° look-around shot of each node of a scene to obtain the image material of each node, and then generate a panoramic texture by filtering, matching, splicing, fusion and rendering, etc., and based on the generated panoramic texture to generate 3D panoramas. In addition, information related to the nodes in the 3D panorama should also be recorded, where the information related to the nodes may include the longitude and latitude coordinates of the nodes, location names, and associations with other nodes.

In step S12, the data structure of the information related to the nodes is described in JSON data exchange format and an undirected graph is obtained.

The JSON data exchange format is composed of a key-value pair (key-value) and an array, and adopting the JSON data exchange format can improve readability of information related to the nodes and can reduce complexity. An undirected graph can represent nodes and edges for each object. The data structure may include the node's unique identifier, title, panorama texture path, whether it can rotate freely, free rotation speed, information prompt box, latitude, longitude, whether it is an obstacle node, whether it is a key node, and whether it can jump to other nodes etc. For example, an exemplary data structure of information related to the nodes described in the JSON data exchange format is shown below.

It should be noted that, in the above exemplary data structure provided, the value of each node is not given, but only the key of each node is shown.

In step S13, an obstacle list and a key node list are established according to the data structure and the undirected graph.

Obstacles in the established obstacle list are formed by adjacent obstacle nodes, and key nodes in the established key node list are associated with end obstacle nodes forming the obstacle.

In step S14, a start node start and a target node end are set among the nodes in the three-dimensional panorama.

When the user desires to roam in the presented 3D panorama, two nodes among the nodes in the 3D panorama can be set as the start node and the target node respectively according to his preference.

In step S15, the path between the starting node start and the target node end is calculated by using the A* algorithm combined with the obstacle list and the key node list.

Specifically, FIG. 2 shows a specific flowchart for calculating a path between the starting node and the target node by using the A* algorithm combined with the obstacle list and the key node list. Hereinafter, the A* star algorithm combined with the obstacle list and the key node list is called HRPA* algorithm (HRPA*, High-efficiency Route Planning A* algorithm). Referring to FIG. 2 , calculating the path between the starting node and the target node using the HRPA* algorithm may include the following steps S21 to S34.

In step S21, an open (OPEN) list and a closed (CLOSED) list are initialized. The OPEN list is used to save all the nodes that have been generated but not yet evaluated, and the CLOSED list is used to save all the nodes that have been evaluated and have the shortest path length from the target node to the current node to be evaluated. The OPEN list and CLOSED list are constantly changing until the end of the algorithm. The initial list length of both the OPEN list and the CLOSED list is 0.

In step S22, the start node start is added to the OPEN list, and then step S23 is executed. In step S23, it is judged whether there is an obstacle intersecting the line segment defined by the start node start and the target node end in the obstacle list, If it is the first obstacle intersected by the line segment defined by the start node start and the target node end, execute step S24, otherwise execute step S31. In a specific implementation manner, the judging whether there is an obstacle intersecting the line segment defined by the starting node start and the target node end in the obstacle list may include: calculating The cross product product of the line segment defined by the two end points of each obstacle and the line segment defined by the start node start and the target node end, if the cross product product is non-zero, then it is determined that the obstacle and the line segment defined by The line segment defined by the start node start and the target node end intersects, otherwise it is determined that the obstacle does not intersect the line segment defined by the start node start and the target node end.

In step S24, the obstacle nodes temp1 and temp2 at both ends of each first obstacle are obtained, wherein the coordinates of temp1 can be recorded as temp1_x and temp1_y, and the coordinates of temp2 can be recorded as temp2_x and temp2_y, and then step S25 is performed .

In step S25, for each of the first obstacles, it is searched whether there are key nodes associated with the end obstacle nodes temp1 and temp2 at both ends of the first obstacle in the list of key nodes, if found If the end obstacle nodes at both ends of the first obstacle are key nodes associated with temp1 and temp2, then step S27 is executed; otherwise, step S26 is executed.

In step S26, the first non-obstacle node and the second non-obstacle node adjacent to the end obstacle nodes temp1 and temp2 at both ends of the first obstacle are obtained, and the first non-obstacle node and the second non-obstacle node are selected. Among the non-obstacle nodes, the non-obstacle node whose distance (calculated by the above formula (1)) is closest to both the start node start and the target node end is used as the temporary target node end', and then step S28 is executed.

In step S27, for each of the first obstacles, select the one with the shortest distance (calculated using one of the above formulas (2)-(6)) to the obstacle node temp1 of the first obstacle among the key nodes A key node is used as the first key node temp1_key and the distance (using one of the above formulas (2)-(6) to calculate) the nearest key node to the obstacle node temp2 of the first obstacle in the key nodes is selected as The second key node temp2_key, then select the distance between the first key node temp1_key and the second key node temp2_key with the start node start and the target node end (using the above formula (1) to calculate ) the nearest key node as the temporary target node end', and then execute step S28.

In step S28, all adjacent nodes of the starting node start are acquired and added to the OPEN list, and then step S29 is executed. In step S29, calculate and obtain the adjacent node with the closest distance (using one of the above formulas (2)-(6)) to the temporary target node end' in the adjacent nodes, and the starting The start node start is added to the CLOSED list while the start node start is deleted from the OPEN list, and the one adjacent node is set as a new start node start, and then step S30 is executed.

In step S30, it is judged whether to set the temporary target node end' as the new starting node start (that is, to judge whether the current node coincides with the temporary target node end'), if the temporary target node end 'is not set as the new starting node start, return to step S28, otherwise return to step S22.

In step S31, all adjacent nodes of the starting node start are acquired and added to the OPEN list, and then step S32 is executed. In step S32, calculate and obtain the nearest adjacent node with the distance (using one of the above formulas (2)-(6)) from the target node end among the adjacent nodes, and the starting node start is added to the CLOSED list, and at the same time, the start node start is deleted from the OPEN list, and the one adjacent node is set as a new start node, and then step S33 is executed. In step S33, it is judged whether the new start node start coincides with the target node end, if yes, execute step S34, otherwise return to execute step S31. In step S34, add the target node end into the CLOSED list, and draw the set path between the starting node and the target node through all the nodes in the closed list.

In the embodiment of the present invention, the minimum binary heap is used to maintain the OPEN list, so operations such as inserting nodes, deleting nodes, sorting, and taking out the smallest node can be conveniently performed, thereby improving the efficiency of traversing nodes in the OPEN list.

In a specific implementation manner, before using the HRPA* algorithm to calculate the path between the starting node start and the target node end, it is first judged whether the set starting node start and the target node end overlap, and only after judging the When the set start node start and the target node end do not coincide, the HRPA* algorithm is used to calculate the path between the set start node start and the target node end. In addition, after drawing the set path between the starting node and the target node through all the nodes in the CLOSED list, the OPEN list and the CLOSED list can be cleared for the next calculation.

In the 3D panoramic roaming pathfinding method provided by the embodiment of the present invention, the data structure of the information related to the nodes in the obtained 3D panoramic image is described in the JSON data exchange format and an undirected graph is obtained, and the obstacle list and key Node list, after that, in the case of setting the start node and target node in the nodes in the three-dimensional panorama, use the A* algorithm combined with the established obstacle list and key node list, that is, the HRPA* algorithm to calculate the set The path between the start node and the destination node of . Compared with using the existing A* algorithm for path navigation and path planning in the three-dimensional panoramic roaming, since the obstacle list and the key node list are pre-established in the invention, and the HRPA* algorithm based on this is used, it can be used at the beginning When there is an obstacle between the start node and the target node, the path is cut into two or more sections for pathfinding, which significantly reduces the number of traversed nodes, thereby improving the efficiency of path search.

second embodiment

FIG. 3 is a schematic structural diagram of a three-dimensional panoramic roaming pathfinding system provided by a second embodiment of the present invention. Referring to FIG. 3 , the 3D panoramic roaming pathfinding system 200 provided by the second embodiment of the present invention may include an acquisition module 210 , a description module 220 , an establishment module 230 , a setting module 240 and a calculation module 250 .

The acquisition module 210 is used to acquire the 3D panorama and information related to the nodes in the 3D panorama.

The description module 220 is used for describing the data structure of the information related to the nodes in JSON data exchange format and obtaining the undirected graph.

The building module 230 is used for building an obstacle list and a key node list according to the data structure and the undirected graph.

The setting module 240 is used for setting a start node and a target node among the nodes in the 3D panorama.

The calculation module 250 is used to calculate the path between the starting node and the target node by using the A* algorithm combined with the obstacle list and the key node list, that is, the HPRA* algorithm in the embodiment of the present invention.

Each of the above modules may be implemented by software codes. In addition, each of the above modules may also be implemented by hardware such as an integrated circuit chip.

For the specific process of realizing the respective functions of each functional module of the three-dimensional panoramic roaming pathfinding system 200 in this embodiment, please refer to the specific content described in the embodiment shown in FIGS.

It should be noted that each embodiment in this specification is described in a progressive manner, and each embodiment focuses on the differences from other embodiments. For the same and similar parts in each embodiment, refer to each other, that is, Can. For the device-type embodiments, since they are basically similar to the method embodiments, the description is relatively simple, and for related parts, please refer to part of the description of the method embodiments.

It should be noted that, in this document, the term "comprising", "comprising" or any other variation thereof is intended to cover a non-exclusive inclusion such that a process, method, article or apparatus comprising a set of elements includes not only those elements, It also includes other elements not expressly listed, or elements inherent in the process, method, article, or device. Without further limitations, an element defined by the phrase "comprising a ..." does not exclude the presence of additional same elements in the process, method, article or apparatus comprising said element.

Those of ordinary skill in the art can understand that all or part of the steps for implementing the above embodiments can be completed by hardware, and can also be completed by instructing related hardware through a program. The program can be stored in a computer-readable storage medium. The above-mentioned The storage medium mentioned may be a read-only memory, a magnetic disk or an optical disk, and the like.

The above description is only a preferred embodiment of the present invention, and does not limit the present invention in any form. Although the present invention has been disclosed as above with preferred embodiments, it is not intended to limit the present invention. Anyone familiar with this field Those skilled in the art, without departing from the scope of the technical solution of the present invention, may use the technical content disclosed above to make some changes or modify equivalent embodiments with equivalent changes, but as long as they do not depart from the technical solution of the present invention, according to the technical content of the present invention Any simple modifications, equivalent changes and modifications made to the above embodiments by the technical essence still belong to the scope of the technical solutions of the present invention.

Claims (9)

1. A three-dimensional panoramic roaming method for finding a way, is characterized in that, comprising: Obtaining a 3D panorama and information related to nodes in the 3D panorama; Describe the data structure of the information related to the node in JSON data exchange format and obtain the undirected graph; Establishing an obstacle list and a key node list according to the data structure and the undirected graph; Setting a start node and a target node in the nodes in the three-dimensional panorama; calculating a path between the starting node and the target node using the A star algorithm combined with the obstacle list and the key node list, Wherein, the calculation of the path between the starting node and the target node using the A star algorithm combined with the obstacle list and the key node list includes: Initialize open list and close list; adding the start node to the open list; Judging whether there is an obstacle intersecting the line segment defined by the starting node and the target node in the obstacle list, when it is judged that there is an obstacle intersecting the line segment defined by the starting node and the When the line segment defined by the target node intersects the first obstacle, for each of the first obstacles, it is searched whether there is a key node associated with the end obstacle nodes at both ends of the first obstacle in the list of key nodes; When the key nodes associated with the end obstacle nodes at both ends of the first obstacle are found, one of the found key nodes is selected as a temporary target node; Obtaining all adjacent nodes of the starting node and adding the adjacent nodes to the open list, calculating and obtaining the adjacent node with the shortest distance from the temporary target node among the adjacent nodes, and adding the The starting node is added to the closed list while deleting the starting node from the open list, and an adjacent node closest to the temporary target node is set as a new starting node, repeating This step until setting the temporary target node as the new starting node; Return the method of adding the starting node into the open list. 2. The three-dimensional panoramic roaming pathfinding method according to claim 1, characterized in that, the method further comprises: when it is judged that the obstacle list does not exist and the starting node and the target node When the defined line segment intersects the first obstacle, Obtaining all adjacent nodes of the starting node and adding the adjacent nodes to the open list, calculating and obtaining the adjacent node with the closest distance to the target node among the adjacent nodes, adding the The initial node is added to the closed list and the initial node is deleted from the open list, and an adjacent node with the closest distance to the target node is set as a new initial node; Judging whether the new starting node coincides with the target node, if so, adding the target node into the closed list, and drawing the set starting node through all nodes in the closed list and the path between the target node, otherwise return to the step of obtaining all adjacent nodes of the starting node and adding the adjacent nodes to the open list. 3. The three-dimensional panoramic roaming pathfinding method according to claim 1, wherein the method further comprises: when no key node associated with the end obstacle nodes at both ends of the first obstacle is found, Acquiring a first non-obstacle node and a second non-obstacle node respectively adjacent to end obstacle nodes at both ends of the first obstacle; Selecting a non-obstacle node with the shortest distance to both the start node and the target node among the first non-obstacle node and the second non-obstacle node as the temporary target node. 4. The three-dimensional panoramic roaming pathfinding method according to claim 1, wherein the selection of one of the key nodes found as a temporary target node includes: For each of the first obstacles, select one of the key nodes that is closest to one end of the first obstacle as the first key node, and select another key node between the key nodes and the first obstacle. A key node with the closest distance at one end is used as the second key node, and a key node with the closest distance to both the starting node and the target node among the first key node and the second key node is selected as a temporary target node. 5. The three-dimensional panoramic roaming pathfinding method according to claim 1, wherein the judging whether there is an obstacle intersecting a line segment defined by the starting node and the target node in the obstacle list ,include: calculating the cross-product product of the line segment defined by the two end points of each obstacle in the obstacle list and the line segment defined by the start node and the target node, if the cross-product product is a non-zero value, Then it is determined that the obstacle intersects the line segment defined by the start node and the target node, otherwise it is determined that the obstacle does not intersect the line segment defined by the start node and the target node. 6. The three-dimensional panoramic roaming pathfinding method according to claim 1, wherein the distance is calculated by the Manhattan distance formula or the distance formula between two points. 7. The three-dimensional panoramic roaming pathfinding method according to claim 1, wherein the information related to the node includes the longitude and latitude coordinates of the node, the location name and the association with other nodes. 8. The three-dimensional panoramic roaming pathfinding method according to claim 7, wherein the data structure includes the unique identifier of the node, the title, the path of the panoramic map, whether it can rotate freely, the speed of free rotation, and the information prompt box , latitude, longitude, whether it is an obstacle node, whether it is a key node, and other nodes that can be jumped to, Obstacles in the obstacle list are formed by adjacent obstacle nodes, and key nodes in the key node list are associated with end obstacle nodes forming the obstacle. 9. A three-dimensional panoramic roaming pathfinding system, characterized in that it comprises: An acquisition module, configured to acquire a 3D panorama and information related to nodes in the 3D panorama; A description module, used to describe the data structure of the information related to the node in JSON data exchange format and obtain an undirected graph; A building module, used to create a list of obstacles and a list of key nodes according to the data structure and the undirected graph; A setting module, configured to set a start node and a target node among the nodes in the three-dimensional panorama; a calculation module, configured to calculate a path between the starting node and the target node using the A star algorithm combined with the obstacle list and the key node list, Wherein, the calculation of the path between the starting node and the target node using the A star algorithm combined with the obstacle list and the key node list includes: Initialize open list and close list; adding the start node to the open list; Judging whether there is an obstacle intersecting the line segment defined by the starting node and the target node in the obstacle list, when it is judged that there is an obstacle intersecting the line segment defined by the starting node and the When the line segment defined by the target node intersects the first obstacle, for each of the first obstacles, it is searched whether there is a key node associated with the end obstacle nodes at both ends of the first obstacle in the list of key nodes; When the key nodes associated with the end obstacle nodes at both ends of the first obstacle are found, one of the found key nodes is selected as a temporary target node; Obtaining all adjacent nodes of the starting node and adding the adjacent nodes to the open list, calculating and obtaining the adjacent node with the shortest distance from the temporary target node among the adjacent nodes, and adding the The starting node is added to the closed list while deleting the starting node from the open list, and an adjacent node closest to the temporary target node is set as a new starting node, repeating This step until setting the temporary target node as the new starting node; Return the method of adding the starting node into the open list.