CN101608926B - Multi-level multi-modal route-finding navigation method - Google Patents
Multi-level multi-modal route-finding navigation method Download PDFInfo
- Publication number
- CN101608926B CN101608926B CN2009101122541A CN200910112254A CN101608926B CN 101608926 B CN101608926 B CN 101608926B CN 2009101122541 A CN2009101122541 A CN 2009101122541A CN 200910112254 A CN200910112254 A CN 200910112254A CN 101608926 B CN101608926 B CN 101608926B
- Authority
- CN
- China
- Prior art keywords
- runway
- crossing
- track
- file
- actual track
- 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
- 238000000034 method Methods 0.000 title claims abstract description 32
- 230000000007 visual effect Effects 0.000 claims description 20
- 238000012800 visualization Methods 0.000 claims description 10
- 238000012545 processing Methods 0.000 claims description 6
- 239000000284 extract Substances 0.000 claims description 5
- 230000003068 static effect Effects 0.000 claims description 3
- 230000006399 behavior Effects 0.000 description 9
- 238000004458 analytical method Methods 0.000 description 8
- 238000010586 diagram Methods 0.000 description 8
- 238000013499 data model Methods 0.000 description 4
- 238000005516 engineering process Methods 0.000 description 4
- 238000005457 optimization Methods 0.000 description 4
- 238000011160 research Methods 0.000 description 4
- 238000004364 calculation method Methods 0.000 description 3
- 230000006870 function Effects 0.000 description 3
- VYMDGNCVAMGZFE-UHFFFAOYSA-N phenylbutazonum Chemical compound O=C1C(CCCC)C(=O)N(C=2C=CC=CC=2)N1C1=CC=CC=C1 VYMDGNCVAMGZFE-UHFFFAOYSA-N 0.000 description 3
- 241001156002 Anthonomus pomorum Species 0.000 description 2
- 241000239290 Araneae Species 0.000 description 2
- 241000611421 Elia Species 0.000 description 2
- 238000011960 computer-aided design Methods 0.000 description 2
- 238000011161 development Methods 0.000 description 2
- 230000018109 developmental process Effects 0.000 description 2
- 230000000694 effects Effects 0.000 description 2
- 238000013507 mapping Methods 0.000 description 2
- 230000000903 blocking effect Effects 0.000 description 1
- 230000001413 cellular effect Effects 0.000 description 1
- 238000012512 characterization method Methods 0.000 description 1
- 238000006243 chemical reaction Methods 0.000 description 1
- 230000019771 cognition Effects 0.000 description 1
- 238000004891 communication Methods 0.000 description 1
- 239000012141 concentrate Substances 0.000 description 1
- 238000000354 decomposition reaction Methods 0.000 description 1
- 238000012217 deletion Methods 0.000 description 1
- 230000037430 deletion Effects 0.000 description 1
- 238000013461 design Methods 0.000 description 1
- 230000009977 dual effect Effects 0.000 description 1
- 230000007613 environmental effect Effects 0.000 description 1
- 238000005206 flow analysis Methods 0.000 description 1
- 230000003993 interaction Effects 0.000 description 1
- 238000007726 management method Methods 0.000 description 1
- 239000003550 marker Substances 0.000 description 1
- 238000009401 outcrossing Methods 0.000 description 1
- 238000007430 reference method Methods 0.000 description 1
- 238000012216 screening Methods 0.000 description 1
- 230000011218 segmentation Effects 0.000 description 1
- 238000000926 separation method Methods 0.000 description 1
- 238000012732 spatial analysis Methods 0.000 description 1
- 238000003786 synthesis reaction Methods 0.000 description 1
Images
Landscapes
- Traffic Control Systems (AREA)
Abstract
A multilevel multi-modal routing navigating method relates to a routing navigation, which is implemented by establishing a road central line node table and an arc section table, generating topology texts T1 and T2, inputting starting point S and destination D, reading road central line and traffic lane attribute data, and calculating optimal routes R1 and R2 based on T1 and T2; establishing actual traffic lane topological structure T3, and recording physical traffic lane ID, virtual traffic lane ID as well as associated starting point ID and destination ID; reading actual traffic lane attribute data, and calculating optimal route R3 based on T3; according to R1, generating a buffer area B1 with certain range d1 in a dynamic way, selecting out architecture set L1 in B1, expressing L1 in a 2D visible window, selecting out landmark architecture set L2 in L1, expressing L2 in the 2.5D visible window, according to the coordinate position of a driver, dynamically calling a buffer area B2 of d2, selecting real time visible landmark L3 containing L2 in B2, and dynamically calling in road traffic relevant facilities in B2.
Description
Technical field
The present invention relates to a kind of footpath navigation of seeking, particularly relate to a kind of multilevel multi-modal routing navigating method when being used for various vehicle driving.
Background technology
A gordian technique in many important applied field such as the service that seeking directly navigates is based on the position, intelligent transportation, emergency reaction.Along with the fast development in city, complicated road network system and means of transportation have appearred in the big city, such as viaduct, underpass, auxilliary road, viaduct etc., all present typical three-dimensional feature.Incident is dynamic, diversity and the specialization of traffic control, for example turns to restriction, one-way trip, Emergency Vehicle Lane, speed limit track etc.In the face of so complicated traffic environment, the service quality of seeking the footpath navigation has had new requirement, is presented as personalized and linguistic context (personalized & contextual) especially.
The path query of at first, satisfying personalized different road network levels.For the user who is familiar with local road traffic environment, needing to understand concrete which bar track can pass through; And, be concerned about how to arrive the destination for the user who is not familiar with the local transit environment, only need to understand which bar street and allow current.Promptly seek the footpath problem at many levels.
Secondly, the visual of navigation information varies with each individual, because of scape different.Such as, the individual user needs three-dimensional navigation scene true to nature to experience local environment on the spot in personly, and other users need provide whole route indication, also have the user to need the switching between the different mode, maximize scene comprehensively and experience.In addition, the navigation content under the different conditions is not quite similar, and need provide disaster relevant information such as the navigation Service under the calamity emergency situation.It is multi-modal navigation problem.
At present, the principal element of restriction multilevel multi-modal routing navigating development has: the road net model tormulation is improper, seek at many levels that the footpath algorithm is improper, the navigation thinking does not match.Below make simple analysis with regard to the problems referred to above.
(1) road network model misrepresentation
Tradition is sought the road axis that the footpath air navigation aid is based on two dimension mostly, with the multilevel traffic of complicacy abstract be simple node, with single segmental arc expression whole street.This describing method obviously can not be expressed complicated multilevel traffic, and topological relation and the complicacy of crossing particularly expressed between single track turn to relation.Relevant improving one's methods arranged in recent years, mainly is to express multilevel traffic through the nonplanar network method, or embodies the restriction that turns to of crossing with GO TO table method or dual graph, or writes down single track topology with the linear reference method.It seems that comprehensively the relevant interdependent geometry entity of improving one's methods remains road axis or comprehensive track, still rests on two dimension in the visual expression.Relevant document has: 1, Fohl, Curtin, Goodchild et al.ANon-Planar, Lane-Based Navigable Data Model for ITS.7th International Symposium on SpatialData Handling, 1996; 2, Lu Feng, Zhou Chenghu, ten thousand celebratings. based on the urban traffic network on-plane surface data model of characteristic. mapping journal, 2000,29 (4): 334-341; 3, what Guiping, Zhao Hongduo, Yao Zukang. based on the OO grade separation model of linear reference system. highway communication science and technology, 2001,6:86-89; 4, Jiang; Han and Chen.Modelling Turning Restrictionsin Traffic Network for Vehicle Navigation System.Symposium on geospatial theory; Processing andapplications, 2002; 5, Winter.Modeling Costs of Turns in Route Planning.GeoInformatica, 2002,6 (4): 345-361; 6, Han Gang, Jiang Jie, Chen Jun treat etc., take the segmental arc dijkstra's algorithm of road turning restriction in the onboard navigation system into account. mapping journal, 2002,31 (4): 366-368; 7, Cova and Johnson.A Network Flow Model for Lane-basedEvacuation Routing.Transportation Research Part A:Policy and Practice, 2003,37 (7): 579-604; 8, Zuo Xiaoqing, Li Qingquan, Xie Zhiying. based on the road data model in track. Chang An University's journal (natural science edition), 2004,24 (2): 73-76; 9, appoint just Wang Wei, Deng Wei. band turns to shortest route problem and the method for solving thereof of incuring loss through delay and limiting. Southeast China University's journal (natural science edition), 2004,34 (1): 104-108; 10, Malaikrisanachalee and Adams.Lane-based Networkfor Transportation Network Flow Analysis and Inventory Management.TRR Journal of theTransportation Research Board; 2005,1935:101-110; 11, Li and Lin.A Trajectory-OrientedCarriageway-Based Road Network Data Model, Part 1:Background.Geo-spatiaI InformationScience, 2006,9 (1): 65-70.
(2) seek at many levels the footpath algorithm improper
The present footpath algorithm of seeking at many levels mainly contains two types, and a kind of is the attribute hierarchies information (national highway, major trunk roads, subsidiary road and branch road etc.) of utilizing road net intrinsic, preferentially selects the high highway section of category of roads.Another kind is to utilize multistage road net structure like the structure pyramid of multiple dimensioned data source nature (1: 50000,1: 10000 with 1: 5000 etc.), preferentially selects the small scale road network to optimize and seeks directly efficient.Analysis-by-synthesis can be seen, seeks the footpath algorithm at many levels for these two kinds and all can not solve the footpath problem of seeking at many levels that " road axis-runway-actual track " this type considered spatial cognition rule and reasoning rule.Pertinent literature has: 12, Quek and Srikanthan.A hierarchical representation of roadway networks 7th World Congress onIntelligent Transportation Systems, 2000; 13, Park, Sung, Doh et al.Finding a path in thehierarchical road networks.Proceedings of 2001 IEEE Intelligent Transportation Systems, 2001,936-942; 14, Jagadeesh; Srikanthan and Quek.Heuristic Techniques for Accelerating HierarchicalRouting on Road Networks.IEEE Transactions on intelligent transportation system 2002,3 (4): 301-309; 15, Chen Ze king, Yuan's letter. based on a kind of real-time vehicle path planning algorithm of layering decomposition. Nanjing Aero-Space University's journal, 2003,35 (2): 193-197; 16, Fu Mengyin, Li Jie, Deng Zhihong. based on the novel path planning algorithm of layering road network. computer-aided design (CAD) and graphics journal, 2005,17 (4): 719-722; 17, Chen Yumin, Gong Jianya, Shi Wenzhong. the optimal path algorithm research of multistage road net. Wuhan University's journal information science version, 2006,31 (1): 70-73).
(3) the navigation thinking does not match
From the visual angle of navigating; The focus that the past people pay close attention to often concentrates on two aspects: the first satisfies different traffic trip modes (such as train, public transport, highway, pedestrian etc.) or different information interaction mode (voice; Image; Touch etc.) the visual service of navigation, promptly so-called multi-modal navigation; Another kind is to utilize appropriate landmark enhanced navigation effect of visualization, promptly so-called ground marker navigation.These two kinds navigation thinkings have satisfied the integrality and the verisimilitude of navigation Service to a certain extent, but can't solve personalized question, particularly vary with each individual, because of the different multi-modal navigation problem of scape.Pertinent literature has: 18, Goodchild.GIS and Transportation:Status and Challenges.GeoInformatica, 2000,4 (2): 127-139; 19, Timpf and Heye.Complexity of routes in multi-modal wayfinding.Second InternationalConference on Geographic Information Science, 2002; 20, Brenner and Elias.Extracting landmarksfor car navigation systems using existing GIS databases and laser scanning.ISPRS Archives; 2003, XXXIV (Part 3/W8): 17-19; 21, Elias and Brenner.Automatic Generation and Application ofLandmarks in Navigation Data Sets.11th International Symposium on Spatial Data Handling, 2004; 22, Li Yuan. based on the architectural scale multi-mode emergency route planning of semantic information. Central China building, 2007,25 (3): 109-111; 24, Xiong Liyin, Lu Feng, Chen Chuanbin. city multimode traffic network characterization connected relation is expressed model. Wuhan University's journal information science version, 2008,33 (4): 393-396.
Domestic related application, such as publication number be the application for a patent for invention of CN101191730 disclose a kind of in auto-navigation system the method and the device thereof of retrieval user point of interest (points of interest) database.The information retrieval method of auto-navigation system may further comprise the steps: be information necessary in the searching interest point data base, generate the general index of relevant numeric type data and the full treatment step of the inverted file index of the title that not have to sort; Differentiating the search condition of input, under the situation that title is retrieved separately, is that step is for information about retrieved and exported on the basis with the inverted file index to above-mentioned title; Differentiate the search condition of input, in title separately under the situation beyond the retrieval, be the basis, retrieve and export step for information about with the general index of above-mentioned numeric type data.
Publication number is that the application for a patent for invention of CN1724976 provides on the picture of navigational system by user's requirement display frame treatment situation step by step.
Although above-mentioned patent documentation has promoted the personalized level of seeking the footpath navigation Service, and does not match different scale applied environment (such as macroscopical 2D, middle sight 2.5D and microcosmic 3D).Up to the present, also do not see complete multilevel multi-modal routing navigating patent documentation.
Summary of the invention
The object of the present invention is to provide a kind of multilevel multi-modal routing navigating method when being mainly used in various vehicle driving.
The present invention includes following steps:
1) according to the road axis geometric data, set up road axis ode table and segmental arc table, generate topological file T1, write down each segmental arc ID, start node ID and stop node ID;
2) according to runway center line geometric data and crossing region geometry data, generate topological file T2, write down the connected relation in each runway and the zone, crossing;
3) input starting point S and terminal point D read road axis attribute data and runway attribute data, utilize dijkstra's algorithm to calculate optimal path R1 and R2 based on topological file T1 and topological file T2 respectively;
4) according to optimal path R2, read related with it runway data set, set up actual track topological structure T3, record physics track ID and virtual track ID, and related starting point ID and terminal point ID;
5) read actual track attribute data, utilize dijkstra's algorithm to calculate optimal path R3 based on actual track topological structure T3;
6) according to optimal path R1, dynamically generate the buffer zone B1 of certain limit d1, filter out the building collection L1 in the buffer zone B1 scope, express building collection L1 in the 2D visualization window with diagramatic way, overall navigational environment is provided;
7) call the building attribute information, further filter out the landmark collection L2 among the building collection L1 that meets the demands, in the 2.5D visualization window,, see navigational environment in providing with axonometric drawing model tormulation landmark collection L2;
8) according to drivers's coordinate position; The buffer zone B2 of dynamic dispatching certain limit d2; Further screen the real-time visual landmark collection L3 that comprises landmark collection L2 in the buffer zone B2 scope; Give respective texture, and in buffer zone B2 scope, dynamically call in the road traffic related facility, 3D microcosmic navigational environment is provided.
In step 3), said road axis attribute data comprises distance, average speed etc., and said runway attribute comprises data such as distance, the unidirectional speed of a motor vehicle, crossing time delay.
In step 4), said actual track attribute data comprises current observation time in track and current stand-by period of crossing etc.
In step 7), said building attribute information comprises character, height etc.
In step 8), said road traffic related facility comprises street lamp, traffic indication board etc.
Said step 2) in, according to runway center line geometric data and crossing region geometry data, generate topological file T2, the method that writes down the connected relation in each runway and the zone, crossing may further comprise the steps:
1) according to the runway geometric data, set up runway ode table and segmental arc table, generate runway local topology file T2
*, write down each runway ID, start node ID and stop node ID;
2) utilize the crossing geometric data, extract its how much barycenter, set up crossing's ode table, and record crossing determinant attribute information, said crossing determinant attribute information comprises enters a profession track ID and goes out runway ID etc.;
3) according to crossing ode table and runway local topology file T2
*, newly-built crossing region topology file T2#, the connection segmental arc ID in the record zone, crossing, start node ID and termination node ID;
4) merge runway local topology file T2
*With crossing region topology file T2#, generate topological file T2, write down complete runway connected relation.
In the said step 4),, read with it related runway data set, set up actual track topological structure T3 according to optimal path R2, record physics track ID and virtual track ID, and related starting point ID and the method for terminal point ID may further comprise the steps:
1) reads the runway ID data set related, generate the topological fundamental in actual track, make up actual track local topology file T3 according to the corresponding attribute data of each runway ID with optimal path R2
*Write down each physics track ID, start node ID and stop node ID; The attribute data that said each runway ID is corresponding comprises actual number of lanes etc., the fundamental of said actual track topology comprise by the runway direction from left to right serial number represent actual track attribute;
2) utilize the number information in actual track and the turning restrictive condition of crossing; Replenish the virtual track ID of crossing; Make up the local topology file T3# of crossing; Write down each virtual track ID, start node ID and stop node ID, the turning restrictive condition of said crossing comprises craspedodrome, left-hand rotation, the control etc. of turning right;
3) merge actual track local topology file T3
*Local topology file T3# with crossing generates topological file T3^, writes down complete static actual track connected relation;
4) detect whether the incident of existence and event property thereof are arranged, the mutual click of mouse carried out track discretize processing, dynamically increases actual track node and actual track segmental arc, on topological file T3^ basis, generates dynamic topology T3.
The present invention is the basis with multi-level road network model and multiple dimensioned BUILDINGS MODELS; Rely on the three-dimension GIS system; Automatically make up actual track, runway and road axis three-layer network topological structure through semantic relation, multi-level path optimization algorithm is provided, set up the visual navigation window of 2D, 2.5D and three kinds of mode of 3D; The route guidance of corresponding macroscopic view, middle sight and microcosmic respectively, satisfying personalized linguistic context self-adaptation navigation demand.
The Basic Ways that the present invention realizes is according to given departure place and destination, at first, analyzes the topological network of road axis, satisfies macroanalysis and visual needs, the particularly needs of the dynamic dispatching of icon model; And then see the runway topological network of level in analyzing, and take all factors into consideration that flowing to turns with the crossing limits, the minimum initial data set of optimal path is provided for the selection in actual track.At last, according to the actual track topology information of association and actual track attribute information etc., confirm practicable track at the microcosmic level.In navigation information output, consider the control of two-layer mode: first application context mode, " role " through definition (role) (situation) controls the content of visual output with " environment "; It two is a visualization window mode, decomposes navigation information with " three-dimensional behavior view ", the overall situation and local message that the maximization input is navigated through " two-dimensional map view ", " the 2.5 dimension navigator views " set.
Description of drawings
Fig. 1 is a principle schematic of the present invention.
Fig. 2 seeks the footpath process flow diagram at many levels for the present invention.
Fig. 3 is the multi-modal navigation flowcharts of the present invention.
Fig. 4 is road axis constructing network topology figure of the present invention.
Fig. 5 is runway constructing network topology figure of the present invention.
Fig. 6 is the actual track of the present invention constructing network topology figure.
Fig. 7 is a 2D map modal data tissue of the present invention.
Fig. 8 is 2.5D navigation modal data tissue of the present invention.
Fig. 9 is a 3D behavior modal data tissue of the present invention.
Embodiment
Following examples will combine accompanying drawing that the present invention is further described.
Referring to Fig. 1; Technical scheme principle of the present invention is based on multi-level Three-dimensional Numeric Map database; Comprise multi-level three-dimensional road network model and multiple dimensioned three-dimensional building model, under the support of high precision vehicle positioning technology, utilize the three-dimension GIS system operation platform; Multi-level path optimization and multi-modal path navigation are provided, satisfy the personalized navigation Service in the complicated urban environment.Do following explanation to key modules wherein:
1) multi-level three-dimensional road network model: same road is different according to level of detail, be organized as the geometry and the network topology structure of " road axis-runway-actual track " three levels, and make up its internal relations.Wherein, the road-center line structure is with the geometric shape of single line abstractdesription road, and its locus places road central authorities; Runway is described the geometric shape of road with two-wire, and the two-wire locus places the center of the flow direction respectively; Actual track is with the geometric shape of multi-thread description road; According to function difference be subdivided into physics track and virtual track (how much bands in track in the corresponding real road network in physics track, virtual track realize the physics track laterally with the zone, crossing in be connected).
2) high precision vehicle location: with the high precision vehicle positioning technology is support; Centimetre-sized vehicle Real-time and Dynamic three-dimensional coordinate information is provided; Cooperate the track band geological information in the multi-level three-dimensional road network model, can extrapolate the particular location of vehicle on actual track.
3) 3DGIS man-machine interface: three-dimension GIS provides data processing and visual platform, and three-dimensional spatial analysis functions such as three-dimensional buffer zone analysis and the three-dimensional multi-scale expression control of band texture particularly is provided.Utilize the 3DGIS man-machine interface, can inquire about three-dimensional above and below ground object in real time, the overall situation and local visible environment are provided at three dimensions.
4) multi-level path optimization: this function is on multi-level three-dimensional road network models, designs corresponding path calculation method respectively, and the path based on road axis, the path of runway and the path in actual track are provided.
5) multi-modal path navigation: the result with multi-level path optimization is the basis; Consider multi-level Three-dimensional Numeric Map database; On the 3DGIS platform, develop 2D, 2.5D and 3D navigation visualization window, corresponding respectively macroscopical map mode navigation, the navigation of mesoscopic model mode and the navigation of microscopic behavior mode.
6) personalized application environment: the whole external demand of seeking the footpath navigation Service, be presented as the personalization apolegamy of navigation content, the selection of navigation mode.
Referring to Fig. 2, the algorithm flow of seeking the footpath at many levels comprises structure three-layer network topological structure T1, T2 and T3.Wherein, T1 and T2 are independent structures, and T3 further makes up on the R2 basis.The input content of seeking the footpath algorithm flow at many levels is three-dimensional scenic, inquiry starting point and terminal point, and output content is R1, R2 and R3.At first; According to the topological network (topological T1) and the runway topological network (topological T2) of predefined process (topology constructing 1 and topology constructing 2) analysis road axis, calculate road-center thread path (path R1) and runway path (path R2) with predefined process (Dijkstra seeks the footpath algorithm).Then, utilize path R2 to read related partial row's lane information, analyze actual track topological network (topological T3), calculate path, actual track (path R3) with predefined process (Dijkstra seeks the footpath algorithm) according to predefined process (topology constructing 3).
Referring to Fig. 3, the algorithm flow of multi-modal navigation is with R1, and R2 and R3 are the basis, through the method for data screening layer by layer, expresses with 2D map view, 2.5D navigator views and 3D behavior view respectively.Wherein, multiple dimensioned model database is an important foundation of the present invention, comprises 2D diagram, 2.5D axonometric drawing and the 3D model of building.To path R1, utilize buffer zone analysis 1 to call the 2D diagram, produce and analyze data (diagram collection L1), and offer the 2D map view.Simultaneously,, call in predefined process (semantic analysis), read building height attribute and character attribute, filter out terrestrial reference collection L2, and offer the 2.5D navigator views based on L1 and axonometric drawing database.Then,, call in predefined process (buffer zone analysis 2), calculate the 3D building collection L3 in the visual line of sight, and offer 3D behavior view based on L2 and 3D model bank.
Implementation procedure of the present invention adopts computer automation to handle, and may further comprise the steps:
For the ease of implementing, the invention provides the concrete mode of step 2, may further comprise the steps:
Step 2.1 according to the runway geometric data, is set up runway ode table and segmental arc table, generates runway local topology file T2
*The present invention reads every runway point set successively according to the runway geometric data, sets up the segmental arc table.Then, obtain in the runway point set and have a few, extract node from beginning to end, and check and have or not repetition, remove the repetition node, set up the runway ode table.Then, according to coordinate position, the table that establishes a connection generates runway local topology file T2 by segmental arc ID in node ID in the ode table and the segmental arc table
*, write down each runway ID, start node ID and stop node ID.
Step 2.2 is utilized the crossing geometric data, extracts its how much barycenter, sets up crossing's ode table, and record crossing determinant attribute information (go into runway ID and go out runway ID).The present invention stores each crossing separately, is the runway connected relation of object tissue crossing with the crossing.On implementation, at first choose the crossing geometric object, be selected into the runway geometric object of crossing then successively, select the driveway geometric object of crossing after the affirmation more successively.Under the default situations, system confirms to go into runway and go out runway according to the digitizing direction of runway automatically.Then, according to the apex coordinate collection of crossing object, calculate center-of-mass coordinate and write down generation crossing ode table barycenter ID number.The crossing ode table is recorded into runway ID collection and goes out runway ID collection.
Step 2.3 is according to crossing ode table and T2
*, newly-built crossing region topology file T2#, the connection segmental arc ID in the record zone, crossing, start node ID and termination node ID.Among the present invention, the inner topological relation in crossing is to realize through the segmental arc of setting up automatically between runway node and the crossing node.At first, utilize going into runway ID collection and going out runway ID collection in the ode table of crossing, find each runway ID, and at T2
*Two records of middle increase " are gone into crossing ID " and " going out crossing ID ", and the crossing id information is recorded each runway ID.Then, utilize the T2 that upgrades
*In each runway ID play period (F_Node) and endpoint number (T_Node); And go into to intersect the slogan (In_Node) and the slogan (Out_Node) that goes out to intersect; Newly-built crossing intra-zone segmental arc ID; Segmental arc starting point and terminal point are played period and are gone out to intersect slogan by runway respectively, and perhaps the runway terminal point and the slogan of going into to intersect constitute, and accomplish crossing region topology file T2# and set up.
Step 2.4 merges T2
*And T2#, generate topological file T2, write down complete runway connected relation.This step is with newly-built crossing intra-zone segmental arc ID table, is increased in the runway ID table, constitutes a complete segmental arc-ode table.
Step 3; Input starting point S and terminal point D; Read road axis attribute data (distance, average speed) and runway attribute (distance, the unidirectional speed of a motor vehicle, crossing time delay) data, utilize dijkstra's algorithm to calculate optimal path R1 and R2 respectively based on T1 and T2.The present invention utilizes traditional Dijkstra to seek the footpath algorithm, calculates the optimal path of vehicle location to the destination.Because road-center spider lines and runway network data amount are not very big, the node number that can travel through calculating is not a lot, on efficiency of algorithm, can meet the demands.On implementation, create two tables (Open table and Close table), preserve all respectively and generated and node of not investigating and the node of having visited.At first in the accesses network from starting point recently and the point that was not examined, this point is put into the Open table and is waited to look into.Find out apart from the nearest point of starting point from the Open table then, find out this all child nodes of point, put into the Close table changing the time.The child node that traversal is investigated this point calculates the weighted value of these nodes apart from starting point, puts child node in the Open table.At last, repeat preceding step, be sky up to the Open table, or find impact point.Among the present invention, for the road-center spider lines, the weight of consideration is a distance, and for the runway network, owing to have the traffic flow directivity, the weight of consideration is a transit time.
Step 4 is referring to Fig. 6.According to R2, read related with it runway data set, set up actual track topological structure T3, record physics track ID and virtual track ID, and related starting point ID and terminal point ID.Among the present invention, adopt the heuristic local method that makes up actual track topology, significantly reduce web search space and actual track network calculations efficient.On implementation, express the actual track topology element on the highway section through setting up the physics track, express the actual track connected relation in the zone, crossing through setting up virtual track.Simultaneously, this research further contemplates the discretize in actual track and handles, and promptly maybe ought detect interim incident (blocking such as the track) at the prompting place of changing trains, and upgrades actual track topology.
For the ease of implementing, the invention provides the concrete mode of step 4, may further comprise the steps:
Step 4.1; Read the runway ID data set related with R2; According to the corresponding attribute data (actual number of lanes) of each runway ID generate actual track topology fundamental (by the runway direction from left to right serial number represent actual track attribute), make up actual track local topology file T3
*, write down each physics track ID, start node ID and stop node ID.Among the present invention; Actual track topology is derived by the runway geometric network; Derive concrete actual track topology key element according to the actual number of lanes that writes down in the runway attribute list, and automatically the runway topology element that derives is write actual lane number according to the direction of runway.
Step 4.2; Utilize the number information in actual track and the turning restrictive condition of crossing (control of keeping straight on, turn left, turn right); Replenish the virtual track ID of crossing, make up the local topology file T3# of crossing, write down each virtual track ID, start node ID and stop node ID.The virtual track robotization that the present invention utilizes respective rule to control crossing makes up.On implementation, rule definition is following:
1) same highway section runway, numbering is set up virtual track between the minimum actual track, uses to be the U type virtual track of turning around
2) the actual track, centre of runway is gone into by crossing, sets up virtual track with other actual tracks, centre that go out runway (remove same highway section and go out runway), uses to be Through Lane.
3) the maximum actual track of numbering of runway is gone into by crossing, sets up virtual track with other maximum actual tracks of numbering that go out runway (remove same highway section and go out runway), uses to be right-turn lane.
Wherein, because the actual number of lanes of each runway record changes, as above rule possibly produce and repeat virtual track, needs deletion repeating data automatically; In addition, each regional actual traffic planning has special case, need come to set up automatically virtual track according to actual steering restriction change traffic rules.
Step 4.3 merges T3
*And T3#, generate topological file T3^, write down complete static actual track connected relation.This step is with the virtual track of intra-zone, newly-built crossing segmental arc ID table, is increased in the physics track ID table, constitutes a complete actual track segmental arc-ode table.
Step 4.4, whether detect has the incident of existence and event property thereof, and mutual click of mouse carried out track discretize processing, dynamically increases actual track node and actual track segmental arc, on the T3^ basis, generates dynamic topology T3.The present invention considers two kinds of traffic behaviors, and a kind of is the behavior of changing between the actual track, and also a kind of is actual Lane Closed behavior under the interim incident.On implementation, handle automatically through computer for first kind, promptly according to the runway direction, choose 2/3 place for changing a little, actual track is divided into the speed-raising district and changes Dao Qu.Second kind is passed through the artificial runway geometric network of clicking, and specifies the position of actual Lane Closed alternately.Two kinds of processing modes all on the segmental arc of original physical track, increase intermediate node, and increase the virtual segmental arc between the intermediate node automatically, are updated to dynamic actual track topology T3.
Step 6 is referring to Fig. 7.According to R1, dynamically generate the buffer zone B1 of certain limit d1, filter out the building collection L1 in the B1 scope, express L1 in the 2D visualization window with diagramatic way, overall navigational environment is provided.The present invention adopts local two-dimensional diagram mode in the macroscopic view navigation is visual, maximum characteristics are that diagram has clear and definite characteristic and meaning, such as hotel, market, stopway, charge station etc.Adopt the reference international standard of ISO19117, preestablish the two-dimensional diagram collection, filter out the diagram building in the R1 certain limit as buffer zone analysis through the association of building character with to path R1 according to building and type of ground objects as Graphic Expression.On implementation, the radius d1 default setting of R1 buffer zone is 50m, and whole navigational environment promptly provides the building symbolism all along the path to represent scene.For the extraneous building of buffer zone, still to build two-dimentional geometrical shape as visual background.
Step 7 is referring to Fig. 8.Call building attribute information (character, highly), further filter out the landmark collection L2 among the L1 that meets the demands, in the 2.5D visualization window,, see navigational environment in providing with axonometric drawing model tormulation L2.The present invention adopts local 2.5 dimension stereoscopic model modes in middle sight navigation is visual, maximum characteristics are to highlight building height and building character.On concrete the realization, the mode that adopts attribute data to read promptly reads the elevation information and building property information of the related building ID of landmark among the L1, filters out vision is outstanding, meaning is important building as landmark.Then, utilize height attributes to draw high landmark and give particular color and strengthen effect of visualization.The default rule of definitions of color is following: { residential architecture: yellow; Commercial building: orange; Administrative office building: redness; Other buildings: blueness }.
Claims (5)
1. multilevel multi-modal routing navigating method is characterized in that may further comprise the steps:
1) according to the road axis geometric data, set up road axis ode table and segmental arc table, generate topological file T1, write down each segmental arc ID, start node ID and stop node ID;
2) according to runway center line geometric data and crossing region geometry data, generate topological file T2, write down the connected relation in each runway and the zone, crossing, concrete steps are following:
(1) according to the runway geometric data, set up runway ode table and segmental arc table, generate runway local topology file T2*, write down each runway ID, start node ID and stop node ID;
(2) utilize the crossing geometric data, extract its how much barycenter, set up crossing's ode table, and record crossing determinant attribute information, said crossing determinant attribute information comprises enters a profession track ID and goes out runway ID;
(3) according to crossing ode table and runway local topology file T2*, newly-built crossing region topology file T2#, the connection segmental arc ID in the record zone, crossing, start node ID and termination node ID;
(4) merge runway local topology file T2* and crossing region topology file T2#, generate topological file T2, write down complete runway connected relation;
3) input starting point S and terminal point D read road axis attribute data and runway attribute data, utilize dijkstra's algorithm to calculate optimal path R1 and R2 based on topological file T1 and topological file T2 respectively;
4) according to optimal path R2, read related with it runway data set, set up actual track topological structure T3, record physics track ID and virtual track ID, and related starting point ID and terminal point ID, concrete steps are following:
(1) reads the runway ID data set related with optimal path R2; Generate the fundamental of actual track topology according to the corresponding attribute data of each runway ID; Make up actual track local topology file T3*; Write down each physics track ID, start node ID and stop node ID, the attribute data that said each runway ID is corresponding comprises actual number of lanes, the fundamental of said actual track topology comprise by the runway direction from left to right serial number represent actual track attribute;
(2) utilize the number information in actual track and the turning restrictive condition of crossing; Replenish the virtual track ID of crossing; Make up the local topology file T3# of crossing; Write down each virtual track ID, start node ID and stop node ID, the turning restrictive condition of said crossing comprises craspedodrome, left-hand rotation, the control of turning right;
(3) the local topology file T3# of actual track local topology file T3* of merging and crossing generates topological file T3^, writes down complete static actual track connected relation;
(4) detect whether the incident of existence and event property thereof are arranged, the mutual click of mouse carried out track discretize processing, dynamically increases actual track node and actual track segmental arc, on topological file T3^ basis, generates dynamic topology T3;
5) read actual track attribute data, utilize dijkstra's algorithm to calculate optimal path R3 based on actual track topological structure T3;
6) according to optimal path R1, dynamically generate the buffer zone B1 of certain limit d1, filter out the building collection L1 in the buffer zone B1 scope, express building collection L1 in the 2D visualization window with diagramatic way, overall navigational environment is provided;
7) call the building attribute information, further filter out the landmark collection L2 among the building collection L1 that meets the demands, in the 2.5D visualization window,, see navigational environment in providing with axonometric drawing model tormulation landmark collection L2;
8) according to drivers's coordinate position; The buffer zone B2 of dynamic dispatching certain limit d2; Further screen the real-time visual landmark collection L3 that comprises landmark collection L2 in the buffer zone B2 scope; Give respective texture, and in buffer zone B2 scope, dynamically call in the road traffic related facility, 3D microcosmic navigational environment is provided.
2. multilevel multi-modal routing navigating method as claimed in claim 1 is characterized in that in step 3), and said road axis attribute data comprises distance, average speed, and said runway attribute comprises distance, the unidirectional speed of a motor vehicle, crossing time delay.
3. multilevel multi-modal routing navigating method as claimed in claim 1 is characterized in that in step 4), and said actual track attribute data comprises current observation time in track and current stand-by period of crossing.
4. multilevel multi-modal routing navigating method as claimed in claim 1 is characterized in that in step 7), and said building attribute information comprises character, highly.
5. multilevel multi-modal routing navigating method as claimed in claim 1 is characterized in that in step 8), and said road traffic related facility comprises street lamp, traffic indication board.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN2009101122541A CN101608926B (en) | 2009-07-24 | 2009-07-24 | Multi-level multi-modal route-finding navigation method |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN2009101122541A CN101608926B (en) | 2009-07-24 | 2009-07-24 | Multi-level multi-modal route-finding navigation method |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN101608926A CN101608926A (en) | 2009-12-23 |
| CN101608926B true CN101608926B (en) | 2012-02-01 |
Family
ID=41482761
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN2009101122541A Expired - Fee Related CN101608926B (en) | 2009-07-24 | 2009-07-24 | Multi-level multi-modal route-finding navigation method |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN101608926B (en) |
Families Citing this family (29)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN102999646B (en) * | 2011-09-14 | 2015-03-04 | 中国科学技术大学 | Method and system for vehicle following and track change in microscopic traffic simulation |
| CN103245342A (en) * | 2012-02-06 | 2013-08-14 | 北京四维图新科技股份有限公司 | Navigation implementation method and navigation implementation apparatus |
| CN104573140A (en) * | 2013-10-09 | 2015-04-29 | 北京军区军事训练模拟仿真研发服务中心 | Layered dynamic path planning method applied to virtual simulation |
| CN104183016B (en) * | 2014-09-05 | 2017-08-15 | 山东省国土测绘院 | A kind of construction method of quick 2.5 dimension building model |
| WO2016082875A1 (en) * | 2014-11-26 | 2016-06-02 | Kone Corporation | Local navigation system |
| EP3330670B1 (en) * | 2015-07-27 | 2019-12-18 | Nissan Motor Co., Ltd. | Route searching device and route searching method |
| TWI584224B (en) * | 2015-12-14 | 2017-05-21 | 台灣國際航電股份有限公司 | 3d map generating method |
| US10048688B2 (en) * | 2016-06-24 | 2018-08-14 | Qualcomm Incorporated | Dynamic lane definition |
| WO2018000313A1 (en) | 2016-06-30 | 2018-01-04 | 华为技术有限公司 | Lane scheduling method, lane information acquisition method, vehicle and management device |
| JP7016214B2 (en) * | 2016-11-29 | 2022-02-04 | アルパイン株式会社 | Travelable area setting device and travelable area setting method |
| CN108663059A (en) * | 2017-03-29 | 2018-10-16 | 高德信息技术有限公司 | A kind of navigation path planning method and device |
| CN107389079B (en) * | 2017-07-04 | 2020-07-28 | 广州海格星航信息科技有限公司 | High-precision path planning method and system |
| CN109242230B (en) * | 2017-07-10 | 2021-09-03 | 中国科学院沈阳自动化研究所 | Scheduling method for solving WBS (work breakdown Structure) sorting problem |
| CN107817000B (en) * | 2017-10-25 | 2020-09-08 | 广州汽车集团股份有限公司 | Path planning method and device for unmanned vehicle and computer equipment |
| CN110110019B (en) * | 2018-01-31 | 2021-10-29 | 北京四维图新科技股份有限公司 | Road network topology data updating method and device |
| CN110440818B (en) * | 2018-05-04 | 2021-11-19 | 沈阳美行科技有限公司 | Lane matrix model, construction method thereof, reading method and device |
| CN108921943B (en) * | 2018-06-29 | 2022-08-09 | 广东星舆科技有限公司 | Road three-dimensional model modeling method based on lane-level high-precision map |
| CN108898862A (en) * | 2018-07-03 | 2018-11-27 | 北京百度网讯科技有限公司 | The determination method, apparatus and electronic equipment of traffic light intersection |
| US10761535B2 (en) * | 2018-08-21 | 2020-09-01 | GM Global Technology Operations LLC | Intelligent vehicle navigation systems, methods, and control logic for multi-lane separation and trajectory extraction of roadway segments |
| CN111121793B (en) * | 2018-10-31 | 2022-07-01 | 百度在线网络技术（北京）有限公司 | Map generation method and device for unmanned driving and storage medium |
| CN111383450B (en) * | 2018-12-29 | 2022-06-03 | 阿里巴巴集团控股有限公司 | Traffic network description method and device |
| CN111912424A (en) * | 2019-05-09 | 2020-11-10 | 上海博泰悦臻电子设备制造有限公司 | Method for switching navigation visual angle, navigation device and vehicle |
| CN111846288B (en) * | 2020-07-30 | 2021-09-24 | 北京理工大学 | Differential game control method for soft landing of small celestial bodies in uncertain environment |
| CN112129306B (en) * | 2020-09-24 | 2024-05-28 | 腾讯科技（深圳）有限公司 | Route generation method, route generation device, computer equipment and storage medium |
| CN112216130B (en) * | 2020-09-30 | 2022-07-26 | 长沙理工大学 | An emergency vehicle induction method in a vehicle-road coordination environment |
| CN112683286A (en) * | 2021-03-16 | 2021-04-20 | 季华实验室 | Method and system for establishing topological road network map, storage medium and electronic equipment |
| CN114526753B (en) * | 2022-04-24 | 2022-07-15 | 深圳依时货拉拉科技有限公司 | Cross-road intersection rule association method and device, computer equipment and readable storage medium |
| CN114913144A (en) * | 2022-05-06 | 2022-08-16 | 国交空间信息技术（北京）有限公司 | Method, device and system for determining road center line, computing equipment and storage medium |
| CN117928559B (en) * | 2024-01-26 | 2024-08-30 | 兰州理工大学 | Unmanned aerial vehicle path planning method under threat avoidance based on reinforcement learning |
-
2009
- 2009-07-24 CN CN2009101122541A patent/CN101608926B/en not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| CN101608926A (en) | 2009-12-23 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN101608926B (en) | Multi-level multi-modal route-finding navigation method | |
| JP3370555B2 (en) | Pedestrian information provision system | |
| CN104899357B (en) | A kind of topological data extracting method based on AutoCAD level-crossing engineering drawings | |
| US8442767B2 (en) | Method of operating a navigation system to provide route guidance | |
| CN109976332A (en) | One kind being used for unpiloted accurately graph model and autonomous navigation system | |
| Beil et al. | CityGML and the streets of New York-A proposal for detailed street space modelling | |
| JP2005515513A (en) | Generate schematic | |
| CN102169637A (en) | Dynamic route guidance method oriented to urban traffic | |
| US8301641B2 (en) | Method of collecting information for a geographic database for use with a navigation system | |
| Chen et al. | Multi-scale and multi-modal GIS-T data model | |
| Labetski et al. | A proposal for an improved transportation model in CityGML | |
| CN106780739A (en) | A kind of intelligent substation patrol three-dimension GIS system method for building up | |
| CN116127786B (en) | System and method for calculating safety status of slow-moving groups based on urban slow-moving traffic simulation | |
| Beil et al. | Combined modelling of multiple transportation infrastructure within 3D city models and its implementation in CityGML 3.0 | |
| CN114580796B (en) | A tourism attribute path planning method and system | |
| Puusepp et al. | Simulating pedestrian movement | |
| Bartelme | Geographic information systems | |
| Boersma | Modelling different levels of detail of roads and intersections in 3D city models | |
| Eldeeb et al. | Investigating walkability and bikeability in compact vs. new extensions: the case of Greater Cairo | |
| JP2002333828A (en) | Electronic map data | |
| Wang et al. | Low-carbon mixed traffic route recommendation for community residents based on multilayer complex traffic network | |
| Noyman et al. | TravelAgent: Generative Agents in the Built Environment | |
| Golledge | Human wayfinding | |
| Gong | Generalization of road network for an embedded car navigation system | |
| de Oliveira e Sousa et al. | Towards urban densification: using shape grammar to develop components for retrofitting street design |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| C14 | Grant of patent or utility model | ||
| GR01 | Patent grant | ||
| CF01 | Termination of patent right due to non-payment of annual fee |
Granted publication date: 20120201 Termination date: 20150724 |
|
| EXPY | Termination of patent right or utility model |