CN107677269B - A kind of low signal areas intelligent navigation method based on topological map - Google Patents
A kind of low signal areas intelligent navigation method based on topological map Download PDFInfo
- Publication number
- CN107677269B CN107677269B CN201710750686.XA CN201710750686A CN107677269B CN 107677269 B CN107677269 B CN 107677269B CN 201710750686 A CN201710750686 A CN 201710750686A CN 107677269 B CN107677269 B CN 107677269B
- Authority
- CN
- China
- Prior art keywords
- node
- user
- topological map
- time
- 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.)
- Expired - Fee Related
Links
Classifications
-
- G—PHYSICS
- G01—MEASURING; TESTING
- G01C—MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY
- G01C21/00—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00
- G01C21/20—Instruments for performing navigational calculations
-
- G—PHYSICS
- G01—MEASURING; TESTING
- G01C—MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY
- G01C21/00—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00
- G01C21/26—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00 specially adapted for navigation in a road network
- G01C21/34—Route searching; Route guidance
- G01C21/3407—Route searching; Route guidance specially adapted for specific applications
Landscapes
- Engineering & Computer Science (AREA)
- Radar, Positioning & Navigation (AREA)
- Remote Sensing (AREA)
- Automation & Control Theory (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Navigation (AREA)
Abstract
The invention discloses a kind of low signal areas intelligent navigation method based on topological map, including the grating map of navigation area needed for acquisition for mobile terminal and it is translated into topological map；User marks start node P and destination node Q in the topological map；Navigation path planning mode is selected in mobile terminal；User inputs driving parameters to the mobile terminal, and the mobile terminal is that user navigates to destination node Q according to driving parameters and navigation path planning mode.The grating map of navigation area needed for obtaining in advance is simultaneously translated into topological map, without by network continuous updating cartographic information, realizing that the real-time map of null zones is shown when to navigate；Calculating has walked ratio to know the current location of user, realizes the positioning of null zones, makes user that can also be clear from itself position in null zones, and positioning accuracy is constantly promoted in navigation procedure.
Description
Technical field
The present invention relates to navigation field more particularly to a kind of low signal areas intelligent navigation methods based on topological map.
Background technology
With the fast development of Modern wireless communication technology and popularizing for smart mobile phone, Mobile Telephone Gps are increasingly gone out by masses
Needed for row.Navigator fix technology outside traditional rooms GPS has gradually tended to be ripe, existing mobile phone after decades of development
Navigation software also has the function of map is checked, map scaling, hot spot are searched for, position and navigate etc. substantially, and portioned product is even borrowed
Acceleration transducer, direction sensor, NFC and interior WI-FI in smart mobile phone etc. is helped to realize indoor navigation.
However, GPS signal can be seriously impaired after building or other obstacles, mobile phone cannot receive GPS
Lead to location navigation misalignment or unavailable in the environment of information.In addition, navigation map is limited and is made by satellite image renewal frequency
Figure personnel's geography information grasps limitation, also has remote areas that cannot provide reliable navigation Service to the user in small range region.
Particularly, for certain low signal areas, it cannot preferably receive GPS information or GPS costs of serving are higher, and there is no NFC
And interior WI-FI auxiliary, location navigation will be unavailable.The thing for making personnel get lost in remote areas because that can not navigate in recent years
Therefore happen occasionally, even threat to life sometimes, therefore provide for the users such as such as outdoor mountain-climbing fan a set of low-cost weak
Signal area navigation system is necessary！
Invention content
It is an object of the invention to propose it is a kind of can null zones are accurately positioned and navigate based on topological map
Low signal areas intelligent navigation method.
For this purpose, the present invention uses following technical scheme：
A kind of low signal areas intelligent navigation method based on topological map, includes the following steps：
Step A, the grating map of navigation area needed for acquisition for mobile terminal are simultaneously translated into topological map；
Step B, user mark start node P and destination node Q in the topological map；
Step C selects navigation path planning mode in mobile terminal, generates corresponding best guidance path；
Step D, user input driving parameters to the mobile terminal, and the mobile terminal is according to driving parameters and navigation road
Diameter planning mode is that user navigates to destination node Q.
Preferably, the step D includes：
" driving " navigation pattern：
Step D11, user input driving parameters to the mobile terminal：Drive average speed per hour N1；
The mobile terminal shows the best guidance path of beginning node P to destination node Q on the topological map
K, by start node P to next node M on the best guidance path K1Link K1Practical section distance to be recorded as first real
Border section distance S, and the first practical section distance S is converted into the first linkage length W1, conversion formula is as follows：
That is the first linkage length W1 of link is that user covers the required of the practical section distance representated by the link
Drive time；
Step D12, user start to set out, and the mobile terminal is to record node the time constantly to set out, and record user is real
When drive time t1 (down time is not counted in the real-time drive time t1 of the user)；According to the real-time drive time t1 of the user
The first walking ratio p1 is generated, i.e.,
According to the first walking ratio p1 calculation formula and the real-time drive time t1 of the user, at interval of 1 second to institute
It is primary to state the first walking ratio p1 updates, and in current ink K1The current location of upper calibration user；
Step D13, when the first walking ratio p1 reaches 95%, the topological map will show the present bit of user
It is set in node M1On, and show node M on the topological map1To the direction arrow of each adjacent node that can directly reach
Head；
Step D14, user reach node M on topological map1Corresponding fork crossing, stop move ahead, according to it is described most
Good guidance path K or the selection of itself wish move on direction, click node M on the mobile terminal1The continuation of upper correspondence
The directional arrow of direction of advance simultaneously confirms；If user does not move on direction by the best guidance path K selections herein,
Start node P is then updated to node M1, and the C that gos to step starts to execute；
Step D15, the mobile terminal will confirm that records node at the time of the directional arrow as the time, reads at this time
The real-time drive time t1 of the user be recorded as the first running time t1', the clearing user described in new record that lays equal stress on drives in real time
Time t1, calculating difference E 1, and judge whether the difference E 1 is more than given threshold e1, wherein
Difference E1=| first the first linkage lengths of running time t1'- W1 |；
If E1>The average speed per hour N1 that drives then is updated to the average speed per hour N1' that actually drives by e1, wherein
Step D16 finds node M according to the directional arrow that user is confirmed in the mobile terminal1To next section
Point M2Link K2, the first practical section distance S is updated to link K2Practical section distance, while press above-mentioned first link
Length W1 calculation formula update the first linkage length W1, and continue to navigate by step D12；
Step D17 constantly repeats step D13 to step D16, until user travels to destination node Q.
Preferably, the step D further includes：
" walking " navigation pattern：
Step D21, user input driving parameters to the mobile terminal：User's height H (cm)；The mobile terminal calculates
User step-length N2, calculation formula are as follows：
User's step-length N2=0.45 × user's height H；
The mobile terminal shows the best guidance path of beginning node P to destination node Q on the topological map
K, by start node P to next node M on the best guidance path K1Link K1Practical section distance to be recorded as first real
Border section distance S, and the first practical section distance S is converted into the second linkage length W2, conversion formula is as follows：
That is the second linkage length W2 of link is that user covers the step number needed for the practical section representated by the link；
Step D22, user start to set out, and the mobile terminal is to record node the time constantly to set out, and record user is real
When step number t2；The second walking ratio p2 is generated according to the real-time step number t2 of the user, i.e.,
According to the second walking ratio p2 calculation formula and the real-time step number t2 of user, at interval of 1 second to second row
It is primary to walk ratio p2 updates, and in current ink K1The current location of upper calibration user；
Step D23, when the second walking ratio p2 reaches 95%, the topological map will show the present bit of user
It is set in node M1On, and show node M on the topological map1To the direction arrow of each adjacent node that can directly reach
Head；
Step D24, user reach node M on topological map1Corresponding fork crossing, stop move ahead, according to it is described most
Good guidance path K or the selection of itself wish move on direction, click node M on the mobile terminal1The continuation of upper correspondence
The directional arrow of direction of advance simultaneously confirms；If user does not move on direction by the best guidance path K selections herein,
Start node P is then updated to node M1, and the C that gos to step starts to execute；
Step D25, the mobile terminal will confirm that records node at the time of the directional arrow as the time, reads at this time
The real-time step number t2 of the user be recorded as the first row and walk step number t2', clearing is laid equal stress on the real-time step number t2 of user described in new record, meter
Difference E2 is calculated, and judges whether the difference E2 is more than given threshold e2, wherein
Difference E2=| the first row walks the second linkage lengths of step number t2'- W2 |；
If E2>User's step-length N2 is then updated to actual user step-length N2' by e2, wherein
Step D26 finds node M according to the directional arrow that user is confirmed in the mobile terminal1To next section
Point M2Link K2, the first practical section distance S is updated to link K2Practical section distance, while press above-mentioned second link
Length W2 calculation formula update the second linkage length W2, and continue to navigate by step D22；
Step D27 constantly repeats step D23 to step D26, until user travels to destination node Q.
Preferably, the step D further includes：
" riding " navigation pattern：
Step D31, user input driving parameters to the mobile terminal：Ride average speed per hour N3；
The mobile terminal shows the best guidance path of beginning node P to destination node Q on the topological map
K, by start node P to next node M on the best guidance path K1Link K1Practical section distance to be recorded as first real
Border section distance S, and the first practical section distance S is converted into third linkage length W3, conversion formula is as follows：
That is the third linkage length W3 of link is that user covers the required of the practical section distance representated by the link
It rides the time；
Step D32, user start to set out, and the mobile terminal is to record node the time constantly to set out, and record user is real
When ride time t3 (down time be not counted in the user ride in real time time t3)；It is ridden in real time time t3 according to the user
Third walking ratio p3 is generated, i.e.,
It is ridden in real time time t3 according to walk ratio p3 calculation formula and the user of the third, at interval of 1 second to institute
It is primary to state third walking ratio p3 updates, and in current ink K1The current location of upper calibration user；
Step D33, when third walking ratio p3 reaches 95%, the topological map will show the present bit of user
It is set in node M1On, and show node M on the topological map1To the direction arrow of each adjacent node that can directly reach
Head；If user does not move on direction by the best guidance path K selections herein, start node P is updated to node M1,
And the C that gos to step starts to execute；
Step D34, user reach node M on topological map1Corresponding fork crossing, stop move ahead, according to it is described most
Good guidance path K or the selection of itself wish move on direction, click node M on the mobile terminal1The continuation of upper correspondence
The directional arrow of direction of advance simultaneously confirms；
Step D35, the mobile terminal will confirm that records node at the time of the directional arrow as the time, reads at this time
The user time t3 that rides in real time be recorded as first and ride time t3', the clearing user described in new record that lays equal stress on rides in real time
Time t3, calculating difference E3, and judge whether the difference E3 is more than given threshold e3, wherein
Difference E3=| first rides time t3'- third linkage length W3 |；
If E3>The average speed per hour N3 that rides then is updated to the average speed per hour N3' that actually rides by e3, wherein
Step D36 finds node M according to the directional arrow that user is confirmed in the mobile terminal1To next section
Point M2Link K2, the first practical section distance S is updated to link K2Practical section distance, while press above-mentioned third link
Length W3 calculation formula update the third linkage length W3, and continue to navigate by step D32；
Step D37 constantly repeats step D33 to step D36, until user travels to destination node Q.
Preferably, topological map production method is in the step A：
Step A1 obtains the grating map of required navigation area and extracts real road；
Step A2 sets the fork on the road in the grating map on all real roads to the node of topological map；
Step A3 sets all special places in the grating map to the node of topological map；
Step A4 generates step A2 and step A3 according to the formal or unofficial real road in the grating map
Multiple nodes be connected, calculate and store the distance of real road between two neighboring node；
The directional arrow of every optional road in the node is arranged on each node of topological map in step A5.
Preferably, the navigation path planning mode includes：Automatic planning shortest path mode, specified orderly necessary point are certainly
Dynamic planning shortest path mode specifies unordered necessary point to plan shortest path mode, Euler's circuit path fashion automatically and make by oneself
Adopted path fashion.
Preferably, the automatic planning shortest path mode is：
First, start node P and destination node Q are marked in the topological map；
Then, the shortest path by start node P to destination node Q is found on the topological map using A* searching algorithms
Diameter；And searched out shortest path is shown on the topological map；
The shortest path found on the topological map using A* searching algorithms by start node P to destination node Q
Diameter is：
Using A* searching algorithms on the topological map, found first by start node P to first Dominator
Then most short branch path finds the most short branch path by first Dominator to next Dominator, according to the method described above
The most short branch path between other Dominators is sequentially found, until finding by the last one Dominator to destination node most
Short branch path, after above-mentioned all most short branch paths head and the tail are spliced, obtaining must by start node P processes on the topological map
The shortest path of destination node Q is reached after node.
Preferably, the specified orderly necessary point plans that shortest path mode is automatically：
Start node P, destination node Q and Dominator are marked in the topological map, and specified first to Dominator
After reach order；
Using A* searching algorithms on the topological map, found first by start node P to first Dominator
Then most short branch path finds the most short branch path by first Dominator to next Dominator, according to the method described above
The most short branch path between other Dominators is sequentially found, until finding by the last one Dominator to destination node most
Short branch path, after above-mentioned all most short branch paths head and the tail are spliced, obtaining must by start node P processes on the topological map
The shortest path of destination node Q is reached after node, and searched out shortest path is shown on topological map.
Preferably, described that unordered necessary point is specified to plan that shortest path mode is automatically：
First, start node P, destination node Q and Dominator are marked in the topological map, utilizes A* searching algorithms
It is found on the topological map by the most short branch path of start node P to each Dominator, each Dominator to target
Most short branch path between the most short branch path and any two Dominator of node Q, and calculate these most short branch path institutes
Corresponding actual distance, to generate most short branch path table between two nodes；
Then, a topology diagram being made of start node P, destination node Q and all Dominators is generated, it will be upper
The actual distance corresponding to most short branch path is stated as between two nodes corresponding to each most short branch path on the topology diagram
Distance；
Then, it is found by start node P only once by all necessary using ant group algorithm on the topology diagram
The Dominator corresponding to the shortest path of destination node Q is reached after node reaches order；
Finally, order is reached according to the Dominator, successively from finding section in most short branch path table between two node
Corresponding most short branch path and splice its head and the tail between point, to obtain on the topological map by start node P by
User specifies the shortest path of the unordered arrival destination node Q after Dominator, and shows and sought on the topological map
The shortest path found.
Preferably, the Euler's circuit path fashion is：
The Euler's circuit path fashion is：
Start node P is marked in the topological map, judges whether the topological map is Euler diagram：
If an Euler's circuit is then found on the topological map using End-pairing algorithms, and in the topology
Searched out Euler's circuit is shown on map；
If not then determining that the optimal of the topological map adds side using MINIMUM WEIGHT perfect matching algorithm combination Floyd algorithms
(need to pass through real road twice), the topological map is made to be converted into Euler diagram；Then utilize End-pairing algorithms at this
An Euler's circuit is found on topological map, and searched out Euler's circuit is shown on the topological map；
Self-defined path fashion is：
User is demarcated on the topological map by the self-defined path of start node P to destination node Q, described self-defined
Path is that Dominator, the successively connection arrival order and Dominator specified between Dominator is arranged in User Defined
Path.
The low signal areas intelligent navigation method based on topological map, with obtaining the grid of required navigation area in advance
Scheme and be translated into topological map, without passing through network continuous updating cartographic information when to navigate, and topological map is only
It shows the path between node and node, to which cartographic information is more simplified, improves the processing speed and picture display rate of data,
Realize that the real-time map of null zones is shown.
By recording each real time running parameter of user, calculating has walked ratio to know the current location of user, in fact
The positioning of present null zones, makes user that can also be clear from itself position in null zones.Moreover, often passing through one
Section link just updates user's driving parameters so that and required parameter is respectively calculated in the mobile terminal has more real-time, from
And improve the positioning accuracy that user current location is shown on the topological map of required navigation area；In addition, starting in navigation
In the stage, user is familiar with itself practical position, not high to the positioning accuracy request of current location, can use more
Coarse user's driving parameters carry out current location positioning to user, and user current location backward is positioned as according to the preceding paragraph chain
Road user's actual travel parameter is adjusted to respectively calculating required parameter in the mobile terminal, and the parameter through constantly adjusting in real time
It is whole, will make user current location positioning persistently keep higher precision, to meet user after navigation the stage due to reach footpath between fields
Raw environment and to the higher demand of positioning accuracy request.
Description of the drawings
The present invention will be further described for attached drawing, but the content in attached drawing does not constitute any limitation of the invention.
Fig. 1 is that the grating map of the one of embodiment of the present invention is converted into the structure chart of topological map；
Fig. 2 is the node distribution map of the topological map of the one of embodiment of the present invention；
Directional arrow display figure when Fig. 3 is the navigation of the one of embodiment of the present invention.
Wherein：Node P1, P2, P3, P4, P5, P6；Path L；Arrow T1, T2, T3, T4.
Specific implementation mode
Technical solution to further illustrate the present invention below with reference to the accompanying drawings and specific embodiments.
Embodiment one
The low signal areas intelligent navigation method based on topological map of the present embodiment, includes the following steps：
Step A, the grating map of navigation area needed for acquisition for mobile terminal are simultaneously translated into topological map, such as Fig. 1, figure
Shown in 2；
Step B, user mark start node P and destination node Q in the topological map；
Step C selects navigation path planning mode in mobile terminal, generates corresponding best guidance path；
Step D, user input driving parameters to the mobile terminal, and the mobile terminal is according to driving parameters and navigation road
Diameter planning mode is that user navigates to destination node Q.
Preferably,
The step D includes：
" driving " navigation pattern：
Step D11, user input driving parameters to the mobile terminal：Drive average speed per hour N1；
The mobile terminal shows the best guidance path of beginning node P to destination node Q on the topological map
K, by start node P to next node M on the best guidance path K1Link K1Practical section distance to be recorded as first real
Border section distance S, and the first practical section distance S is converted into the first linkage length W1, conversion formula is as follows：
That is the first linkage length W1 of link is that user covers the required of the practical section distance representated by the link
Drive time；
Step D12, user start to set out, and the mobile terminal is to record node the time constantly to set out, and record user is real
When drive time t1 (down time is not counted in the real-time drive time t1 of the user)；According to the real-time drive time t1 of the user
The first walking ratio p1 is generated, i.e.,
According to the first walking ratio p1 calculation formula and the real-time drive time t1 of the user, at interval of 1 second to institute
It is primary to state the first walking ratio p1 updates, and in current ink K1The current location of upper calibration user；
Step D13, when the first walking ratio p1 reaches 95%, the topological map will show the present bit of user
It is set in node M1On, and show node M on the topological map1To the direction arrow of each adjacent node that can directly reach
Head；
Step D14, user reach node M on topological map1Corresponding fork crossing, stop move ahead, according to it is described most
Good guidance path K or the selection of itself wish move on direction, click node M on the mobile terminal1The continuation of upper correspondence
The directional arrow of direction of advance simultaneously confirms；If user does not move on direction by the best guidance path K selections herein,
Start node P is then updated to node M1, and the C that gos to step starts to execute；
Step D15, the mobile terminal will confirm that records node at the time of the directional arrow as the time, reads at this time
The real-time drive time t1 of the user be recorded as the first running time t1', the clearing user described in new record that lays equal stress on drives in real time
Time t1, calculating difference E 1, and judge whether the difference E 1 is more than given threshold e1, wherein
Difference E1=| first the first linkage lengths of running time t1'- W1 |；
If E1>The average speed per hour N1 that drives then is updated to the average speed per hour N1' that actually drives by e1, wherein
Step D16 finds node M according to the directional arrow that user is confirmed in the mobile terminal1To next section
Point M2Link K2, the first practical section distance S is updated to link K2Practical section distance, while press above-mentioned first link
Length W1 calculation formula update the first linkage length W1, and continue to navigate by step D12；
Step D17 constantly repeats step D13 to step D16, until user travels to destination node Q.
The low signal areas intelligent navigation method based on topological map, with obtaining the grid of required navigation area in advance
Scheme and be translated into topological map, without passing through network continuous updating cartographic information when to navigate, and topological map is only
It shows the path between node and node, to which cartographic information is more simplified, improves the processing speed and picture display rate of data,
Realize that the real-time map of null zones is shown.
Under " driving " navigation pattern, by recording the real-time drive time t1 of the user, and described first is calculated in real time
Walking ratio p1 realizes the positioning of null zones, makes user in null zones to know the real-time current location of user
Also itself position can be clear from.Moreover, often reach one section of new link just update described in drive average speed per hour N1 so that
Required parameter is respectively calculated in the mobile terminal and has more real-time, to improve on the topological map of required navigation area
Show the positioning accuracy of user current location；In addition, in the navigation incipient stage, user is more ripe to itself practical position
Know, it is not high to the positioning accuracy request of current location, can use it is more coarse it is described drive average speed per hour N1 to user into
Trade front position positions, and user current location backward is positioned as according to t1 pairs of user's real-time drive time described in the preceding paragraph link
Such as described average speed per hour N1 and the first walking ratio p1 that drives of required parameter is respectively calculated in the mobile terminal to be adjusted
Whole, which will make user current location positioning persistently keep higher precision, to meet user through constantly adjustment in real time
The stage is due to reaching foreign environment and to the higher demand of positioning accuracy request after navigation.
Preferably, the step D further includes：
" walking " navigation pattern：
Step D21, user input driving parameters to the mobile terminal：User's height H (cm)；The mobile terminal calculates
User step-length N2, calculation formula are as follows：
User's step-length N2=0.45 × user's height H；
The mobile terminal shows the best guidance path of beginning node P to destination node Q on the topological map
K, by start node P to next node M on the best guidance path K1Link K1Practical section distance to be recorded as first real
Border section distance S, and the first practical section distance S is converted into the second linkage length W2, conversion formula is as follows：
That is the second linkage length W2 of link is that user covers the step number needed for the practical section representated by the link；
Step D22, user start to set out, and the mobile terminal is to record node the time constantly to set out, and record user is real
When step number t2；The second walking ratio p2 is generated according to the real-time step number t2 of the user, i.e.,
According to the second walking ratio p2 calculation formula and the real-time step number t2 of user, at interval of 1 second to second row
It is primary to walk ratio p2 updates, and in current ink K1The current location of upper calibration user；
Step D23, when the second walking ratio p2 reaches 95%, the topological map will show the present bit of user
It is set in node M1On, and show node M on the topological map1To the direction arrow of each adjacent node that can directly reach
Head；
Step D24, user reach node M on topological map1Corresponding fork crossing, stop move ahead, according to it is described most
Good guidance path K or the selection of itself wish move on direction, click node M on the mobile terminal1The continuation of upper correspondence
The directional arrow of direction of advance simultaneously confirms；If user does not move on direction by the best guidance path K selections herein,
Start node P is then updated to node M1, and the C that gos to step starts to execute；
Step D25, the mobile terminal will confirm that records node at the time of the directional arrow as the time, reads at this time
The real-time step number t2 of the user be recorded as the first row and walk step number t2', clearing is laid equal stress on the real-time step number t2 of user described in new record, meter
Difference E2 is calculated, and judges whether the difference E2 is more than given threshold e2, wherein
Difference E2=| the first row walks the second linkage lengths of step number t2'- W2 |；
If E2>User's step-length N2 is then updated to actual user step-length N2' by e2, wherein
Step D26 finds node M according to the directional arrow that user is confirmed in the mobile terminal1To next section
Point M2Link K2, the first practical section distance S is updated to link K2Practical section distance, while press above-mentioned second link
Length W2 calculation formula update the second linkage length W2, and continue to navigate by step D22；
Step D27 constantly repeats step D23 to step D26, until user travels to destination node Q.
Under " walking " navigation pattern, by recording the real-time step number t2 of the user, and second walking is calculated in real time
Ratio p2 realizes the positioning of null zones, user is made also in null zones to know the real-time current location of user
It is clear from itself position.Moreover, often reaching one section of new link just updates user's step-length N2 so that the movement
Required parameter is respectively calculated in terminal and has more real-time, and user is shown on the topological map of required navigation area to improve
The positioning accuracy of current location；In addition, in the navigation incipient stage, user is familiar with itself practical position, to current
The positioning accuracy request of position is not high, more coarse user's step-length N2 can be used to carry out current location to user fixed
Position, it is possible to be estimated to obtain according to user's height, user current location backward is positioned as according to the preceding paragraph link institute
The real-time step number t2 of user is stated to respectively calculating for example described user's step-length N2 of required parameter and second row in the mobile terminal
It walks ratio p2 to be adjusted, which will make user current location positioning persistently keep higher essence through constantly adjustment in real time
Degree, to meet user after navigation the stage due to reach foreign environment and to the higher demand of positioning accuracy request.
Preferably, the step D further includes：
" riding " navigation pattern：
Step D31, user input driving parameters to the mobile terminal：Ride average speed per hour N3；
The mobile terminal shows the best guidance path of beginning node P to destination node Q on the topological map
K, by start node P to next node M on the best guidance path K1Link K1Practical section distance to be recorded as first real
Border section distance S, and the first practical section distance S is converted into third linkage length W3, conversion formula is as follows：
That is the third linkage length W3 of link is that user covers the required of the practical section distance representated by the link
It rides the time；
Step D32, user start to set out, and the mobile terminal is to record node the time constantly to set out, and record user is real
When ride time t3 (down time be not counted in the user ride in real time time t3)；It is ridden in real time time t3 according to the user
Third walking ratio p3 is generated, i.e.,
It is ridden in real time time t3 according to walk ratio p3 calculation formula and the user of the third, at interval of 1 second to institute
It is primary to state third walking ratio p3 updates, and in current ink K1The current location of upper calibration user；
Step D33, when third walking ratio p3 reaches 95%, the topological map will show the present bit of user
It is set in node M1On, and show node M on the topological map1To the direction arrow of each adjacent node that can directly reach
Head；If user does not move on direction by the best guidance path K selections herein, start node P is updated to node M1,
And the C that gos to step starts to execute；
Step D34, user reach node M on topological map1Corresponding fork crossing, stop move ahead, according to it is described most
Good guidance path K or the selection of itself wish move on direction, click node M on the mobile terminal1The continuation of upper correspondence
The directional arrow of direction of advance simultaneously confirms；
Step D35, the mobile terminal will confirm that records node at the time of the directional arrow as the time, reads at this time
The user time t3 that rides in real time be recorded as first and ride time t3', the clearing user described in new record that lays equal stress on rides in real time
Time t3, calculating difference E3, and judge whether the difference E 3 is more than given threshold e3, wherein
Difference E3=| first rides time t3'- third linkage length W3 |；
If E3>The average speed per hour N3 that rides then is updated to the average speed per hour N3' that actually rides by e3, wherein
Step D36 finds node M according to the directional arrow that user is confirmed in the mobile terminal1To next section
Point M2Link K2, the first practical section distance S is updated to link K2Practical section distance, while press above-mentioned third link
Length W3 calculation formula update the third linkage length W3, and continue to navigate by step D32；
Step D37 constantly repeats step D33 to step D36, until user travels to destination node Q.
Under " riding " navigation pattern, ridden in real time time t3 by recording the user, and calculate the third in real time
Walking ratio p3 realizes the positioning of null zones, makes user in null zones to know the real-time current location of user
Also itself position can be clear from.Moreover, often reach one section of new link just update described in ride average speed per hour N3 so that
Required parameter is respectively calculated in the mobile terminal and has more real-time, to improve on the topological map of required navigation area
Show the positioning accuracy of user current location；In addition, in the navigation incipient stage, user is more ripe to itself practical position
Know, it is not high to the positioning accuracy request of current location, can use it is more coarse it is described ride average speed per hour N3 to user into
Trade front position positions, and user current location backward is positioned as being ridden in real time t3 pairs of time according to user described in the preceding paragraph link
Such as described average speed per hour N3 and third walking ratio p3 that rides of required parameter is respectively calculated in the mobile terminal to be adjusted
Whole, which will make user current location positioning persistently keep higher precision, to meet user through constantly adjustment in real time
The stage is due to reaching foreign environment and to the higher demand of positioning accuracy request after navigation.
Preferably, topological map production method is in the step A：
Step A1 obtains the grating map of required navigation area and extracts real road；
Step A2 sets the fork on the road in the grating map on all real roads to the node of topological map；
Step A3 sets all special places in the grating map to the node of topological map；
Step A4 generates step A2 and step A3 according to the formal or unofficial real road in the grating map
Multiple nodes be connected, calculate and store the distance of real road between two neighboring node；
The directional arrow of every optional road in the node is arranged on each node of topological map in step A5.
The topological map production method obtains the grating map of required navigation area and extracts practical road before navigation
Road, by the node of the equal translation bit topological map in fork on the road, special place in the grating map；And it calculates and stores phase
The distance of real road between adjacent two nodes, in order to obtain the practical section distance of link in navigation.Moreover, each node
On every optional road be set to point to arrow, user can select the next section that need to be reached according to practical road conditions when in order to navigate
Point improves flexibility and the adaptability of navigation.The special place refers to sight spot, gas station, lavatory etc..
Preferably, the navigation path planning mode includes：Automatic planning shortest path mode, specified orderly necessary point are certainly
Dynamic planning shortest path mode specifies unordered necessary point to plan shortest path mode, Euler's circuit path fashion automatically and make by oneself
Adopted path fashion.User can select different navigation path planning modes according to actual demand, to meet different navigation needs
The changeable road conditions with adaptation.
Preferably, the automatic planning shortest path mode is：
First, start node P and destination node Q are marked in the topological map；
Then, the shortest path by start node P to destination node Q is found on the topological map using A* searching algorithms
Diameter；And searched out shortest path is shown on the topological map；
The shortest path found on the topological map using A* searching algorithms by start node P to destination node Q
Diameter is：
Using A* searching algorithms on the topological map, found first by start node P to first Dominator
Then most short branch path finds the most short branch path by first Dominator to next Dominator, according to the method described above
The most short branch path between other Dominators is sequentially found, until finding by the last one Dominator to destination node most
Short branch path, after above-mentioned all most short branch paths head and the tail are spliced, obtaining must by start node P processes on the topological map
The shortest path of destination node Q is reached after node.
When user selects the automatic planning shortest path mode, user only specifies start node P and destination node
Q finds the shortest path to destination node Q by start node P, is suitable for using A* searching algorithms on the topological map
The case where destination node Q need to be only navigated to by start node P.The A* searching algorithms are to solve shortest path in a kind of static road network
The most effective direct search method of diameter, using found out on the path of multiple nodes it is minimum by cost as target.
Preferably, the specified orderly necessary point plans that shortest path mode is automatically：
Start node P, destination node Q and Dominator are marked in the topological map, and specified first to Dominator
After reach order；
Using A* searching algorithms on the topological map, found first by start node P to first Dominator
Then most short branch path finds the most short branch path by first Dominator to next Dominator, according to the method described above
The most short branch path between other Dominators is sequentially found, until finding by the last one Dominator to destination node most
Short branch path, after above-mentioned all most short branch paths head and the tail are spliced, obtaining must by start node P processes on the topological map
The shortest path of destination node Q is reached after node, and searched out shortest path is shown on topological map.
When user's selection specified orderly necessary point plans shortest path mode automatically, user can refer to Dominator
It is fixed successively to reach order, then the mobile terminal combination A* searching algorithms found on topological map by start node P by with
The specified sequence in family reaches the shortest path of destination node Q after Dominator, can be used for such as that orienteering needs are in order
The case where by multiple places.
Preferably, described that unordered necessary point is specified to plan that shortest path mode is automatically：
First, start node P, destination node Q and Dominator are marked in the topological map, utilizes A* searching algorithms
It is found on the topological map by the most short branch path of start node P to each Dominator, each Dominator to target
Most short branch path between the most short branch path and any two Dominator of node Q, and calculate these most short branch path institutes
Corresponding actual distance, to generate most short branch path table between two nodes；
Then, a topology diagram being made of start node P, destination node Q and all Dominators is generated, it will be upper
The actual distance corresponding to most short branch path is stated as between two nodes corresponding to each most short branch path on the topology diagram
Distance；
Then, it is found by start node P only once by all necessary using ant group algorithm on the topology diagram
The Dominator corresponding to the shortest path of destination node Q is reached after node reaches order；
Finally, order is reached according to the Dominator, successively from finding section in most short branch path table between two node
Corresponding most short branch path and splice its head and the tail between point, to obtain on the topological map by start node P by
User specifies the shortest path of the unordered arrival destination node Q after Dominator, and shows and sought on the topological map
The shortest path found.
When user's selection is described, and unordered necessary point is specified to plan shortest path mode automatically, user only specifies starting section
Point P, destination node Q and Dominator, there is no specified Dominators to reach order, then the mobile terminal passes through ant group algorithm
Find only once reached after all Dominators by start node P it is necessary corresponding to the shortest path of destination node Q
Node reaches order, recycle above-mentioned specified orderly necessary point plan automatically the finding method of shortest path find out it is specified it is unordered must
Through putting automatic planning shortest path, can be used for before reaching destination node Q needing by other necessary places, but to by sequence
The case where not requiring.
Preferably, the Euler's circuit path fashion is：
The Euler's circuit path fashion is：
Start node P is marked in the topological map, judges whether the topological map is Euler diagram：
If an Euler's circuit is then found on the topological map using End-pairing algorithms, and in the topology
Searched out Euler's circuit is shown on map；
If not then determining that the optimal of the topological map adds side using MINIMUM WEIGHT perfect matching algorithm combination Floyd algorithms
(need to pass through real road twice), the topological map is made to be converted into Euler diagram；Then utilize End-pairing algorithms at this
An Euler's circuit is found on topological map, and searched out Euler's circuit is shown on the topological map.
When user select the Euler's circuit path fashion when, only specify start node P, can be used for start node P and
The case where destination node Q is the same place.If the topological map is Euler diagram, the Euler's circuit is from start node P
Set out it is primary by each of the links on topological map and only once after return to the path of start node P；If the topological map is not
It is Euler diagram, from start node P on topological map, other all links pass through other than a few links pass through twice
Cross primary and only once return to start node P afterwards, it is all meet the path of above-mentioned condition in shortest path.
Preferably, self-defined path fashion is：
User demarcates the self-defined path by start node to destination node, the self-defined road on the topological map
Diameter is that Dominator, the successively link road arrival order and Dominator specified between Dominator is arranged in User Defined
Diameter.When user selects self-defined path fashion, user can voluntarily plan navigation routine according to self-demand on topological map,
Improve the flexibility of navigation.
Embodiment two
The low signal areas intelligent navigation method based on topological map of the present embodiment, includes the following steps：
S10：The grating map of navigation area needed for acquisition for mobile terminal is simultaneously translated into topological map.
S20：User marks start node P (i.e. current location) and destination node Q (i.e. purposes in the topological map
Ground).
S30：Navigation path planning mode is selected in mobile terminal.
S40：User inputs driving parameters to the mobile terminal, and the mobile terminal is according to driving parameters and guidance path
Planning mode is that user navigates to destination node Q.
As shown in figure 3, node P1 be start node P, node P4 be destination node Q, select navigation path planning mode for
Automatic planning shortest path, path L are the optimal path according to navigation path planning mode from the node P1 to node P4, i.e.,
From node P1, successively passes through node P2 and node P3, eventually arrive at node P4；
Under " walking " navigation pattern, for navigating to node P2 from node P1：
S41：User is user's height H (cm) to mobile terminal input driving parameters, and the mobile terminal, which calculates, to be used
Family step-length N2, the mobile terminal show paths L on the topological map, by node P1 on the L of path to the link of node P2
The practical section distance of P1P2 is recorded as the first practical section distance S, and the first practical section distance S is converted into the second link
Length W2；
S42：User starts to set out, and the mobile terminal is to record node the time constantly to set out, and record user walks in real time
Number t2；The second walking ratio p2 is generated according to the real-time step number t2 of the user, according to the second walking ratio p2 calculation formula
And the real-time step number t2 of user, it is primary to the second walking ratio p2 updates at interval of 1 second, and demarcated on current ink P1P2
The current location of user；
S43：When the second walking ratio p2 reaches 95%, the topological map will show that the current location of user is
On node P2, and show on the topological map node P2 to each adjacent node that can directly reach directional arrow,
The directional arrow of adjacent node is that node P2 is directed toward the arrow T1 of node P1, node P2 is directed toward the arrow T2 of node P3, section herein
Point P2 is directed toward the arrow T4 of the arrow T3 and node P2 direction nodes P6 of node P5；
S44：User reaches the fork crossing corresponding to node P2 on topological map, stops moving ahead, (next according to path L
Destination node is P3) or the selection of itself wish move on direction, click on the mobile terminal it is corresponding on node P2 should be after
The directional arrow of continuous direction of advance simultaneously confirms；If L instructions selection arrow T2 is not moved on user by path herein, will
Start node P is updated to node P2 by original P1, and the S30 that gos to step starts to execute；
S45：Node is recorded as the time at the time of mobile terminal will confirm that directional arrow T2, reads at this time described
The real-time step number t2 of user is recorded as the first row and walks step number t2', resets the real-time step number t2 of user described in new record that lays equal stress on, calculating difference
E2, and judge whether the difference E2 is more than given threshold e2, if E2>User's step-length N2 is then updated to practical use by e2
Family step-length N2'；
S46：According to the directional arrow T2 that user is confirmed in the mobile terminal, node P2 is found to next node
First practical section distance S is updated to the practical section distance of link P2P3, while pressing above-mentioned second chain by the link P2P3 of P3
Road length W2 calculation formula update the second linkage length W2, and continue to navigate by step S42；
S47：Step S43 to step S46 constantly is repeated, until user travels to destination node P4.
The technical principle of the present invention is described above in association with specific embodiment.These descriptions are intended merely to explain the present invention's
Principle, and it cannot be construed to limiting the scope of the invention in any way.Based on the explanation herein, the technology of this field
Personnel would not require any inventive effort the other specific implementation modes that can associate the present invention, these modes are fallen within
Within protection scope of the present invention.
Claims (9)
1. a kind of low signal areas intelligent navigation method based on topological map, which is characterized in that include the following steps：
Step A, the grating map of navigation area needed for acquisition for mobile terminal are simultaneously translated into topological map；
Step B, user mark start node P and destination node Q in the topological map；
Step C selects navigation path planning mode in mobile terminal, generates corresponding best guidance path；
Step D, user input driving parameters to the mobile terminal, and the mobile terminal is advised according to driving parameters and guidance path
The mode of drawing is that user navigates to destination node Q；
The step D includes：
" driving " navigation pattern：
Step D11, user input driving parameters to the mobile terminal：Drive average speed per hour N1；
The mobile terminal shows the best guidance path K of beginning node P to destination node Q on the topological map, will
Start node P to next node M on the best guidance path K1Link K1Practical section distance be recorded as the first practical road
Duan Lucheng S, and the first practical section distance S is converted into the first linkage length W1, conversion formula is as follows：
That is the first linkage length W1 of link covers the required of the practical section distance representated by the link for user and drives
Time；
Step D12, user start to set out, and the mobile terminal is to record node the time constantly to set out, and record user drives in real time
Vehicle time t1, down time are not counted in the real-time drive time t1 of the user；It is generated according to the real-time drive time t1 of the user
First walking ratio p1, i.e.,
It walks ratio p1 calculation formula and the real-time drive time t1 of the user according to described first, at interval of 1 second to described the
One walking ratio p1 updates are primary, and in current ink K1The current location of upper calibration user；
Step D13, when the first walking ratio p1 reaches 95%, the topological map will show that the current location of user is
In node M1On, and show node M on the topological map1To the directional arrow of each adjacent node that can directly reach；
Step D14, user reach node M on topological map1Corresponding fork crossing stops moving ahead, according to the best navigation
Path K or the selection of itself wish move on direction, click node M on the mobile terminal1Upper correspondence side of moving on
To the directional arrow and confirm；If user does not move on direction by the best guidance path K selections herein, will rise
Beginning, node P was updated to node M1, and the C that gos to step starts to execute；
Step D15, the mobile terminal will confirm that records node at the time of the directional arrow as the time, reads institute at this time
It states the real-time drive time t1 of user and is recorded as the first running time t1', reset the real-time drive time of user described in new record of laying equal stress on
T1, calculating difference E1, and judge whether the difference E1 is more than given threshold e1, wherein
Difference E1=| first the first linkage lengths of running time t1'- W1 |；
If E1>The average speed per hour N1 that drives then is updated to the average speed per hour N1' that actually drives by e1, wherein
Step D16 finds node M according to the directional arrow that user is confirmed in the mobile terminal1To next node M2
Link K2, the first practical section distance S is updated to link K2Practical section distance, while press above-mentioned first linkage length
W1 calculation formula update the first linkage length W1, and continue to navigate by step D12；
Step D17 constantly repeats step D13 to step D16, until user travels to destination node Q.
2. the low signal areas intelligent navigation method according to claim 1 based on topological map, which is characterized in that described
Step D further includes：
" walking " navigation pattern：
Step D21, user input driving parameters to the mobile terminal：User's height H (cm)；The mobile terminal calculates user
Step-length N2, calculation formula are as follows：
User's step-length N2=0.45 × user's height H；
The mobile terminal shows the best guidance path K of beginning node P to destination node Q on the topological map, will
Start node P to next node M on the best guidance path K1Link K1Practical section distance be recorded as the first practical road
Duan Lucheng S, and the first practical section distance S is converted into the second linkage length W2, conversion formula is as follows：
That is the second linkage length W2 of link is that user covers the step number needed for the practical section representated by the link；
Step D22, user start to set out, and the mobile terminal is to record node the time constantly to set out, and record user walks in real time
Number t2；The second walking ratio p2 is generated according to the real-time step number t2 of the user, i.e.,
According to the second walking ratio p2 calculation formula and the real-time step number t2 of user, at interval of 1 second to the second walking ratio
Example p2 updates are primary, and in current ink K1The current location of upper calibration user；
Step D23, when the second walking ratio p2 reaches 95%, the topological map will show that the current location of user is
In node M1On, and show node M on the topological map1To the directional arrow of each adjacent node that can directly reach；
Step D24, user reach node M on topological map1Corresponding fork crossing stops moving ahead, according to the best navigation
Path K or the selection of itself wish move on direction, click node M on the mobile terminal1Upper correspondence side of moving on
To the directional arrow and confirm；If user does not move on direction by the best guidance path K selections herein, will rise
Beginning, node P was updated to node M1, and the C that gos to step starts to execute；
Step D25, the mobile terminal will confirm that records node at the time of the directional arrow as the time, reads institute at this time
It states the real-time step number t2 of user and is recorded as the first row and walk step number t2 ', clearing is laid equal stress on the real-time step number t2 of user described in new record, and it is poor to calculate
Value E2, and judge whether the difference E2 is more than given threshold e2, wherein
Difference E2=| the first row walks the second linkage lengths of step number t2'- W2 |；
If E2>User's step-length N2 is then updated to actual user step-length N2' by e2, wherein
Step D26 finds node M according to the directional arrow that user is confirmed in the mobile terminal1To next node M2
Link K2, the first practical section distance S is updated to link K2Practical section distance, while press above-mentioned second linkage length
W2 calculation formula update the second linkage length W2, and continue to navigate by step D22；
Step D27 constantly repeats step D23 to step D26, until user travels to destination node Q.
3. the low signal areas intelligent navigation method according to claim 1 based on topological map, which is characterized in that described
Step D further includes：
" riding " navigation pattern：
Step D31, user input driving parameters to the mobile terminal：Ride average speed per hour N3；
The mobile terminal shows the best guidance path K of beginning node P to destination node Q on the topological map, will
Start node P to next node M on the best guidance path K1Link K1Practical section distance be recorded as the first practical road
Duan Lucheng S, and the first practical section distance S is converted into third linkage length W3, conversion formula is as follows：
That is the third linkage length W3 of link covers the required of the practical section distance representated by the link for user and rides
Time；
Step D32, user start to set out, and the mobile terminal is to record node the time constantly to set out, and record user rides in real time
Row time t3, down time are not counted in the user and ride in real time time t3；According to the user ride in real time time t3 generate
Third walking ratio p3, i.e.,
It is ridden in real time time t3 according to walk ratio p3 calculation formula and the user of the third, at interval of 1 second to described the
Three walking ratio p3 updates are primary, and in current ink K1The current location of upper calibration user；
Step D33, when third walking ratio p3 reaches 95%, the topological map will show that the current location of user is
In node M1On, and show node M on the topological map1To the directional arrow of each adjacent node that can directly reach；If
User does not move on direction by the best guidance path K selections herein, then start node P is updated to node M1, and jump
Step C is gone to start to execute；
Step D34, user reach node M on topological map1Corresponding fork crossing stops moving ahead, according to the best navigation
Path K or the selection of itself wish move on direction, click node M on the mobile terminal1Upper correspondence side of moving on
To the directional arrow and confirm；
Step D35, the mobile terminal will confirm that records node at the time of the directional arrow as the time, reads institute at this time
It states the user time t3 that rides in real time to be recorded as first and ride time t3', the clearing user described in new record that lays equal stress on rides the time in real time
T3, calculating difference E3, and judge whether the difference E3 is more than given threshold e3, wherein
Difference E3=| first rides time t3'- third linkage length W3 |；
If E3>The average speed per hour N3 that rides then is updated to the average speed per hour N3' that actually rides by e3, wherein
Step D36 finds node M according to the directional arrow that user is confirmed in the mobile terminal1To next node M2
Link K2, the first practical section distance S is updated to link K2Practical section distance, while press above-mentioned third linkage length
W3 calculation formula update the third linkage length W3, and continue to navigate by step D32；
Step D37 constantly repeats step D33 to step D36, until user travels to destination node Q.
4. the low signal areas intelligent navigation method according to claim 1 based on topological map, which is characterized in that described
Topological map production method is in step A：
Step A1 obtains the grating map of required navigation area and extracts real road；
Step A2 sets the fork on the road in the grating map on all real roads to the node of topological map；
Step A3 sets all special places in the grating map to the node of topological map；
Step A4 generates step A2 and step A3 more according to the formal or unofficial real road in the grating map
A node is connected, and calculates and store the distance of real road between two neighboring node；
The directional arrow of every optional road in the node is arranged on each node of topological map in step A5.
5. the low signal areas intelligent navigation method according to claim 1 based on topological map, it is characterised in that：It is described
Navigation path planning mode includes：Automatic planning shortest path mode, specified orderly necessary point plan automatically shortest path mode,
Unordered necessary point is specified to plan shortest path mode, Euler's circuit path fashion and self-defined path fashion automatically.
6. the low signal areas intelligent navigation method according to claim 5 based on topological map, which is characterized in that described
It is automatic to plan that shortest path mode is：
First, start node P and destination node Q are marked in the topological map；
Then, the shortest path by start node P to destination node Q is found on the topological map using A* searching algorithms；
And searched out shortest path is shown on the topological map；
Described found on the topological map using A* searching algorithms be by the shortest path of start node P to destination node Q：
Using A* searching algorithms on the topological map, found first by the most short of start node P to first Dominator
Then branch path finds the most short branch path by first Dominator to next Dominator, according to the method described above successively
The most short branch path between other Dominators is found, until finding the most short branch by the last one Dominator to destination node
Path obtains passing through necessary section by start node P on the topological map after splicing above-mentioned all most short branch path head and the tail
The shortest path of destination node Q is reached after point.
7. the low signal areas intelligent navigation method according to claim 5 based on topological map, which is characterized in that described
Specified orderly necessary point plans that shortest path mode is automatically：
Start node P, destination node Q and Dominator are marked in the topological map, and is successively arrived to Dominator is specified
Up to order；
Using A* searching algorithms on the topological map, found first by the most short of start node P to first Dominator
Then branch path finds the most short branch path by first Dominator to next Dominator, according to the method described above successively
The most short branch path between other Dominators is found, until finding the most short branch by the last one Dominator to destination node
Path obtains passing through necessary section by start node P on the topological map after splicing above-mentioned all most short branch path head and the tail
The shortest path of destination node Q is reached after point, and searched out shortest path is shown on topological map.
8. the low signal areas intelligent navigation method according to claim 6 based on topological map, which is characterized in that described
Unordered necessary point is specified to plan that shortest path mode is automatically：
First, start node P, destination node Q and Dominator are marked in the topological map, using A* searching algorithms in institute
It states and finds most short branch path by start node P to each Dominator, each Dominator to destination node Q on topological map
Most short branch path and any two Dominator between most short branch path, and calculate corresponding to these most short branch paths
Actual distance, to generate two nodes between most short branch path table；
Then, generate a topology diagram being made of start node P, destination node Q and all Dominators, by it is above-mentioned most
Actual distance corresponding to short branch path as between two nodes corresponding to each most short branch path on the topology diagram away from
From；
Then, it is found using ant group algorithm on the topology diagram and all Dominators only once is passed through by start node P
The Dominator corresponding to the shortest path of destination node Q is reached afterwards reaches order；
Finally, order is reached according to the Dominator, successively from being found in most short branch path table between two node between node
Corresponding most short branch path simultaneously splice its head and the tail, to obtain on the topological map by start node P by user
The shortest path of the specified unordered arrival destination node Q after Dominator, and show and searched out on the topological map
Shortest path.
9. the low signal areas intelligent navigation method according to claim 5 based on topological map, which is characterized in that described
Euler's circuit path fashion is：
Start node P is marked in the topological map, judges whether the topological map is Euler diagram：
If an Euler's circuit is then found on the topological map using End-pairing algorithms, and in the topological map
The searched out Euler's circuit of upper display；
If not then determining that the optimal of the topological map adds side using MINIMUM WEIGHT perfect matching algorithm combination Floyd algorithms, that is, need
By real road twice, the topological map is made to be converted into Euler diagram；Then utilize End-pairing algorithms on topology ground
An Euler's circuit is found on figure, and searched out Euler's circuit is shown on the topological map；
Self-defined path fashion is：
User is demarcated on the topological map by the self-defined path of start node P to destination node Q, the self-defined path
For User Defined, Dominator, the successively connection path arrival order and Dominator specified between Dominator are set.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201710750686.XA CN107677269B (en) | 2017-08-28 | 2017-08-28 | A kind of low signal areas intelligent navigation method based on topological map |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201710750686.XA CN107677269B (en) | 2017-08-28 | 2017-08-28 | A kind of low signal areas intelligent navigation method based on topological map |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN107677269A CN107677269A (en) | 2018-02-09 |
| CN107677269B true CN107677269B (en) | 2018-08-14 |
Family
ID=61135016
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201710750686.XA Expired - Fee Related CN107677269B (en) | 2017-08-28 | 2017-08-28 | A kind of low signal areas intelligent navigation method based on topological map |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN107677269B (en) |
Families Citing this family (13)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN108628309B (en) * | 2018-04-26 | 2021-01-12 | 广东容祺智能科技有限公司 | Automatic addressing method for complex terrain |
| CN111998865B (en) | 2018-06-07 | 2022-06-21 | 北京嘀嘀无限科技发展有限公司 | System and method for path determination |
| CN109009887A (en) * | 2018-07-17 | 2018-12-18 | 东北大学 | A kind of man-machine interactive navigation system and method based on brain-computer interface |
| CN109347741B (en) * | 2018-08-01 | 2021-02-26 | 北京邮电大学 | Full-network path optimization traversal method and device based on in-band network telemetry technology |
| CN112789671B (en) * | 2018-10-01 | 2022-10-28 | 日产自动车株式会社 | Information processing system, information processing apparatus, and information processing method |
| CN110174108B (en) * | 2019-05-13 | 2021-01-01 | 杭州蓝芯科技有限公司 | Human-simulated Automatic Guided Vehicle (AGV) autonomous positioning navigation method based on topological map |
| CN110455295B (en) * | 2019-09-16 | 2023-05-30 | 广州电加软件有限责任公司 | Automatic planning method for river channel shipping route |
| CN111780762B (en) * | 2020-06-30 | 2022-04-22 | 杭州海康机器人技术有限公司 | Patrol path generation method and device and storage medium |
| CN111896021B (en) * | 2020-08-06 | 2022-06-10 | 南京审计大学 | Intelligent navigation method for signal-free road |
| CN114234988A (en) * | 2020-09-09 | 2022-03-25 | 华为技术有限公司 | Navigation method, equipment and system |
| CN113778073A (en) * | 2020-11-10 | 2021-12-10 | 北京京东乾石科技有限公司 | Robot running method, device and system applied to indoor scene |
| CN116972870B (en) * | 2023-09-21 | 2023-12-15 | 南京遇简信息科技有限公司 | Road navigation enhancement method, system and medium based on computer image recognition |
| CN117889866B (en) * | 2024-03-18 | 2024-06-11 | 深圳竹芒科技有限公司 | Navigation path planning method, device and storage medium |
Family Cites Families (10)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6553310B1 (en) * | 2000-11-14 | 2003-04-22 | Hewlett-Packard Company | Method of and apparatus for topologically based retrieval of information |
| CN101246013B (en) * | 2007-02-14 | 2012-05-23 | 高德软件有限公司 | Vehicle-mounted road navigation device |
| CN101694749B (en) * | 2009-08-25 | 2012-08-08 | 北京世纪高通科技有限公司 | Method and device for speculating routes |
| CN102110364B (en) * | 2009-12-28 | 2013-12-11 | 日电（中国）有限公司 | Traffic information processing method and traffic information processing device based on intersections and sections |
| CN103512581B (en) * | 2012-06-28 | 2016-12-21 | 北京搜狗科技发展有限公司 | A kind of paths planning method and device |
| CN102749084A (en) * | 2012-07-10 | 2012-10-24 | 南京邮电大学 | Path selecting method oriented to massive traffic information |
| CN105953785A (en) * | 2016-04-15 | 2016-09-21 | 青岛克路德机器人有限公司 | Map representation method for robot indoor autonomous navigation |
| CN106225788B (en) * | 2016-08-16 | 2019-04-19 | 上海理工大学 | The robot path planning method of ant group algorithm is expanded based on path |
| CN106323324B (en) * | 2016-11-25 | 2019-03-26 | 西安电子科技大学 | Quick shortest path planning method based on road chain |
| CN106931974B (en) * | 2017-03-29 | 2020-04-03 | 清华大学 | Method for calculating personal commuting distance based on mobile terminal GPS positioning data record |
-
2017
- 2017-08-28 CN CN201710750686.XA patent/CN107677269B/en not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| CN107677269A (en) | 2018-02-09 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN107677269B (en) | A kind of low signal areas intelligent navigation method based on topological map | |
| CN1821718B (en) | Determining a display position of road name data and displaying the road name data | |
| CN101275841B (en) | Feature information collecting apparatus and feature information collecting method | |
| US8213682B2 (en) | Feature information collecting apparatuses, methods, and programs | |
| EP2813816B1 (en) | Method for performing map matching in user terminal | |
| CN103186710B (en) | Optimum route search method and system | |
| CN106996783B (en) | Intelligent matching method and device for driving tracks and road network base map | |
| JP6303810B2 (en) | Vehicle position estimation apparatus and vehicle position estimation method | |
| CN113821029A (en) | Path planning method, device, equipment and storage medium | |
| CN103267526A (en) | Indoor navigation method and system | |
| JP2021120755A (en) | Map data structure and obstacle determination device | |
| CN110186457B (en) | Bluetooth indoor positioning navigation method based on high-precision electronic map | |
| CN109031382B (en) | High-precision road calculation matching method and system based on parking spaces | |
| CN110398965A (en) | It is a kind of based on have mark navigation map design AGV navigation scheduling method | |
| CN109523781A (en) | A kind of crossing prediction technique based on satellite positioning | |
| CN106323268A (en) | Mobile terminal positioning and travelling navigation method and mobile terminal | |
| CN105352506A (en) | Indoor road network planning method and apparatus | |
| CN105466442A (en) | Navigation method for dim starting point preset route | |
| CN111985715B (en) | Automatic navigation method and equipment based on corridor path of multi-target line | |
| JP2015194438A (en) | Map data structure, route search device, and route search method | |
| JP6528164B2 (en) | Positioning system | |
| JP2019158701A (en) | Feature point generating method | |
| JP2013050411A (en) | Vehicle itself position recognition system, vehicle itself position recognition program, and vehicle itself position recognition method | |
| CN110705751B (en) | Method for intelligently planning line path | |
| CN109540164B (en) | Path planning method, system and equipment |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant | ||
| CF01 | Termination of patent right due to non-payment of annual fee | ||
| CF01 | Termination of patent right due to non-payment of annual fee |
Granted publication date: 20180814 Termination date: 20200828 |