Method and apparatus for determining a road network partitioning border line

Patent metadata

Field	Value
Publication number	US-10169529-B2
Application number	US-201514944299-A
Country	US
Kind code	B2
Filing date	Nov 18, 2015
Priority date	Nov 28, 2014
Publication date	Jan 1, 2019
Grant date	Jan 1, 2019

Abstract

Embodiments of the present invention disclose a technical solution of determining a border between road network partitions, comprising: determining a border point based on road network data and partitioning information of road segments in the road network; determining a buffer zone between adjacent partitions based on the border point, the partitioning information of the road segments, and the road network data; determining a border between the adjacent partitions based on the buffer zone. With the solution of the present invention, border lines for road network partitions can be accurately determined.

First claim

What is claimed is:

1. A computer implemented method for determining a road network partitioning border line, comprising:
determining a border point based on road network data;
determining a buffer zone between adjacent partitions based on the border point, partitioning information of road segments in a road network, and the road network data;
determining a border line segment between the adjacent partitions based on the buffer zone; and
determining a border line of at least one partition based on the border line segment.

2. The computer implemented method according to claim 1 , wherein the determining a buffer zone comprises:
selecting the border point as a start point, and determining an initial road segment based on the start point;
proceeding to a next road segment along a preset direction based on the initial road segment, till proceeding to the initial road segment; and
determining the buffer zone based on the initial road segment as traversed.

3. The computer implemented method according to claim 2 ,
wherein the determining border points based on road network data comprises:
for each node in the road network, determining partition information of a road segment connected to the node based on the road network data and partitioning information of road segments in the road network; and
if the road segments connected to the node belong to different partitions, determining the node as a first kind of border points,

wherein the selecting a border point as a start point and determining an initial road segment based on the start point comprises:
selecting one of the first kind of border points and determining all road segments connected to the one of the first kind of border points and partitioning information of all road segments;
determining a sector area formed by road segments corresponding to each partition among all road segments connected to the one of the first kind of border points, and determining an outer side road segment forming an edge of the sector area; and
determining the initial road segment based on the outer side road segment.

4. The computer implemented method according to claim 2 ,
wherein the determining a border point based on road network data comprises:
determining an envelope of the road network based on the road network data; and
determining nodes situated on the envelope of the road network as a second kind of border points,

wherein the selecting a border point as a start point and determining an initial road segment based on the start point comprises: selecting two of the second kind of border points that are adjacent but belong to different partitions, and determining a road segment connecting the two of the second kind of border points as the initial road segment.

5. The computer implemented method according to claim 1 , wherein the determining a border line segment between the adjacent partitions based on the buffer zone comprises:
performing a triangular partition to the buffer zone; and
determining the border line segment based on the border point and a central point of respective triangular areas after the triangular partition.

6. The computer implemented method according to claim 1 , wherein the determining a border line segment between the adjacent partitions based on the buffer zone comprises:
determining a plurality of pairs of nodes, nodes in the pairs of nodes belonging to different partitions; and
determining a border line segment based on middle points of connection lines of the pairs of nodes and the border point.

7. The computer implemented method according to claim 1 , wherein the determining a border line segment between the adjacent partitions based on the buffer zone comprises:
extending, within the buffer zone, a angle bisector of an interior angle where a border point of the buffer zone is located to interact with a border of the buffer zone, to thereby form a first line segment;
starting, from a middle point of the first line segment, to connect to another border node to form a connection line;
if the connection line is not intersected in the buffer zone with the border of the buffer zone, determining the border line segment based on the connection lines; and
if the connection line is intersected in the buffer zone with the border of the buffer zone to form a second line segment, taking the second line segment as the first line segment to continue the above mentioned steps.

8. The computer implemented method according to claim 1 , further comprising:
storing road network data of at least one road network partition in each server; and
in response to receiving a request containing location information, assigning the request to a corresponding server based on a border line of respective partition.

9. A system for determining a road network partitioning border line, the system having a processor in communication with a memory, the processor comprising:
a border point determining module configured to determine a border point based on road network data;
a buffer zone determining module configured to determine a buffer zone between adjacent partitions based on the border point, partitioning information of road segments in a road network, and the road network data;
a border line segment determining module configured to determine a border line segment between the adjacent partitions based on the buffer zone; and
a border line determining module configured to determine a border line of at least one partition based on the border line segment.

10. The system according to claim 9 , the buffer zone determining module comprises:
a module configured to select the border point as a start point, and determine an initial road segment based on the start point;
a module configured to proceed to a next road segment along a preset direction based on the initial road segment, till proceeding to the initial road segment; and
a module configured to determine the buffer zone based on the initial road segment as traversed.

11. The system according to claim 10 ,
wherein the border point determining module comprises:
a module configured to, for each node in the road network, determine partition information of a road segment connected to the node based on the road network data and partitioning information of road segments in the road network; and
a module configured to, if the road segment connected to the node has different partitions, determine the node as a first kind of border points,

wherein the module configured to select a border point as a start point, and determine an initial road segment based on the start point comprises:
a module configured to select one of the first kind of border points and determine all road segments connected to the one of the first kind of border points and partitioning information of all road segments;
a module configured to determine a sector area formed by road segments corresponding to each partition among all road segments connected to the one of the first kind of border points, and to determine an outer side road segment forming an edge of the sector area; and
a module configured to determine the initial road segment based on the outer side road segment.

12. The system according to claim 10 ,
wherein the border point determining module comprises:
a module configured to determine an envelope of the road network based on the road network data; and
a module configured to determine nodes situated on the envelope of the road network as a second kind of border points,

wherein the module configured to select a border point as a start point and determine an initial road segment based on the start point comprises: a module configured to select two of t

Assignees

• IBM

Inventors

• Dong Wei Shan
• Duan Ning
• Gao Peng
• Hu Guoqiang
• Zhang Xin

Classifications

• G06F30/18

  Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling (circuit design at the physical level G06F30/39; network planning tools for wireless communication networks H04W16/18) · CPC title

• G06F17/509 Primary

  Physics · mapped topic

• G01C21/32

  Structuring or formatting of map data · CPC title

• G01C21/3867

  Geometry of map features, e.g. shape points, polygons or for simplified maps · CPC title

• G01C21/3815 Primary

  Road data · CPC title