CN107239461A - A kind of road isolated island determines method and device - Google Patents
A kind of road isolated island determines method and device Download PDFInfo
- Publication number
- CN107239461A CN107239461A CN201610183449.5A CN201610183449A CN107239461A CN 107239461 A CN107239461 A CN 107239461A CN 201610183449 A CN201610183449 A CN 201610183449A CN 107239461 A CN107239461 A CN 107239461A
- Authority
- CN
- China
- Prior art keywords
- road
- isolated island
- coordinate
- calculation
- node
- 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.)
- Granted
Links
- 238000000034 method Methods 0.000 title claims abstract description 42
- 238000004364 calculation method Methods 0.000 claims abstract description 97
- 238000006116 polymerization reaction Methods 0.000 claims abstract description 79
- 238000012216 screening Methods 0.000 claims description 3
- 238000001914 filtration Methods 0.000 claims description 2
- 230000002093 peripheral effect Effects 0.000 abstract description 5
- 238000010586 diagram Methods 0.000 description 10
- 230000000694 effects Effects 0.000 description 6
- 238000004422 calculation algorithm Methods 0.000 description 3
- 230000004931 aggregating effect Effects 0.000 description 2
- 230000005540 biological transmission Effects 0.000 description 2
- 241000208340 Araliaceae Species 0.000 description 1
- 235000005035 Panax pseudoginseng ssp. pseudoginseng Nutrition 0.000 description 1
- 235000003140 Panax quinquefolius Nutrition 0.000 description 1
- 230000003321 amplification Effects 0.000 description 1
- 238000013459 approach Methods 0.000 description 1
- 235000013399 edible fruits Nutrition 0.000 description 1
- 230000005611 electricity Effects 0.000 description 1
- 235000008434 ginseng Nutrition 0.000 description 1
- 238000011835 investigation Methods 0.000 description 1
- 238000012986 modification Methods 0.000 description 1
- 230000004048 modification Effects 0.000 description 1
- 238000003199 nucleic acid amplification method Methods 0.000 description 1
- 229920000642 polymer Polymers 0.000 description 1
- 230000000750 progressive effect Effects 0.000 description 1
- 238000009877 rendering Methods 0.000 description 1
- 238000013215 result calculation Methods 0.000 description 1
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
- G06F16/29—Geographical information databases
Landscapes
- Engineering & Computer Science (AREA)
- Databases & Information Systems (AREA)
- Theoretical Computer Science (AREA)
- Remote Sensing (AREA)
- Data Mining & Analysis (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Navigation (AREA)
Abstract
Method and device is determined this application discloses a kind of road isolated island, method includes：Obtain multiple calculation road requests comprising starting point coordinate and terminal point coordinate, road is calculated to ask to hold up to provide not successfully for calculation pass to ask the calculation road of road result to ask, coordinate points in the coordinate point set for further constituting the starting point coordinate in being asked by multiple calculation roads and terminal point coordinate carry out point polymerization, obtain multiple congruent points, using multiple congruent points as candidate roads isolated island, to determine road isolated island from the candidate roads isolated island.Holding up failed provide due to calculation pass asks the calculation road of road result to ask, at least one in its starting point coordinate and terminal point coordinate is road isolated island, the application regard congruent point as candidate roads isolated island, need only to check candidate roads isolated island progress peripheral path connectedness, determine whether it is road isolated island, the query context of road isolated island is greatly reduced, road isolated island can be fast and efficiently determined compared to prior art.
Description
Technical field
The application is related to path computation technique field, more specifically to a kind of road isolated island determination side
Method and device.
Background technology
Road isolated island is meant：If the road on certain position periphery, without connectedness, is somebody's turn to do with extraneous road
Position is road isolated island.
The presence of road isolated island can influence path computation service, be this it is desirable that early by road isolated island
Find out.But, due to the complexity of road network, if we travel through each one by one in electronic map
The road conditions of nearby coordinates, carry out the lookup of isolated island, it will take a substantial amount of time.For this existing skill
Art needs a kind of scheme badly, can fast and efficiently determine road isolated island.
The content of the invention
In view of this, method and device is determined this application provides a kind of road isolated island, for quick, height
The determination road isolated island of effect.
To achieve these goals, it is proposed that scheme it is as follows：
A kind of road isolated island determines method, including：
Multiple calculation road requests comprising starting point coordinate and terminal point coordinate are obtained, the calculation road request is to calculate pass
Holding up failed provide asks the calculation road of road result to ask；
Starting point coordinate in multiple calculation road requests, the coordinate points of terminal point coordinate are subjected to point polymerization, obtained
To multiple congruent points, using multiple congruent points as candidate roads isolated island, so as to from the candidate roads isolated island
Middle determination road isolated island.
A kind of road isolated island determining device, including：
Road acquisition request unit is calculated, for obtaining multiple calculation road requests comprising starting point coordinate and terminal point coordinate,
The calculation road request holds up failed provide for calculation pass and asks the calculation road of road result to ask；
Polymerized unit, for by the starting point coordinate in multiple calculation roads requests, the coordinate points of terminal point coordinate
A point polymerization is carried out, multiple congruent points are obtained, using multiple congruent points as candidate roads isolated island, so as to from institute
State determination road isolated island in candidate roads isolated island.
It can be seen from above-mentioned technical scheme that, the road isolated island that the embodiment of the present application is provided determines method,
Multiple calculation road requests comprising starting point coordinate and terminal point coordinate are obtained, road request is calculated and is held up not successfully to calculate pass
Provide and ask the calculation road of road result to ask, the seat of starting point coordinate and terminal during further multiple calculation roads are asked
Punctuate carries out a point polymerization, obtains multiple congruent points, using multiple congruent points as candidate roads isolated island, so as to
Road isolated island is determined from the candidate roads isolated island.Failed provide is held up due to calculation pass and seeks road result
It is road isolated island to calculate at least one in road request, its starting point coordinate and terminal point coordinate, and the application will polymerize
Point is used as candidate roads isolated island, it is thus only necessary to carries out peripheral path connectedness to candidate roads isolated island and checks,
Road isolated island is determined whether it is, the query context of road isolated island is greatly reduced, compared to prior art
Road isolated island can fast and efficiently be determined.
Brief description of the drawings
, below will be to reality in order to illustrate more clearly of the embodiment of the present application or technical scheme of the prior art
The accompanying drawing used required for applying in example or description of the prior art is briefly described, it should be apparent that, below
Accompanying drawing in description is only embodiments herein, for those of ordinary skill in the art, not
On the premise of paying creative work, other accompanying drawings can also be obtained according to the accompanying drawing of offer.
Fig. 1 is that a kind of road isolated island disclosed in the embodiment of the present application determines method flow diagram；
Fig. 2 is that another road isolated island disclosed in the embodiment of the present application determines method flow diagram；
Fig. 3 is that another disclosed road isolated island of the embodiment of the present application determines method flow diagram；
Fig. 4 is a kind of R-Tree trees schematic diagram of the embodiment of the present application example；
Fig. 5 is a kind of R-Tree tree constructing methods flow chart of the embodiment of the present application example；
Fig. 6 is one kind disclosed in the embodiment of the present application to projection congruent point and labeled polymer number on electronic map
The method flow diagram of value；
Fig. 7-9 for the embodiment of the present application example electronic map under different zoom grade congruent point display effect
Figure；
Figure 10 is a kind of road isolated island determining device structural representation disclosed in the embodiment of the present application.
Embodiment
Below in conjunction with the accompanying drawing in the embodiment of the present application, the technical scheme in the embodiment of the present application is carried out
Clearly and completely describe, it is clear that described embodiment is only some embodiments of the present application, and
The embodiment being not all of.Based on the embodiment in the application, those of ordinary skill in the art are not doing
Go out the every other embodiment obtained under the premise of creative work, belong to the scope of the application protection.
Referring to Fig. 1, Fig. 1 is that a kind of road isolated island disclosed in the embodiment of the present application determines method flow diagram.
As shown in figure 1, this method includes：
Step S100, the multiple calculation roads requests comprising starting point coordinate and terminal point coordinate of acquisition, the calculation road please
Asking to hold up to provide not successfully for calculation pass asks the calculation road of road result to ask；
Specifically, user to calculate pass hold up transmission calculate road request, the calculation road request contain starting point coordinate and
Terminal point coordinate, request calculates pass and holds up the feasible route provided from starting point coordinate coordinate to terminal.Pass is calculated to hold up
Path computing is carried out according to starting point coordinate and terminal point coordinate, if there is the path for the condition that meets in road network,
Calculation pass, which is held up to provide, seeks road result, if the path for the condition that meets is not present in road network, calculates pass and holds up nothing
Method, which is successfully provided, seeks road result.
The calculation road request that the application is obtained is that calculation pass holds up failed provide and asks the calculation road of road result to ask.
Step S110, the coordinate points progress by starting point coordinate, terminal point coordinate in multiple calculation road requests
Point polymerization, obtains multiple congruent points, regard multiple congruent points as candidate roads isolated island.
Specifically, previous step acquires multiple calculation road requests, the starting point in being asked using multiple calculation roads
Coordinate and terminal point coordinate composition coordinate point set, and then point is carried out to each coordinate points in coordinate point set
Polymerization, obtains multiple congruent points.Existing aggregating algorithm can be used during point polymerization, such as based on distance
Point aggregating algorithm etc..
Holding up failed provide due to calculation pass asks the calculation road of road result to ask, its starting point coordinate and terminal point coordinate
In at least one be road isolated island, therefore the application regard multiple congruent points that a polymerization is obtained as candidate
Road isolated island, can subsequently determine road isolated island from candidate roads isolated island.
Determine that road isolated island can be done by staff from candidate roads isolated island, such as staff
The path connected checked near candidate roads isolated island, and then determine whether candidate roads isolated island is that road is lonely
Island.
The road isolated island that the embodiment of the present application is provided determines method, obtains multiple comprising starting point coordinate and terminal
The calculation road request of coordinate, calculation road request holds up failed provide for calculation pass and asks the calculation road of road result to ask, and enters
Starting point coordinate and the coordinate points of terminal point coordinate in the request of multiple calculation roads is carried out a point polymerization by one step, obtains many
Individual congruent point, using multiple congruent points as candidate roads isolated island, so as to true from the candidate roads isolated island
Determine road isolated island.Failed provide, which is held up, due to calculating pass asks the calculation road of road result ask, its starting point coordinate with
At least one in terminal point coordinate is road isolated island, the application using congruent point as candidate roads isolated island, only
Only need to check candidate roads isolated island progress peripheral path connectedness, determine whether it is road isolated island,
The query context of road isolated island is greatly reduced, can fast and efficiently be determined compared to prior art
Road isolated island.
Referring to Fig. 2, Fig. 2 is that another road isolated island disclosed in the embodiment of the present application determines method flow diagram.
As shown in Fig. 2 this method includes：
Step S200, acquisition calculate the serve log that pass is held up；
Specifically, starting point coordinate, the terminal of record You Meitiaosuan roads request in the serve log that pass is held up are calculated
Coordinate and seek road result.
User accesses calculation pass when needing to carry out Routing Service and held up, and submits comprising starting point coordinate and terminal
The calculation road request of coordinate.Calculation pass is held up carries out path computing according to the request of calculation road, and the every Tiao Suan roads of record are asked
Qiu Qiu roads result.Road result is asked there are two kinds, one kind is to ask road success, and another is to ask road to fail.
Step S210, filter out in the serve log calculation road request for seeking road result for failure；
Specifically, after sufficient amount of calculation road request is have accumulated in the serve log that calculation pass is held up, from
The calculation road request for seeking road result for failure is filtered out in serve log.
Step S220, the coordinate points progress by starting point coordinate, terminal point coordinate in multiple calculation road requests
Point polymerization, obtains multiple congruent points, regard multiple congruent points as candidate roads isolated island.
Specifically, road isolated island can be subsequently determined from the candidate roads isolated island.
The embodiment of the present application provides a kind of specific implementation for obtaining and calculating road request.That is, calculating road
The calculation road request for seeking road result for failure is filtered out in the serve log of engine.Certainly, in addition, originally
Application can also obtain the request of calculation road by third party's approach, to this application without considered critical.
Optionally, in the above-described embodiments, calculating in the serve log that pass is held up can also further record every
The request time of one Tiao Suan roads request.That is, calculating pass holds up the following information that have recorded and calculate road request：1、
Request time；2nd, road result is sought；3rd, starting point coordinate；4th, terminal point coordinate.
Based on this, above-mentioned steps S200 is obtained and is calculated the process of serve log that pass holds up and can be, according to
Request time, chooses the calculation road in target time section and asks.For example, obtain 2015.1.1-2016.1.1 it
Ask on Jian Suan roads.
Because map datum is continuous updating, therefore apart from current time Tai Jiusuan roads, request may be
Through failure, for the accuracy of algorithm, the application can be only obtained at request time with setting time scope
In time range Nei Suan roads request.
Referring to Fig. 3, Fig. 3 is that another disclosed road isolated island of the embodiment of the present application determines method flow diagram.
As shown in figure 3, this method includes：
Step S300, the multiple calculation roads requests comprising starting point coordinate and terminal point coordinate of acquisition, the calculation road please
Asking to hold up to provide not successfully for calculation pass asks the calculation road of road result to ask；
Specifically, user to calculate pass hold up transmission calculate road request, the calculation road request contain starting point coordinate and
Terminal point coordinate, request calculates pass and holds up the feasible route provided from starting point coordinate coordinate to terminal.Pass is calculated to hold up
Path computing is carried out according to starting point coordinate and terminal point coordinate, if there is the path for the condition that meets in road network,
Calculation pass, which is held up to provide, seeks road result, if the path for the condition that meets is not present in road network, calculates pass and holds up nothing
Method, which is successfully provided, seeks road result.
The calculation road request that the application is obtained is that calculation pass holds up failed provide and asks the calculation road of road result to ask.
Step S310, the coordinate points progress by starting point coordinate, terminal point coordinate in multiple calculation road requests
Point polymerization, obtains multiple congruent points, regard multiple congruent points as candidate roads isolated island；
Specifically, previous step acquires multiple calculation road requests, the starting point in being asked using multiple calculation roads
Coordinate and terminal point coordinate composition coordinate point set, and then point is carried out to each coordinate points in coordinate point set
Polymerization, obtains multiple congruent points.
Holding up failed provide due to calculation pass asks the calculation road of road result to ask, its starting point coordinate and terminal point coordinate
In at least one be road isolated island, therefore the application regard multiple congruent points that a polymerization is obtained as candidate
Road isolated island, can subsequently determine road isolated island from candidate roads isolated island.
Step S320, the polymerization numerical value for determining the congruent point, the polymerization numerical value represent that congruent point gathers
The number of the coordinate points of conjunction.
It is understood that when starting point is isolated island, the overwhelming majority calculates road failure and starting point is close
Request in, the terminal of user is all different.Similarly, when terminal is isolated island, overwhelming majority request
Starting point is different.Therefore, the polymerization numerical value of the congruent point obtained after polymerisation is also different.Polymerization
Numerical value is bigger, represents correspondence congruent point bigger as the possibility of road isolated island.Therefore, congruent point is passed through
Polymerization numerical value can further reduce the determination range of road isolated island, reduce the investigation workload of staff.
Further alternative, on the basis of above-described embodiment, the application can also project to congruent point
On electronic map, and the polymerization numerical value of congruent point is marked in electronic map.
By the way that polymerization result is showed on the electronic map, some regional polymerization occurs on electronic map
Numerical value is very big, and the situation of the fragmentary very little numerical value that is scattered in other places, and staff can filter out
It polymerize the larger congruent point of numerical value, and then according to the connectedness of congruent point peripheral path on electronic map, really
Whether be road isolated island, accelerate the speed that staff determines road isolated island if determining congruent point.
In another embodiment of the application, introduce to by the starting point coordinate in multiple calculation roads requests,
The coordinate points of terminal point coordinate carry out a kind of alternative of point polymerization.
Starting point coordinate and terminal point coordinate in the request of multiple calculation roads is constituted coordinate point set by the application；Enter one
Walk and the coordinate points in coordinate point set are carried out with multi-level polymerization, polymerization result composition space tree.
The level of space tree and the scalable grade of the engineer's scale of electronic map are corresponded, coordinate point set
In coordinate points and the leaf node of space tree correspond, the father node of any one node in space tree
For the congruent point obtained by being polymerize to its each child node, any one non-leaf nodes in space tree
Node all recorded polymerization numerical value, polymerization numerical value is all by the tree structure of root node of the node
The number of leaf node.
In embodiments of the present invention, space tree is preferably R-Tree trees, but is not limited to R-Tree trees, ginseng
It is a kind of R-Tree trees schematic diagram of the embodiment of the present application example to see Fig. 4, Fig. 4.
Assuming that the scalable number of degrees of the engineer's scale of electronic map is 3,5 coordinates are had in coordinate point set
Point, respectively A1-A5.
With reference to Fig. 4,5 coordinate points A1-A5 in coordinate point set as R-Tree trees first layer section
Point, namely leaf node.
To the A1-A5 of first layer, totally 5 nodes carry out a point converging operation, and node is obtained by A1-A3 polymerizations
A6；Node A7 is obtained by A4-A5 polymerizations.It is used as node A1-A3's in R-Tree tree interior joint A6
Father node, and node A6 polymerization numerical value is the leaf section in using node A6 as the tree structure of root node
The total number of point, node A6 polymerization numerical value F=3.Node A4-A5 is used as in R-Tree tree interior joint A7
Father node, and node A7 polymerization numerical value is the leaf in using node A7 as the tree structure of root node
The total number of node, node A7 polymerization numerical value F=2.
Node A6 and node A7 as R-Tree trees the second node layer.
To the A6 and A7 of the second layer, totally 2 nodes carry out a point converging operation, and node is obtained by A6 and A7 polymerizations
A8.In father nodes of the R-Tree tree interior joint A8 as node A6 and A7, and node A8 polymerization numerical value
For the total number of the leaf node in using node A8 as the tree structure of root node, node A8 polymerization numerical value
F=5.
Node A8 as R-Tree trees third layer node.
In summary, the scalable number of degrees of electronic map is identical with the number of levels of R-Tree trees, and one a pair
Should.The first level of the first zoom level correspondence R-Tree trees of electronic map；Second scaling of electronic map
The second level of grade correspondence R-Tree trees；The 3rd of the 3rd zoom level correspondence R-Tree trees of electronic map
Level.
Wherein, the first zoom level>Second zoom level>3rd zoom level, and zoom level bigger generation
Table electronic map multiplication factor is higher, and the cartographic information of display is more detailed.
Above-described embodiment describes and the coordinate points in coordinate point set is carried out with multi-level polymerization, polymerization knot
The structure of the R-Tree trees of fruit composition.Fig. 5 is may be referred to for the building process of R-Tree trees.
As shown in Figure 5：
Step S500, determine the electronic map engineer's scale scalable number of degrees；
Step S510, by the coordinate points in coordinate point set, be defined as point to be polymerized, point to be polymerized is true
It is set to the node of same layer in R-Tree trees；
Wherein, coordinate point set is made up of the starting point coordinate and terminal point coordinate in multiple calculation road requests.
Step S520, judge whether the number of levels of the R-Tree trees reaches the scalable number of degrees, if
It is to perform step S530, if it is not, performing step S540；
Step S530, terminate and export the R-Tree trees；
Step S540, to it is described it is to be polymerized point polymerize, obtain some congruent points, in R-Tree trees,
The congruent point is defined as to the father node of the node corresponding to the point to be polymerized that it is polymerize, and in father's section
Record polymerization numerical value in point；
Wherein, the polymerization numerical value is all leaf nodes using the father node as the tree structure of root node
Number.
Step S550, the congruent point is defined as to point to be polymerized, and returns to execution step S520.
Based on disclosed in above-described embodiment, the coordinate points in coordinate point set are carried out with multi-level polymerization,
The process of R-Tree trees is constituted using polymerization result, the present embodiment is further in above-described embodiment, by institute
State congruent point to project on electronic map, and the polymerization numerical value of congruent point is marked in electronic map
Process be introduced.
Referring to Fig. 6, Fig. 6 is one kind disclosed in the embodiment of the present application to projection congruent point on electronic map and marked
The method flow diagram of note polymerization numerical value.
As shown in fig. 6, the process includes：
Step S600, determine the electronic map engineer's scale current zoom number of degrees；
Specifically, above-described embodiment have been described above electronic map engineer's scale there may be it is multiple scaling etc.
The current zoom number of degrees of the engineer's scale of electronic map is determined in level, this step.
Step S610, according to the current zoom number of degrees, determine corresponding layer in the R-Tree trees
Level；
The different zoom grade for having been described above the engineer's scale of electronic map above exists in R-Tree trees
Corresponding level, therefore layer corresponding with the current zoom number of degrees in R-Tree trees is determined in this step
Level.
Step S620, the node of the corresponding level of determination projected on the electronic map, and in electricity
The polymerization numerical value of mark projection node in sub- map.
Specifically, under electronic map current zoom grade, the node of the corresponding level of determination is projected to
Correspondence position on electronic map, and mark projects the polymerization numerical value of node in electronic map.
According to the projecting method of the present embodiment, staff can control the zoom level of electronic map,
It can be seen that different congruent point and polymerization numerical value on the electronic map of different zoom grade.
Gather referring to Fig. 7-9, Fig. 7-9 for the electronic map of the embodiment of the present application example under different zoom grade
Chalaza display renderings.
Wherein, Fig. 7 be the 3rd zoom level under display effect, Fig. 8 be the second zoom level under show effect
Really, Fig. 9 is display effect under the first zoom level.
Staff is under the first zoom level it can be seen that the polymerization result of each national emphasis provinces and cities, gathers
The polymerization numerical value of chalaza is bigger, and to represent the possibility comprising road isolated island under the province higher, conversely, representing
The possibility comprising road isolated island is lower under the province.
Lift for example, staff's selection Guangzhou is amplified, under the second zoom level, Fig. 8 is positioned
" the Poly Dong Jiang provincial capital " under to Guangzhou, the polymerization numerical value of the point is 11, and representing polymerization under the point has
11 coordinate points.
Further " the Poly Dong Jiang provincial capital " is amplified, the display effect under the 3rd zoom level is such as
Fig. 9.Black penoncel filial generation table coordinate points in Fig. 9.Staff can be attached to each coordinate points in fig .9
Near path connected is checked, and then determines whether coordinate points are road isolated island.
In summary, staff can choose polymerization numerical value in the electronic map under minimum amplification stage
Amplified step by step more than the congruent point of threshold value, and then to the congruent point, until navigating to maximum zoom etc.
Whether coordinate points in the lower electronic map of level, it is road isolated island to judge the coordinate points.It is low for polymerization numerical value
In the congruent point of threshold value, the application assert that it does not include road isolated island, enters without being investigated to it, subtracts
The screening operation amount of road isolated island is lacked.
The road isolated island determining device that the embodiment of the present application is provided is described below, road described below
Road isolated island determining device determines that method can be mutually to should refer to above-described road isolated island.
Referring to Figure 10, Figure 10 is a kind of road isolated island determining device structural representation disclosed in the embodiment of the present application
Figure.
As shown in Figure 10, the device includes：
Road acquisition request unit 10 is calculated, please for obtaining multiple calculation roads comprising starting point coordinate and terminal point coordinate
Ask, the calculation road request holds up failed provide for calculation pass and asks the calculation road of road result to ask；
Polymerized unit 11, for by starting point coordinate, the coordinate of terminal point coordinate in multiple calculation roads requests
Point carries out a point polymerization, obtains multiple congruent points, using multiple congruent points as candidate roads isolated island, so as to from
Road isolated island is determined in the candidate roads isolated island.
The road isolated island determining device that the embodiment of the present application is provided, obtains multiple by calculating road acquisition request unit
Calculation road request comprising starting point coordinate and terminal point coordinate, calculation road request holds up failed provide for calculation pass and asks road
As a result calculation road request, by polymerized unit by multiple calculation roads ask in starting point coordinate and terminal point coordinate seat
Punctuate carries out a point polymerization, obtains multiple congruent points, using multiple congruent points as candidate roads isolated island, so as to
Road isolated island is determined from the candidate roads isolated island.Failed provide is held up due to calculation pass and seeks road result
It is road isolated island to calculate at least one in road request, its starting point coordinate and terminal point coordinate, and the application will polymerize
Point is used as candidate roads isolated island, it is thus only necessary to carries out peripheral path connectedness to candidate roads isolated island and checks,
Road isolated island is determined whether it is, the query context of road isolated island is greatly reduced, compared to prior art
Road isolated island can fast and efficiently be determined.
Optionally, above-mentioned calculation road acquisition request unit can include：
Serve log acquiring unit, the serve log that pass is held up is calculated for obtaining, and is remembered in the serve log
Record the starting point coordinate asked on You Meitiaosuan roads, terminal point coordinate and seek road result；
Road request screening unit is calculated, for filtering out the calculation for seeking road result for failure in the serve log
Ask on road.
Optionally, the road isolated island determining device of the application can also include：
It polymerize numerical value determining unit, the polymerization numerical value for determining the congruent point, the polymerization numerical tabular
Show the number for the coordinate points that congruent point is polymerize.
Optionally, the road isolated island determining device of the application can also include：
Projecting cell, for the congruent point to be projected into electronic map, and by the aggregate number of congruent point
Value is marked in electronic map.
Optionally, above-mentioned polymerized unit can include：
First polymerization subelement, for by the starting point coordinate and terminal point coordinate in multiple calculation road requests
Coordinate points in the coordinate point set of composition carry out multi-level polymerization, polymerization result composition space tree；
The level of the space tree and the scalable grade of the engineer's scale of the electronic map are corresponded, and are sat
The leaf node of coordinate points and space tree in punctuate set is corresponded, any one node in space tree
Father node be congruent point obtained by being polymerize to its each child node, any one in space tree is non-
The node of leaf node has all recorded polymerization numerical value, and polymerization numerical value is the tree-like knot by root node of the node
The number of all leaf nodes of structure.
Based on the space tree obtained by the first polymerization subelement, above-mentioned projecting cell can include：
First projection subelement, the current zoom number of degrees of the engineer's scale for determining the electronic map；
Second projection subelement, for according to the current zoom number of degrees, being determined in the space tree
Corresponding level；
3rd projection subelement, for the node of the corresponding level of determination to be projected into the electronic map
On, and mark projects the polymerization numerical value of node in electronic map.
Finally, in addition it is also necessary to explanation, herein, such as first and second or the like relational terms
It is used merely to make a distinction an entity or operation with another entity or operation, and not necessarily requires
Or imply between these entities or operation there is any this actual relation or order.Moreover, art
Language " comprising ", "comprising" or any other variant thereof is intended to cover non-exclusive inclusion, so that
So that process, method, article or equipment including a series of key elements not only include those key elements, and
Also include other key elements for being not expressly set out, or also include for this process, method, article or
The intrinsic key element of person's equipment.In the absence of more restrictions, by sentence "including a ..."
The key element of restriction, it is not excluded that also deposited in the process including the key element, method, article or equipment
In other identical element.
The embodiment of each in this specification is described by the way of progressive, and each embodiment is stressed
Be between the difference with other embodiment, each embodiment identical similar portion mutually referring to.
The foregoing description of the disclosed embodiments, enables professional and technical personnel in the field to realize or use
The application.A variety of modifications to these embodiments will be aobvious and easy for those skilled in the art
See, generic principles defined herein can in the case where not departing from spirit herein or scope,
Realize in other embodiments.Therefore, the application is not intended to be limited to the embodiments shown herein,
And it is to fit to the most wide scope consistent with features of novelty with principles disclosed herein.
Claims (10)
1. a kind of road isolated island determines method, it is characterised in that including：
Multiple calculation road requests comprising starting point coordinate and terminal point coordinate are obtained, the calculation road request is to calculate pass
Holding up failed provide asks the calculation road of road result to ask；
Starting point coordinate in multiple calculation road requests, the coordinate points of terminal point coordinate are subjected to point polymerization, obtained
To multiple congruent points, using multiple congruent points as candidate roads isolated island, so as to from the candidate roads isolated island
Middle determination road isolated island.
2. according to the method described in claim 1, it is characterised in that described to obtain multiple comprising starting point seat
The calculation road of mark and terminal point coordinate is asked, including：
Obtain and calculate the serve log that pass is held up, the starting point of record You Meitiaosuan roads request in the serve log
Coordinate, terminal point coordinate and seek road result；
The calculation road request for seeking road result for failure is filtered out in the serve log.
3. according to the method described in claim 1, it is characterised in that described to ask multiple calculation roads
In starting point coordinate, terminal point coordinate coordinate points carry out point a polymerization, including：
To being carried out at many levels by the starting point coordinate and the coordinate points of terminal point coordinate in multiple calculation road requests
Polymerization, polymerization result composition space tree；
The level of the space tree and the scalable grade of the engineer's scale of the electronic map are corresponded, and are sat
The leaf node of coordinate points and space tree in punctuate set is corresponded, any one node in space tree
Father node be congruent point obtained by being polymerize to its each child node, any one in space tree is non-
The node of leaf node has all recorded polymerization numerical value, and polymerization numerical value is the tree-like knot by root node of the node
The number of all leaf nodes of structure.
4. method according to claim 3, it is characterised in that also include：
The congruent point is projected on electronic map, and by the polymerization numerical value of congruent point in electronic map
It is marked.
5. method according to claim 4, it is characterised in that described to project to the congruent point
On electronic map, and the polymerization numerical value of congruent point is marked in electronic map, including：
Determine the current zoom number of degrees of the engineer's scale of the electronic map；
According to the current zoom number of degrees, corresponding level is determined in the space tree；
The node of the corresponding level of determination is projected on the electronic map, and in electronic map acceptance of the bid
The polymerization numerical value of note projection node.
6. a kind of road isolated island determining device, it is characterised in that including：
Road acquisition request unit is calculated, for obtaining multiple calculation road requests comprising starting point coordinate and terminal point coordinate,
The calculation road request holds up failed provide for calculation pass and asks the calculation road of road result to ask；
Polymerized unit, for by the starting point coordinate in multiple calculation roads requests, the coordinate points of terminal point coordinate
A point polymerization is carried out, multiple congruent points are obtained, using multiple congruent points as candidate roads isolated island, so as to from institute
State determination road isolated island in candidate roads isolated island.
7. device according to claim 6, it is characterised in that the calculation road acquisition request unit bag
Include：
Serve log acquiring unit, the serve log that pass is held up is calculated for obtaining, and is remembered in the serve log
Record the starting point coordinate asked on You Meitiaosuan roads, terminal point coordinate and seek road result；
Road request screening unit is calculated, for filtering out the calculation for seeking road result for failure in the serve log
Ask on road.
8. device according to claim 6, it is characterised in that the polymerized unit includes：
First polymerization subelement, for by the starting point coordinate and terminal point coordinate in multiple calculation road requests
Coordinate points carry out multi-level polymerization, polymerization result composition space tree；
The level of the space tree and the scalable grade of the engineer's scale of the electronic map are corresponded, and are sat
The leaf node of coordinate points and space tree in punctuate set is corresponded, any one node in space tree
Father node be congruent point obtained by being polymerize to its each child node, any one in space tree is non-
The node of leaf node has all recorded polymerization numerical value, and polymerization numerical value is the tree-like knot by root node of the node
The number of all leaf nodes of structure.
9. device according to claim 8, it is characterised in that also include：
Projecting cell, for the congruent point to be projected into electronic map, and by the aggregate number of congruent point
Value is marked in electronic map.
10. device according to claim 9, it is characterised in that the projecting cell includes：
First projection subelement, the current zoom number of degrees of the engineer's scale for determining the electronic map；
Second projection subelement, for according to the current zoom number of degrees, being determined in the space tree
Corresponding level；
3rd projection subelement, for the node of the corresponding level of determination to be projected into the electronic map
On, and mark projects the polymerization numerical value of node in electronic map.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201610183449.5A CN107239461B (en) | 2016-03-28 | 2016-03-28 | Road island determination method and device |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201610183449.5A CN107239461B (en) | 2016-03-28 | 2016-03-28 | Road island determination method and device |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN107239461A true CN107239461A (en) | 2017-10-10 |
| CN107239461B CN107239461B (en) | 2020-08-07 |
Family
ID=59983114
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201610183449.5A Active CN107239461B (en) | 2016-03-28 | 2016-03-28 | Road island determination method and device |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN107239461B (en) |
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN111861673A (en) * | 2020-07-28 | 2020-10-30 | 滴图(北京)科技有限公司 | Data processing method, apparatus, readable storage medium and electronic device |
| CN112667758A (en) * | 2020-12-17 | 2021-04-16 | 佳都新太科技股份有限公司 | Interest point aggregation method, map aggregation display method and processing terminal |
| CN119849080A (en) * | 2025-03-17 | 2025-04-18 | 浙江大华系统工程有限公司 | Road network construction method and device |
Citations (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5519619A (en) * | 1994-03-14 | 1996-05-21 | Motorola, Inc. | Route planning method for hierarchical map routing and apparatus therefor |
| CN101750089A (en) * | 2008-12-11 | 2010-06-23 | 北京四维图新科技股份有限公司 | Road network connectivity detection method and device based on mass e-maps |
| CN103632532A (en) * | 2012-08-22 | 2014-03-12 | 北京掌城科技有限公司 | Taxi taxi-taking inducing method |
| CN104422461A (en) * | 2013-09-06 | 2015-03-18 | 上海博泰悦臻电子设备制造有限公司 | Path acquisition method and navigation method of navigation system |
| CN104583722A (en) * | 2012-06-29 | 2015-04-29 | 通腾发展德国公司 | Apparatus and method for route searching |
| CN105335393A (en) * | 2014-07-11 | 2016-02-17 | 阿里巴巴集团控股有限公司 | Map display method and device |
-
2016
- 2016-03-28 CN CN201610183449.5A patent/CN107239461B/en active Active
Patent Citations (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5519619A (en) * | 1994-03-14 | 1996-05-21 | Motorola, Inc. | Route planning method for hierarchical map routing and apparatus therefor |
| CN101750089A (en) * | 2008-12-11 | 2010-06-23 | 北京四维图新科技股份有限公司 | Road network connectivity detection method and device based on mass e-maps |
| CN104583722A (en) * | 2012-06-29 | 2015-04-29 | 通腾发展德国公司 | Apparatus and method for route searching |
| CN103632532A (en) * | 2012-08-22 | 2014-03-12 | 北京掌城科技有限公司 | Taxi taxi-taking inducing method |
| CN104422461A (en) * | 2013-09-06 | 2015-03-18 | 上海博泰悦臻电子设备制造有限公司 | Path acquisition method and navigation method of navigation system |
| CN105335393A (en) * | 2014-07-11 | 2016-02-17 | 阿里巴巴集团控股有限公司 | Map display method and device |
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN111861673A (en) * | 2020-07-28 | 2020-10-30 | 滴图(北京)科技有限公司 | Data processing method, apparatus, readable storage medium and electronic device |
| CN112667758A (en) * | 2020-12-17 | 2021-04-16 | 佳都新太科技股份有限公司 | Interest point aggregation method, map aggregation display method and processing terminal |
| CN119849080A (en) * | 2025-03-17 | 2025-04-18 | 浙江大华系统工程有限公司 | Road network construction method and device |
| CN119849080B (en) * | 2025-03-17 | 2025-06-06 | 浙江大华系统工程有限公司 | A road network construction method and device |
Also Published As
| Publication number | Publication date |
|---|---|
| CN107239461B (en) | 2020-08-07 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN113822190B (en) | A factory road network data fitting method, device, electronic equipment and storage medium | |
| CN109859525B (en) | Parking Navigation Method Based on A-Star Algorithm | |
| CN107239461A (en) | A kind of road isolated island determines method and device | |
| CN107423455B (en) | Automatic modeling method and system for highway | |
| CN105444735A (en) | Road grade determining method and device | |
| CN113095697B (en) | Urban marginal zone three-generation space evaluation analysis method, system, equipment and medium | |
| CN111460986A (en) | Lane line processing method and device | |
| CN107543553A (en) | A kind of point of interest update method and device | |
| CN113984062A (en) | A ground vehicle path planning method based on mobility assessment | |
| CN108257384A (en) | A kind of robustness of road network veneziano model determines method and system | |
| CN118116193A (en) | A comprehensive transportation accessibility measurement method based on multi-scale cross-regional | |
| CN113779430A (en) | Road network data generation method and device, computing equipment and storage medium | |
| CN114723316B (en) | Reachability evaluation method and system for urban public facilities based on GIS | |
| CN114254060A (en) | Space matching method and system for urban road and public transport line | |
| CN113158314B (en) | Slope stability analysis method | |
| CN116150296A (en) | Road network skeleton generation method and device, electronic equipment and storage medium | |
| CN110188152A (en) | Electronic map road information processing method and device, electronic equipment, readable medium | |
| CN111369102A (en) | Method and device for extracting waterlogging risk points | |
| CN117273476A (en) | Green road line selection method, device, electronic equipment and medium | |
| CN115712970A (en) | Method and system for analyzing influence of pipe network model generalization degree on parameter sensitivity and model precision and storage medium | |
| CN111199357B (en) | Express delivery point electronic fence diagnosis method and device | |
| JP3525619B2 (en) | Method and apparatus for automatically generating road network information | |
| CN107886570A (en) | A kind of visible range computational methods for taking into account precision and efficiency | |
| CN117312396A (en) | Lane positioning method and device, electronic equipment and readable storage medium | |
| CN114676996A (en) | Method, device, equipment and medium for measuring the correlation between road network form and industrial layout |
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 | ||
| TA01 | Transfer of patent application right | ||
| TA01 | Transfer of patent application right |
Effective date of registration: 20200507 Address after: 310052 room 508, floor 5, building 4, No. 699, Wangshang Road, Changhe street, Binjiang District, Hangzhou City, Zhejiang Province Applicant after: Alibaba (China) Co.,Ltd. Address before: 100080 Beijing City, Haidian District Suzhou Street No. 3 floor 16 room 2 Applicant before: AUTONAVI INFORMATION TECHNOLOGY Co.,Ltd. |
|
| GR01 | Patent grant | ||
| GR01 | Patent grant |