CN101900565A - Path determining method and device - Google Patents
Path determining method and device Download PDFInfo
- Publication number
- CN101900565A CN101900565A CN200910027265XA CN200910027265A CN101900565A CN 101900565 A CN101900565 A CN 101900565A CN 200910027265X A CN200910027265X A CN 200910027265XA CN 200910027265 A CN200910027265 A CN 200910027265A CN 101900565 A CN101900565 A CN 101900565A
- Authority
- CN
- China
- Prior art keywords
- point
- position point
- key
- points
- shortest path
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
- 238000000034 method Methods 0.000 title claims abstract description 58
- 238000004364 calculation method Methods 0.000 claims description 35
- 230000008569 process Effects 0.000 description 8
- 238000010586 diagram Methods 0.000 description 7
- 238000012545 processing Methods 0.000 description 4
- 238000007726 management method Methods 0.000 description 3
- 238000012986 modification Methods 0.000 description 3
- 230000004048 modification Effects 0.000 description 3
- 238000013459 approach Methods 0.000 description 2
- 230000001174 ascending effect Effects 0.000 description 2
- 230000015572 biosynthetic process Effects 0.000 description 2
- 230000008859 change Effects 0.000 description 2
- 238000013507 mapping Methods 0.000 description 2
- 238000013439 planning Methods 0.000 description 2
- 238000002360 preparation method Methods 0.000 description 2
- 238000003786 synthesis reaction Methods 0.000 description 2
- 238000004458 analytical method Methods 0.000 description 1
- 238000010276 construction Methods 0.000 description 1
- 238000013461 design Methods 0.000 description 1
- 230000000694 effects Effects 0.000 description 1
- 230000007613 environmental effect Effects 0.000 description 1
- 238000011156 evaluation Methods 0.000 description 1
- 230000006872 improvement Effects 0.000 description 1
- 230000010354 integration Effects 0.000 description 1
- 238000013178 mathematical model Methods 0.000 description 1
- 238000012544 monitoring process Methods 0.000 description 1
- 238000005457 optimization Methods 0.000 description 1
- 239000007787 solid Substances 0.000 description 1
Images
Landscapes
- Navigation (AREA)
Abstract
The invention relates to a path determining method and a device, wherein the method comprises the following steps: determining a first key position point which is nearest to a source position point and is pre-saved, and a second key position point which is nearest to a target position point; calculating a first shortest path between the source position point and the first key position point and a second shortest path between the target position point and the second key position point; and obtaining a third shortest path between the first key position point which is pre-saved and the second key position point, and determining a path between the source position point and the target position point according to the first shortest path, the second shortest path and the third shortest path. The adoption of the method and the device can reduce the computation workload, further improve the overall efficiency of computation and improve the user experience.
Description
Technical Field
The invention relates to the technical field of computers, in particular to a method and a device for determining a path between two position points under a complex traffic network diagram.
Background
A Geographic Information System (GIS) is a System that processes Geographic Information. Here, the geographic information refers to information directly or indirectly related to a spatial position on the earth, and is also referred to as spatial information. In general, GIS can be defined as: "computer systems for gathering, storing, managing, processing, retrieving, analyzing, and expressing geospatial data are common techniques for analyzing and processing vast amounts of geographic data". From the application point of view of the GIS system, the method can be further defined as the following steps: the GIS is composed of a computer system, geographic data and users, generates and outputs various geographic information through integration, storage, retrieval, operation and analysis of the geographic data, thereby providing new knowledge for land utilization, resource evaluation and management, environmental monitoring, transportation, economic construction, city planning and government department administrative management, and serving engineering design, planning and management decision-making.
One typical application of GIS is traffic mapping, including application scenarios for urban public roads, highway traffic, and the like. In traffic mapping applications, one of the main technical applications is to query the shortest path, or the optimized path, between two given locations.
The mathematical model of the path searching algorithm in the GIS is to map the geographic position in the GIS into a weighted graph, each node in the graph is a position, and the weight of a connecting line between two nodes represents the distance between the two positions, as shown in fig. 1. The shortest distance between two locations can be found by such a weighted graph, i.e. equivalent to calculating the shortest distance between two nodes in the graph using graph theory techniques.
At present, the method for calculating the shortest path of the geographical map is mainly to adopt a Dijkstra algorithm. The Dijistra shortest path algorithm is an optimization method used for calculating the shortest path in the current graph theory. The basic idea of the Dijkstra algorithm is as follows: let s be the set of vertices whose shortest distances have been determined, and V-s be the set of vertices whose shortest distances have not been determined, the basic steps mainly include:
(1) initialization
At initialization, only the shortest distance of the active point S is known (sd (S) ═ 0), so S ═ S }.
(2) Repeating the following steps to generate the shortest path of each vertex according to the ascending order of the path length
And selecting a point J with the minimum shortest distance from the current V-s point set to expand the s point set so as to ensure that the algorithm generates the shortest path of each vertex according to the ascending order of the path length.
When only points with the shortest distance of ∞ are left in the V-S point set or points in all the V-S point sets are expanded to the S point set, the shortest path from S to all vertexes is obtained.
If a path from the source point to the point J does not exist, it can be assumed that the shortest path from the starting point to the point J is a virtual path with infinite length.
The shortest path from the source point S to the destination point v is simply called the shortest path of v; the shortest path length from S to v is abbreviated as the shortest distance of v and is denoted as SD (v).
(3) Selecting a point k with the minimum shortest distance from the V-S point set to expand the S point set to generate the shortest path according to the idea of increasing the sequence according to the length, wherein the shortest path of the point k in the V-S point set with the minimum shortest distance is as follows:
source points, S1, S2, □, S, k
The distance is as follows: the shortest distance from the source point to the point S + < S, k > side length.
And setting a vector D [0.... n-1] for solving conveniently, and recording the shortest path length (estimation distance for short) of a point V belonging to V-S in each V-S point set point, wherein the point V belongs to V-S, reaches V from a source point S, and does not pass through any point in the V-S point set except V in the middle (if an intermediate point exists, the point in the S point set is required to be the intermediate point).
If k is the vertex with the smallest estimated distance in the V-S point set, the estimated distance of k is the shortest distance, that is, if D [ k ] equals rain { D [ i ] i ∈ V-S }, then D [ k ]: SD (k).
Initially, the value of D [ e ] for point V in each set of V-S points should be the weight w < S, V >, and there are no intermediate points on the path from S to V, since the path contains only one edge < S, V >.
The method is characterized in that a point k with the minimum shortest distance is selected from a V-S point set to expand the S point set.
(4) After k expands point set s, modification of estimated distance of V-s point set
After expanding k to the s-point set, the estimated distances of the points in the remaining V-s point set may decrease due to the addition of new points k, at which point the estimated distances of the points in the corresponding V-s point set must be adjusted.
For point j in any set of V-s points, if D [ j ] is made smaller after k is changed from the set of V-s points to the set of next s points, then this must be due to the existence of a shorter path from s to j that contains the new point k: p ═ s, □, k, j >. And the new path P with reduced D j is only possible due to the path < S, □, k > and edge < k, j >.
Therefore, when length (P) ═ D [ k ] + W < k, j > is less than D [ j ], the value of D [ j ] should be modified by the length of P.
From the perspective of graph theory, Dijkstra algorithm is the best shortest path calculation method at present, but when applied to traffic maps, Dijkstra algorithm has certain limitations:
1) the number of position points in the traffic map is usually very large, and by using the Dijkstra algorithm, after the number of the points reaches a certain degree, the time overhead of the algorithm execution may exceed the actual allowable scale of software application, so that the efficiency is not high, and the user experience is not reduced;
2) the shortest path sought by the traffic map is not necessarily the shortest path in a strict graph theory sense, but may actually include other consideration factors, such as road conditions, traffic capacity, and the like, which cause the shortest path sought by the traffic map to be an approximate shortest path in nature, and to be an optimized path comprehensively considering other factors.
Especially for large traffic maps, effective use effect cannot be obtained by simply using Dijkstra algorithm, so that a better technical scheme needs to be sought for the large traffic maps.
Disclosure of Invention
In view of this, the present invention provides an improved path determination scheme, so as to solve the problem in the prior art that the operation speed is not high due to the Dijkstra algorithm adopted in the large traffic map.
According to one aspect of the present invention, a path determination method is provided for determining a path between a source location point and a target location point on a traffic map.
The path determining method according to the present invention includes: determining a first key position point which is stored in advance and is closest to the source position point and a second key position point which is closest to the target position point; calculating a first shortest path between the source position point and the first key position point and a second shortest path between the target position point and the second key position point; and acquiring a third shortest path between the first key position point and the second key position point which are stored in advance, and determining a path between the source position point and the target position point according to the first shortest path, the second shortest path and the third shortest path.
According to another aspect of the present invention, there is provided a path determination apparatus.
The path determination device according to the present invention includes: the device comprises a storage module, an acquisition module, a calculation module and a path determination module. The storage module is used for storing preset and calculated position information of all key position points in the traffic map and the shortest path between all the key position points; the acquisition module is used for acquiring a first key position point which is stored by the storage module and is closest to the source position point and a second key position point which is stored by the storage module and is closest to the target position point; the calculation module is used for calculating a first shortest path between the source position point and the first key position point and a second shortest path between the target position point and the second key position point; and the path determining module is used for determining a path between the source position point and the target position point according to the shortest path between the first key position point and the second key position point stored by the storage module and the first shortest path and the second shortest path calculated by the calculating module.
Through at least one scheme of the invention, the shortest path between each key position point in the traffic map is preserved in advance, and when the path between any two position points is calculated, the shortest path between each position point and the nearest key position point is calculated, so that the path between the two position points is determined, the workload of calculation can be reduced, the overall efficiency of calculation is improved, and the user experience is improved.
Additional features and advantages of the invention will be set forth in the description which follows, and in part will be obvious from the description, or may be learned by practice of the invention. The objectives and other advantages of the invention will be realized and attained by the structure particularly pointed out in the written description and claims hereof as well as the appended drawings.
Drawings
The accompanying drawings, which are included to provide a further understanding of the invention and are incorporated in and constitute a part of this specification, illustrate embodiments of the invention and together with the description serve to explain the principles of the invention and not to limit the invention. In the drawings:
FIG. 1 is a flow chart of a path determination method according to an embodiment of the invention;
FIG. 2 is a flowchart of a first embodiment;
FIG. 3 is a schematic diagram illustrating identification of a large station in a traffic map according to an embodiment;
FIG. 4 is a diagram illustrating a path between two location points according to one embodiment;
FIG. 5 is a flowchart of the second embodiment;
FIG. 6 is a schematic diagram showing a division of a neutron map in the second embodiment;
FIG. 7 is a diagram illustrating the determination of boundary points of a sub-graph adjacent to a position point in the second embodiment;
fig. 8 is a schematic structural diagram of a path determination device according to an embodiment of the present invention.
Detailed Description
Overview of the function
Aiming at the problems that a large traffic map has more position points and the traditional shortest path calculation method cannot obtain good efficiency, the embodiment of the invention provides an improved optimized path determination method which can effectively improve the path calculation efficiency in the large traffic map. In the embodiment of the invention, key parts in a large traffic map are extracted (such as abstract large stations and abstract sub-map areas), a subset map only containing key position points is formed, the subset map is pre-calculated, an optimal path between all the key position points is generated and stored in a data table, for any two position points, firstly, the key position point closest to the two position points is searched, the shortest path between the two key position points is searched from the data table, and then, for each given position point, the shortest path from the given position point to the searched nearest key position point is calculated, so that the path between the two position points is determined.
The embodiments and features of the embodiments in the present application may be combined with each other without conflict.
The preferred embodiments of the present invention will be described in conjunction with the accompanying drawings, and it will be understood that they are described herein for the purpose of illustration and explanation and not limitation.
According to an embodiment of the present invention, a path determining method is provided for determining a path between a source location point and a target location point on a traffic map.
Fig. 1 is a flowchart of a path determining method according to an embodiment of the present invention, and as shown in fig. 1, the path determining method according to the embodiment of the present invention mainly includes the following steps:
step S101: determining a key position point P0 which is saved in advance and is closest to the source position point and a key position point P which is closest to the target position point;
step S103: calculating a shortest path between the source location point and the key location point P0S 1, and a shortest path between the destination location point and the key location point P S2;
step S105: and obtaining the pre-saved shortest path S3 between the key position point P0 and the key position point P, and determining the path between the source position point and the target position point according to the shortest paths S1, S2 and S3.
In a specific implementation process, the key location point may be a large station extracted from a traffic map in advance (that is, a location point with important geographic location characteristics in the traffic map, for example, located on a main road or connecting multiple connected location points), that is, a route determination method based on priority of the large station; the traffic map may be divided into a plurality of regions (which may also be referred to as sub-maps), and the boundary points of each region, i.e., the route determination method based on region priority, are described below by specific embodiments.
The first embodiment is as follows: path determination method based on big site priority
According to the embodiment, a calculation method for dividing position points in a large traffic map into a large station and a small station and solving a preferred path between the two position points is provided, and in the embodiment, determining a path between any two position points mainly comprises the following two parts:
A) for all location points on a large traffic map, there are some location points with important geographical location characteristics, such as: or on the main road or connected with a plurality of connected position points, in the embodiment, the important position points are set as large stations, and other position points on the large traffic map are set as small stations. Moreover, on a large traffic map, the arrangement of large stations is relatively uniformly distributed in each area of the traffic map, and the number of small stations is greater than that of large stations.
B) When an optimized path from a starting position point to a target position point needs to be determined, a large station-the starting large station (i.e. the key position point P0) corresponding to the starting position point and a large station-the target large station (i.e. the key position point P) corresponding to the target position point can be determined; then determining and calculating a preferred path between the starting large station and the target large station; respectively calculating a preferred path from the starting position point to the starting large station and a preferred path from the target large station to the target position point; and determining the optimal path from the starting position point to the target position point according to the synthesis of the three paths.
Specifically, as shown in fig. 2, the method for determining a path between two positions according to the present embodiment mainly includes the following steps:
step S201: large sites are marked from the original traffic map and preferred paths (i.e., shortest paths) between the large sites are calculated and saved. Specifically, as shown in fig. 2, the process of step S201 may include substeps of steps S201A, S201B, and S201C, etc. Wherein,
step S201A: according to the importance of the positions of the position points in the original traffic map, the position points in the traffic map are marked as a large station and a small station respectively, and the large station is registered (namely stored) in a large station data table. As shown in fig. 3, a large station is marked as a black solid point in the traffic map, and a small station is marked as a black open point, and in fig. 3, P1 to P8 are all large stations, and A, B are small stations.
Step S201B: for each big station in the big station data table, searching the big stations adjacent to the big station, recording the proximity relation into the big station data table, and calculating the optimal path from each big station to the big stations adjacent to the big station, wherein the shortest path is also stored in the big station data table adjacent to the big station (including the path length, the big stations and the small stations passing through in sequence).
In the implementation, the nearby big sites of each big site are calculated, including but not limited to the following three methods:
(1) and the method of manual identification is that a large site is identified by a human being.
(2) The depth-first approach calculation method has the basic principle that starting from a source big site, the depth-first approach is performed on adjacent sites (including big sites and small sites), and the traversed big sites are sequentially registered in an adjacent big site list within the permission of a certain depth range; if there is an already registered neighboring large site in the path from the source large site to a large site, the large site is not considered as a neighboring large site, for example, in fig. 3, if the allowed depth is 4, the neighboring large site of the large site P1 includes: p2, P3, P4 and P6, whereas P1 to P8, although having a depth of 4, already the path from P1 to P8 necessarily includes one registered large site (P4), and therefore P8 is not the next large site of the large site P1;
(3) and a radius intra-domain proximity calculation method, wherein the algorithm uses a source large site as a center and uses an initial length as a radius to draw a circle, and if a path reaching the source large site exists in the large site in the radius length range, the large site in the radius length range is a neighboring large site of the source large site. If no neighboring large site can be found within the path length of the initial length, the radius length can be stepped up until a neighboring large site for the source large site is found, or the upper bound of the allowed radius is reached.
In the implementation process, the calculation of the optimal path from the source large station to the neighboring large station includes, but is not limited to, the following methods:
(1) the radius domain subgraph shortest path calculation method can use a source large station as a center, use a certain proper length as a radius to draw a circle to form a circular area, wherein the circular area can cover all adjacent large stations, and then use a sub-traffic map formed by all position points in the circular area to calculate the optimal path from each large station to the adjacent large stations by adopting a Dijstra calculation method.
(2) And a depth-first shortest path calculation method, wherein a depth-first traversal method is used to obtain all paths from the source large site to the adjacent large site within the permission of a certain depth range, and an optimal path is selected from the paths. If the allowed depth is not long enough to find a path from the source large site to the target large site, the allowed depth can be expanded and searched in the new depth.
Step S201C: and calculating the optimal path from each large station in the large station data table to all adjacent large stations, and storing the optimal paths into the large station optimal path data table.
All the large stations are constructed into a traffic map subset called a large station traffic map, the path length between each large station is the path length of the optimal path from each large station to the adjacent station established in step S201B, and the shortest path between each two large stations is calculated by using the large station traffic map. Specifically, the Dijstra calculation method can be used to calculate the shortest path between every two large stations by using the large station traffic map.
In a specific implementation process, the above processing of step S201 may be performed in advance, the calculation result (i.e. the shortest path between every two large sites) is stored, and when a path between two arbitrary location points needs to be calculated, the calculation is performed according to the stored result.
Step S202: using the obtained result of step S201, a preferred path between any two location points on the traffic map is calculated. Taking fig. 4 as an example, the processing of step S202 includes the following steps:
step S202A: two location points A, B (i.e., two stops) on any given traffic map, assuming that both are small stops;
if the location point a and/or the location point B is not a small site, i.e., a or B is a large site, the large site adjacent to the site a or B acquired in step S202B is itself.
Step S202B: the large sites adjacent to the small site a and the small site B are calculated respectively, and various methods in step S201B may be specifically used. In this embodiment, the large site adjacent to the small site a is P1, and the large site adjacent to the small site B is P7.
Step S202C: from the large-site optimal path data table generated in step S201C, an optimal path between the large site P1 and the large site P7 is searched.
Step S202D: the optimal path from small site a to large site P1 is calculated. Specifically, the calculation may be performed by using a method of calculating an optimal path from the source large station to the neighboring large station in step S201B, that is, a radius domain subgraph shortest path calculation method or a depth-first shortest path calculation method may be used. Likewise, the optimal path from small site B to large site P7 may be calculated.
Step S202E: according to steps S202C, S202D, a preferred path from cell a to cell B is obtained, which may be composed of three segments as follows: the optimal path from the small site A to the large site P1, the optimal path from the large site P1 to the large site P2, and the optimal path from the big site P2 to the small site B are the sequential sum of the three paths.
In the above embodiment, step S201 belongs to the preparation step, and may be performed after the traffic map is established, without waiting for the time to find the preferred route between the two location points, so that the process of calculating the preferred route between the two location points may be accelerated. When the traffic map is changed, the calculation of the re-step S201 may be performed. If the change of the traffic map is limited to only a local part, the calculation of step S201 may be performed on the local traffic map while leaving the other parts unchanged, and the amount of calculation may be greatly reduced.
Example two: path determining method based on regional priority
According to the present embodiment, a method for dividing a large traffic map into several sub-map regions and solving a preferred path between two location points on the basis of the sub-map regions is provided, and in the present embodiment, the method for determining a path between two location points mainly includes two parts:
(1) the large traffic map is divided into a plurality of areas, each area is not overlapped with each other, namely, no intersected part exists between the areas, and in the embodiment, one area is called as a sub-map. The boundary of the sub-graph is formed by connecting a plurality of sub-graph boundary points (which can also be called as boundary points of the region), and each position point only belongs to a specific sub-graph.
(2) In the present embodiment, when determining the optimized path from a starting position point P1 (i.e. the source position point) to a target position point P2, the following steps may be included: firstly, determining a subgraph Z1 to which a starting position point P1 belongs and a subgraph Z2 to which a target position point P2 belongs; determining an optimal path from each sub-graph boundary point of the sub-graph Z1 to each sub-graph boundary point of the sub-graph Z2; acquiring a sub-graph boundary point of the sub-graph Z1 nearest to the position point P1, and similarly acquiring a sub-graph boundary point of the sub-graph Z2 nearest to the position point P2; then, the shortest path from the starting position point P1 to the nearest sub-graph boundary point on Z1 is obtained, and the shortest path from the position point P2 to the nearest sub-graph boundary point on Z2 is obtained; and finally, determining a preferred path from the starting position point to the target position point according to the synthesis of the three paths.
Fig. 5 is a flowchart of a method for determining an optimized route between two locations according to the present embodiment, and as shown in fig. 5, the method for determining an optimized route between two locations in a large traffic map according to the present embodiment mainly includes the following steps:
step S501: and separating the original traffic map into a plurality of adjacent subgraphs, and determining subgraph boundary points of each subgraph. And calculating the shortest path between each sub-graph boundary point of the sub-graph A and each sub-graph boundary point of the sub-graph B for any two different sub-graphs in all the sub-graphs, namely the sub-graph A and the sub-graph B. Specifically, the step may include the following steps S501A, S501B, S501C, and the like, wherein,
step S501A: the original traffic map is divided into a plurality of adjacent areas, each area can be called a sub-map (such as Z1, Z2,.. and Zn), the boundary of each sub-map (such as the boundary of the sub-map Z1) is formed by connecting a plurality of sub-map boundary points, as shown in FIG. 6, the boundary position points of the sub-map Z1 are ZP (1, 1), ZP (1, 2),. and.. and ZP (1, p), and the sub-map boundary seals the sub-map into an independent sub-map area. And storing the information of each subgraph into a subgraph data table, and registering the adjacency relation of each subgraph into an adjacent subgraph data table. These sub-graph boundary points are stored in a sub-graph boundary point data table.
Step S501B: and calculating the distance from the boundary point of the subgraph of each subgraph to the boundary point of the subgraph adjacent to the subgraph. Wherein the proximity of one subgraph to another subgraph can be obtained from the proximity subgraph data table. The calculation method for calculating the shortest path between two subgraph boundary points may adopt the corresponding method in step S201B in the first embodiment. And storing the calculated shortest path of the two sub-graph boundary points into a sub-graph boundary point shortest path data table.
Step S501C: all sub-graph boundary points are constructed into an independent traffic graph, and the shortest path between any two sub-graph boundary points of all sub-graphs is further calculated according to the shortest path data between the boundary points of two adjacent sub-graphs calculated in S501B. The calculation can be processed by adopting Dijstra algorithm, and finally, the shortest path data between every two subgraph boundary points is stored in a subgraph boundary point shortest path data table.
Step S502: when two position points P1, P2 on the original traffic map are given, an optimized path between the two position points P1, P2 is calculated. Specifically, the optimized path between P1 and P2 may be determined according to the following steps S502A, S502B, S502C, S502D, wherein,
step S502A: according to the geographic coordinates of the P1 and P2 position points, for example, the geographic coordinates of P1 are (X1, Y1) and the geographic coordinates of P2 are (X2, Y2), the traffic subgraphs respectively belonging to the positions are searched, and in the embodiment, it is assumed that the P1 position point belongs to the subgraph Z1 and the P2 position point belongs to the subgraph Z2.
Step S502B: and acquiring a sub-graph boundary point nearest to the point at the position of P1 in the sub-graph Z1 and a sub-graph boundary point nearest to the point at the position of P2 in the sub-graph Z2.
In one implementation, as shown in fig. 7, a line may be connected between the positions P1 and P2, such that the line crosses the subgraphs Z1 and Z2, and the line is denoted as L (P1-P2). The nearest sub-graph boundary points belonging to sub-graphs Z1 and Z2 are found on both sides of the connecting line respectively. For example, on the sub-graph Z1, the adjacent sub-graph boundary points on both sides of the connecting line L (P1-P2) are: ZP (1, r), ZP (1, s). On the subgraph Z2, the adjacent subgraph boundary points on the two sides of the connecting line P1-P2 are as follows: ZP (2, u), ZP (2, v).
Specifically, the following method can be adopted to find the boundary points of the nearest subgraph Z1 and Z2 on the two sides of the position point connecting line L (P1-P2) and the nearest subgraph boundary point of the position point P1 along the direction of the ray P1 → P2:
(1) the parallel line bounding method includes moving the parallel line (denoted as L ') to both sides of the line L (P1-P2) so that the sub-graph boundary point which is included between the line L (P1-P2) and the line L' and belongs to the sub-graph Z1 and is close to the position point P2 is the sub-graph boundary point on the desired sub-graph Z1 and closest to the position point P1 along the direction of the ray P1 → P2.
(2) The radius domain definition method is solved by an algorithm similar to the radius domain intra-domain neighbor calculation method in step S201B. For the source position point P1, taking the source position point P1 as the center of a circle, taking an initial length as the radius, if the radius range contains one or more boundary points of the region where the source position point P1 is located, taking the one or more boundary points as the sought sub-graph boundary points, otherwise, gradually increasing the radius length until one or more sub-graph boundary points are found, or the maximum allowable range of the radius is reached; similarly, for the target position point P2, taking the target position point P2 as the center, and taking an initial length as the radius, if the radius range contains one or more sub-graph boundary points of the region Z2 where the target position point P2 is located, then the one or more sub-graph boundary points are taken as the sought sub-graph boundary points, otherwise, the radius length is increased step by step until one or more sub-graph boundary points are found.
Step S502C: for the sub-graph boundary points of the sub-graphs Z1 and Z2 at the two sides of the P1-P2 connection line found in step S502B, the sub-graph boundary point shortest path data table generated in step S501C is found, and the shortest path between each two sub-graph boundary points is obtained, which is totally 4, and is recorded as: SR [ ZP (1, r), ZP (2, u) ], SR [ ZP (1, r), ZP (2, v) ], SR [ ZP (1, s), ZP (2, u) ], SR [ ZP (1, s), ZP (2, v) ].
Step S502D: for sub-graph Z1, the shortest path from position point P1 to sub-graph boundary point ZP (1, r), ZP (1, s) is computed. For sub-graph Z2, the shortest path and path length from position point P2 to sub-graph boundary point ZP (2, u), ZP (2, v) points are computed.
The calculation method of the shortest path from the position point P1 to the sub-graph boundary point obtained in step S502B may be similar to that in step S202D.
Step S502E: and calculating a synthesized optimized path according to the shortest paths calculated in the steps S502C and S502D, and searching the shortest path from the optimized paths to be the optimized path between the P1 position point and the P2 position point.
In the specific implementation process, step S501 belongs to a preparation step, which may be performed after the traffic map is established, and does not need to wait until the preferred route between two location points is found, so that the process of calculating the preferred route between two location points may be accelerated. When the traffic map is changed, the calculation of step S501 may be re-executed. If the change of the traffic map is limited to only a local part, the calculation of step S501 may be performed on the local traffic map while leaving the other parts unchanged, and the amount of calculation may be greatly reduced.
According to the embodiment of the invention, the invention further provides a path determining device, which can be used for a GIS system to realize the path determining method provided by the embodiment of the invention.
Fig. 8 is a schematic structural diagram of a path determining apparatus according to an embodiment of the present invention, and as shown in fig. 8, the path determining apparatus according to the embodiment of the present invention mainly includes: a storage module 81, an acquisition module 83, a calculation module 85 and a path determination module 87. The storage module 81 is configured to store preset and calculated position information of each key position point in the traffic map and a shortest path between each key position point; the obtaining module 83 is connected to the storage module 81, and is configured to obtain a first key location point that is closest to the source location point and is stored in the storage module 81, and a second key location point that is closest to the target location point; the calculating module 85 is connected to the obtaining module 83, and is configured to calculate a first shortest path between the source location point and the first key location point, and a second shortest path between the destination location point and the second key location point; the path determining module 87 is connected to the calculating module 85 and the storage module 81, and configured to determine a path between the source location point and the destination location point according to the shortest path between the first key location point and the second key location point stored in the storage module 81, and the first shortest path and the second shortest path calculated by the calculating module 85.
As described above, according to the technical solution provided by the embodiment of the present invention, a subset map including only key location points is formed by extracting key parts (such as abstract large sites and abstract sub-map regions) in a large traffic map, and the subset map is pre-calculated to generate an optimal path between the key location points, which is stored in a data table. When determining the path between any two position points, searching the key position point nearest to the two position points, searching the shortest path between the two key position points from the data table, and calculating the shortest path from each position point to the nearest key position point searched by the position point. Therefore, the path between the two position points is determined, and because when the shortest path from each position point to the nearest key position point is calculated, the calculation of the shortest path can be limited within a small range by a radius domain shortest path calculation method or a depth-first shortest path calculation method, thereby obtaining high operation efficiency. According to the embodiment of the invention, the traffic map is effectively cut, so that the workload of operation can be reduced, and the operation efficiency can be improved.
The above description is only a preferred embodiment of the present invention and is not intended to limit the present invention, and various modifications and changes may be made by those skilled in the art. Any modification, equivalent replacement, or improvement made within the spirit and principle of the present invention should be included in the protection scope of the present invention.
Claims (9)
1. A method for determining a path between a source location point and a target location point on a traffic map, the method comprising:
determining a first key position point which is saved in advance and is closest to the source position point and a second key position point which is closest to the target position point;
calculating a first shortest path between the source location point and the first key location point, and a second shortest path between the destination location point and the second key location point;
and acquiring a third shortest path between the first key position point and the second key position point, which is saved in advance, and determining a path between the source position point and the target position point according to the first shortest path, the second shortest path and the third shortest path.
2. The method of claim 1, wherein prior to determining a pre-saved first keypoint location point closest to the source location point, the method further comprises:
determining and storing a plurality of key position points in the traffic map according to a preset rule;
and calculating and storing the shortest path between each key position point in the plurality of key position points.
3. The method of claim 2, wherein computing and saving the shortest path between each of the plurality of key location points comprises:
for each key position point, searching the adjacent key position point, and calculating and storing the shortest path from the key position point to the adjacent key position point;
and calculating and storing the shortest path between each key position point by using the shortest path from each key position point to the adjacent key position point.
4. The method of claim 2 or 3, wherein the plurality of key location points are relatively evenly distributed in each area of the traffic map, and wherein the number of the plurality of key location points is less than the number of other location points in the traffic map.
5. The method of claim 1, wherein prior to determining a pre-saved first keypoint location point closest to the source location point, the method further comprises:
dividing the traffic map into a plurality of non-overlapping areas according to a preset rule, wherein the boundary of each area comprises a plurality of boundary points;
and respectively calculating and storing the shortest path between each boundary point of the first area and each boundary point of the second area for any two different areas, namely a first area and a second area, in the plurality of areas.
6. The method of claim 5, wherein determining a first pre-saved keypoint location point closest to the source location point and a second keypoint location point closest to the target location point comprises:
determining the areas of the source position point and the target position point according to the position information of the source position point and the position information of the target position point;
and selecting one or more boundary points nearest to the source position point from the boundary points of the region where the source position point is located as the first key position points, and selecting one or more boundary points nearest to the target position point from the boundary points of the region where the target position point is located as the second key position points.
7. The method of claim 6,
selecting one or more boundary points nearest to the source location point from among the boundary points of the region in which the source location point is located as the first keypoint location point includes:
selecting one or more boundary points which are positioned at two sides of a connecting line of the source position point and the target position point and are closest to the connecting line in each boundary point of the region where the source position point is positioned as the first key position point;
selecting one or more boundary points nearest to the target location point from among the boundary points of the area in which the target location point is located as the second key location point includes:
and selecting one or more boundary points which are positioned at two sides of a connecting line of the source position point and the target position point and are closest to the connecting line in each boundary point of the region where the target position point is positioned as the second key position point.
8. The method of claim 6,
selecting one or more boundary points from among the boundary points of the region in which the source location point is located as the first keypoint location point includes:
taking the source position point as a circle center, taking an initial length as a radius, if the radius range contains one or more boundary points of the region where the source position point is located, taking the one or more boundary points as the first key position point, and if not, gradually increasing the radius length until the one or more boundary points are found;
selecting one or more boundary points from among the boundary points of the area where the target location point is located as the second key location point includes:
and taking the target position point as a circle center, taking an initial length as a radius, if the radius range contains one or more boundary points of the area where the target position point is located, taking the one or more boundary points as the second key position point, and otherwise, gradually increasing the radius length until the one or more boundary points are found.
9. A path determination device, comprising:
the storage module is used for storing preset and calculated position information of all key position points in the traffic map and the shortest path between all the key position points;
the acquisition module is used for acquiring a first key position point which is stored by the storage module and is closest to the source position point and a second key position point which is stored by the storage module and is closest to the target position point;
a calculation module, configured to calculate a first shortest path between the source location point and the first key location point, and a second shortest path between the destination location point and the second key location point;
and the path determining module is used for determining a path between the source position point and the target position point according to the shortest path between the first key position point and the second key position point stored by the storage module and the first shortest path and the second shortest path calculated by the calculating module.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN200910027265XA CN101900565A (en) | 2009-05-26 | 2009-05-26 | Path determining method and device |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN200910027265XA CN101900565A (en) | 2009-05-26 | 2009-05-26 | Path determining method and device |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CN101900565A true CN101900565A (en) | 2010-12-01 |
Family
ID=43226312
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN200910027265XA Pending CN101900565A (en) | 2009-05-26 | 2009-05-26 | Path determining method and device |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN101900565A (en) |
Cited By (16)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN102538806A (en) * | 2010-12-30 | 2012-07-04 | 上海博泰悦臻电子设备制造有限公司 | Path planning method and related equipment |
| CN102800242A (en) * | 2011-05-25 | 2012-11-28 | 腾讯科技（深圳）有限公司 | Path finding verification method and device |
| CN103261855A (en) * | 2010-12-17 | 2013-08-21 | 罗伯特·博世有限公司 | Method and device for determining the cruising range of a motor vehicle |
| CN103292823A (en) * | 2012-02-23 | 2013-09-11 | 日本善邻数据通信有限公司 | Route searching system and route searching method |
| CN103620345A (en) * | 2011-06-28 | 2014-03-05 | 微软公司 | Providing routes through information collection and retrieval |
| CN104751733A (en) * | 2013-12-25 | 2015-07-01 | 携程计算机技术（上海）有限公司 | Region drawing method, region drawing device, path distance classifying method and path distance classifying system for maps |
| CN106403970A (en) * | 2016-06-27 | 2017-02-15 | 百度在线网络技术（北京）有限公司 | Road network data processing method and device |
| CN106445957A (en) * | 2015-08-10 | 2017-02-22 | 华为技术有限公司 | Data visualization method and device |
| CN104111074B (en) * | 2013-04-16 | 2017-03-01 | 神达电脑股份有限公司 | Mobile electronic device and method for generating navigation path |
| CN106649450A (en) * | 2016-09-23 | 2017-05-10 | 厦门嵘拓物联科技有限公司 | Method for identifying critical path in location service |
| CN107167152A (en) * | 2016-03-08 | 2017-09-15 | 高德信息技术有限公司 | Paths planning method and device |
| CN109000675A (en) * | 2018-06-20 | 2018-12-14 | 北京三快在线科技有限公司 | The method, apparatus and electronic equipment and storage medium of to acquisite approachs information |
| CN109147469A (en) * | 2018-07-09 | 2019-01-04 | 安徽慧视金瞳科技有限公司 | A kind of calligraphy exercising method |
| CN111818596A (en) * | 2020-05-21 | 2020-10-23 | 蓓安科仪（北京）技术有限公司 | Medical robot communication quality optimization method based on 5G |
| CN113701768A (en) * | 2020-05-20 | 2021-11-26 | 杭州海康威视数字技术股份有限公司 | Path determination method and device and electronic equipment |
| CN114247081A (en) * | 2019-04-04 | 2022-03-29 | 南京敏思软件有限公司 | Method and system for determining motion energy consumption of intelligent stone lock |
-
2009
- 2009-05-26 CN CN200910027265XA patent/CN101900565A/en active Pending
Cited By (27)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN103261855A (en) * | 2010-12-17 | 2013-08-21 | 罗伯特·博世有限公司 | Method and device for determining the cruising range of a motor vehicle |
| US9785612B2 (en) | 2010-12-17 | 2017-10-10 | Robert Bosch Gmbh | Method and device for determining a range of a vehicle |
| CN103261855B (en) * | 2010-12-17 | 2016-08-10 | 罗伯特·博世有限公司 | Method and device for determining the cruising range of a motor vehicle |
| CN102538806A (en) * | 2010-12-30 | 2012-07-04 | 上海博泰悦臻电子设备制造有限公司 | Path planning method and related equipment |
| CN102538806B (en) * | 2010-12-30 | 2015-10-07 | 上海博泰悦臻电子设备制造有限公司 | A kind of paths planning method and relevant device |
| CN102800242A (en) * | 2011-05-25 | 2012-11-28 | 腾讯科技（深圳）有限公司 | Path finding verification method and device |
| CN103620345A (en) * | 2011-06-28 | 2014-03-05 | 微软公司 | Providing routes through information collection and retrieval |
| CN103620345B (en) * | 2011-06-28 | 2016-08-31 | 微软技术许可有限责任公司 | Route is provided by information gathering and retrieval |
| CN103292823A (en) * | 2012-02-23 | 2013-09-11 | 日本善邻数据通信有限公司 | Route searching system and route searching method |
| CN103292823B (en) * | 2012-02-23 | 2016-01-06 | 日本善邻数据通信有限公司 | Route search system and method for searching path |
| CN104111074B (en) * | 2013-04-16 | 2017-03-01 | 神达电脑股份有限公司 | Mobile electronic device and method for generating navigation path |
| CN104751733A (en) * | 2013-12-25 | 2015-07-01 | 携程计算机技术（上海）有限公司 | Region drawing method, region drawing device, path distance classifying method and path distance classifying system for maps |
| CN106445957B (en) * | 2015-08-10 | 2019-11-12 | 华为技术有限公司 | Data visualization method and device |
| CN106445957A (en) * | 2015-08-10 | 2017-02-22 | 华为技术有限公司 | Data visualization method and device |
| CN107167152A (en) * | 2016-03-08 | 2017-09-15 | 高德信息技术有限公司 | Paths planning method and device |
| CN107167152B (en) * | 2016-03-08 | 2019-12-03 | 高德信息技术有限公司 | Paths planning method and device |
| CN106403970A (en) * | 2016-06-27 | 2017-02-15 | 百度在线网络技术（北京）有限公司 | Road network data processing method and device |
| CN106649450B (en) * | 2016-09-23 | 2019-07-23 | 厦门嵘拓物联科技有限公司 | The method of critical path is identified in a kind of location-based service |
| CN106649450A (en) * | 2016-09-23 | 2017-05-10 | 厦门嵘拓物联科技有限公司 | Method for identifying critical path in location service |
| CN109000675A (en) * | 2018-06-20 | 2018-12-14 | 北京三快在线科技有限公司 | The method, apparatus and electronic equipment and storage medium of to acquisite approachs information |
| CN109000675B (en) * | 2018-06-20 | 2021-04-23 | 北京三快在线科技有限公司 | Method and device for acquiring path information, electronic equipment and storage medium |
| CN109147469A (en) * | 2018-07-09 | 2019-01-04 | 安徽慧视金瞳科技有限公司 | A kind of calligraphy exercising method |
| CN114247081A (en) * | 2019-04-04 | 2022-03-29 | 南京敏思软件有限公司 | Method and system for determining motion energy consumption of intelligent stone lock |
| CN113701768A (en) * | 2020-05-20 | 2021-11-26 | 杭州海康威视数字技术股份有限公司 | Path determination method and device and electronic equipment |
| CN113701768B (en) * | 2020-05-20 | 2024-05-31 | 杭州海康威视数字技术股份有限公司 | Path determination method, device and electronic device |
| CN111818596A (en) * | 2020-05-21 | 2020-10-23 | 蓓安科仪（北京）技术有限公司 | Medical robot communication quality optimization method based on 5G |
| CN111818596B (en) * | 2020-05-21 | 2022-04-08 | 蓓安科仪（北京）技术有限公司 | Medical robot communication quality optimization method based on 5G |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN101900565A (en) | Path determining method and device | |
| Zhong et al. | Detecting the dynamics of urban structure through spatial network analysis | |
| US7953548B2 (en) | Location-based information determination | |
| Song et al. | Efficient routing on large road networks using hierarchical communities | |
| KR101517898B1 (en) | System and method for Estimating of the spatial development patterns based on determination factors of the city form | |
| CN102496187B (en) | Method for tracking contour line to boundary and fault based on triangular mesh | |
| CN108280463B (en) | Optimization method and device for double-layer path of vehicle-mounted unmanned aerial vehicle | |
| CN114548811B (en) | Airport reachability detection method and device, electronic equipment and storage medium | |
| CN113865589A (en) | A long-distance fast path planning method based on terrain slope | |
| Ai et al. | Generation of constrained network Voronoi diagram using linear tessellation and expansion method | |
| Daniel et al. | GIS-based study on the association between road centrality and socio-demographic parameters: A case study | |
| Mark Ware et al. | Automated production of schematic maps for mobile applications | |
| Hasan et al. | Improved GIS-T model for finding the shortest paths in graphs | |
| CN113724279A (en) | System, method, equipment and storage medium for automatically dividing traffic cells into road networks | |
| Telega | Urban street network analysis using space syntax in GIS--cracow case study | |
| Stadler et al. | A method for the optimized placement of bus stops based on voronoi diagrams | |
| Chandio et al. | An approach for map-matching strategy of GPS-trajectories based on the locality of road networks | |
| Xie et al. | An improved Dijkstra algorithm in GIS application | |
| CN115438135B (en) | Method and device for constructing temporal geographic data model based on hierarchical compression linear referencing technology, and method for constructing index structure | |
| Ware et al. | An ant colony system algorithm for automatically schematizing transport network data sets | |
| CN116975172A (en) | Zoning methods, devices, electronic equipment, storage media and program products | |
| Rasmussen et al. | Case study on geocoding based scheduling optimization in supply chain operations management | |
| CN119334358B (en) | Heterogeneous unmanned aerial vehicle cooperative road network searching method based on Euler path | |
| Matrood et al. | A simple gis based method for designing fiber-network | |
| Kumar et al. | Spatial data mining: recent trends and techniques |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| C02 | Deemed withdrawal of patent application after publication (patent law 2001) | ||
| WD01 | Invention patent application deemed withdrawn after publication |
Open date: 20101201 |