Road splitting in a map editor

A method and system for editing map data by automatically splitting a road segment into a pair of road segments while maintaining the proper attributes and directionality for each road segment. A road segment that has two directions of travel is selected for splitting. A new road segment is instantiated to represent one of the directions of travel. A direction of travel is assigned to both of the road segments. Attributes that are common to both directions of travel are copied to the new road segment. Attributes that are only associated with the direction of travel of the new road segment are migrated to the new road segment.

FIELD OF THE INVENTION

The present invention relates to map editing and more specifically to a map editor configured for automatically splitting a road segment into a pair of road segments while maintaining the proper attributes and directionality for each road segment.

BACKGROUND OF THE INVENTION

Digital maps are found in a wide variety of devices, including car navigation systems, hand-held GPS units, mobile phones, and also in many websites such as GOOGLE MAPS and MAPQUEST. Although digital maps are easy to use from an end-user's perspective, creating a digital map is a difficult and time-consuming process. Every digital map begins with a set of raw data representing millions of streets and intersections. The raw map data is derived from a variety of sources, each source providing different amounts and types information. In many cases, data from different sources is inaccurate and out of date. Oftentimes the data from the different sources is in a format which is not suitable for use in a real map. Integrating data from these heterogeneous sources so that it can be used and displayed properly is an enormous challenge.

In particular, many sources of map data use a very simple representation of two-way roads. These data sources treat a two-way road as a series of bi-directional road segments. However, in the real world, each two way street may have multiple lanes traveling in opposite directions that can at times be separated by hundreds of feet. In addition, each direction of travel may have its own road attributes, such as addresses, speed restrictions, and the like. Using a single road segment to represent two way roads in digital maps can thus lead to inaccurate maps. For example, if a single bi-directional road segment is overlaid onto a satellite image of a divided highway, the resulting map would be inaccurate because the road segment would be appear to sit on top of the median instead of on the highway itself.

SUMMARY OF THE INVENTION

A map editing system and method is configured to automatically split a road segment into a pair of road segments while maintaining the proper attributes and directionality for each road segment. A map editor displays road segments in a visual map to a user. The user selects a road segment that corresponds to a two-way road to be split using the map editor. The map editor instantiates a new road segment in the database, thus resulting in two road segments for the road. The map editor assigns the correct direction of travel to both of the road segments so that each road segment has a direction of travel that corresponds to a different direction of travel of the road. Attributes that are common to both directions of travel for the road are copied to the new road segment. Attributes that correspond to the direction of travel of the new road segment are copied to the new road segment and deleted from the original road segment. As a result, a single road segment can quickly be split into two separate road segments, increasing the accuracy of the map generated from the map data and reducing the time needed to process the raw map data.

The map editor can also be used to split one-way road segments. The user first selects a road segment that corresponds to lanes of a road that have one direction of travel. The map editor instantiates a new road segment in the database, thus resulting in two road segments for the road. The map editor assigns the correct direction of travel to the new road segment so that both road segments have the same direction of travel. The attributes of the original road segment are then copied to the new road segment.

In one embodiment, the road segments have nodes that define the endpoints of the road segments, and the nodes of the road segment are positioned so that it appears as if each road segment is being divided into two geometrically similar separate road segments. The map editor can receive a user input adjusting the distance between the road segments, which causes the map editor to update the placement of the road segments in the database. Additionally, the map editor configures the geometry of the new road segment so that it is based on the geometry of the original road segment. Furthermore, the map editor can receive a user input indicating that the split road segments intersect with another road. The map editor then instantiates a new road segment at the location of the intersection to connect the split road segments. Finally, after one segment is split, the map editor can automatically identify another segment of the same road to be split. These features help to facilitate fast processing of thousands of different road segments while maintaining the accuracy of the post-processed data.

DETAILED DESCRIPTION OF THE INVENTION

System Overview

FIG. 1is a high-level block diagram that illustrates a computing environment for a map editor, according to one embodiment of the present disclosure. A shown inFIG. 1, the computing environment includes a server105connected to a number of client computers115through network125. The network includes but is not limited to any combination of a LAN, MAN, WAN, mobile, wired or wireless network, a private network, or a virtual private network. While only three clients are shown to simplify and clarify the description, it is understood that very large numbers of client computers are supported and can be in communication with the server105.

Both the server105and the clients115are computers that comprise a CPU, memory, network interface, peripheral interfaces, and other well known components. As is known to one skilled in the art, other types of computers can be used which have different architectures. The server105and the client115are also adapted to execute computer program modules for providing functionality described herein. As used herein, the term “module” refers to computer program logic used to provide the specified functionality. Thus, a module can be implemented in hardware, firmware, and/or software. In one embodiment, program modules are stored in on a storage device, loaded into memory, and executed by a processor or can be provided from computer program products that are stored in tangible computer-readable storage mediums (e.g. RAM, hard disk, or optical/magnetic media).

A map data database110is illustrated as being stored in server105. Alternatively, many other configurations are possible. The database110does not need to be physically located within server105. For example, the database can be placed within client115, stored in external storage attached to server105, or stored in network attached storage. Additionally, there may be multiple servers105that connect to a single database110.

The database110contains map data that can be used to generate a digital road map. Physical roads are represented in the map data by a list of nodes and road segments which connect those nodes. Each node corresponds to a specific geographic location in the physical world. Each road segment corresponds to a section of a physical road that begins at one node and ends at a different node. The map data can be obtained from several different sources such as OASIS and TIGER. The map data can also be accessed by map editor120, modified, and stored back into the database110.

The client115executes map editor120, which allows a user to modify the map data stored in map data database110, for example in the process of creating a digital map. The map editor is configured to store map data to database110. The data is visually displayed to a user as a set of nodes and road segments connecting those nodes. The user selects a segment of the road that represents a two-way road. The map editor then instantiates a new segment, assigns the appropriate directionality to the segments, and then allocates the appropriate attributes to each segment. Further, the map editor can determine if any other road segments intersect with the split segments. If so, an additional road segment can be instantiated at the location of the intersection to connect the split road segments. To facilitate fast processing of additional segments, the editor also automatically identifies another segment for splitting.

Road Splitting with the Map Editor

Turning now toFIG. 2, illustrated is a high level block diagram illustrating modules within a map editor according to one embodiment. As illustrated, the map editor120includes a database interface module205, a segment selection module210, a node splitting module215, a segment splitting module220, an intersection connection module225, a next segment identification module230, and an output module235. Some embodiments of the map editor120have different and/or other modules than the ones described herein. Similarly, the functions described herein can be distributed among the modules in accordance with other embodiments in a different manner than is described here. The detailed operation of these modules is next explained by reference toFIG. 3, which shows a flow diagram of a process for splitting road segments.

The database interface module205stores305and retrieves map data to and from the database110. As discussed above, physical roads in the real world are represented in the map data as nodes and road segments that connect those nodes. Each node corresponds to a specific geographical location in the real world. The data representation for each node includes positional coordinates (e.g. latitude and longitude). The data representation for each node also includes a list of the road segments that are connected to the node.

Each of the road segments corresponds to a length of a road that has either one or two directions of travel. The data representation for each road segment includes an association with two nodes. The nodes mark the beginning and ending of each road segment. The data representation for each road segment also includes an ordered list of positional coordinates (e.g. latitude and longitude) that are used to re-create the geometry of the road segment, such as whether the road segment is straight or curved.

The data representation for each road segment further includes various sets of attributes that describe features of the road. One set of attributes (“non-directional” attributes) is common to both directions of travel of the road. A second set of attributes represents the features of one of the two directions of travel. A third set of attributes represents the features of the other direction of travel. The second and third sets of attributes are “directional” attributes because they represent features for only one direction of travel.

Attributes that are common to both directions of travel of a road include those attributes that describe the general characteristics of the road. Examples of common attributes are listed below:Surface type (e.g. paved, gravel, dirt)Priority (e.g. non-traffic, local road, minor arterial, major arterial, secondary, primary highway, limited access highway, controlled access highway)Speed information (e.g. speed limit, recommended speed)Usage (e.g. ramp, roundabout, trail)Median widthRoad width

Attributes that are associated only with a single direction of travel include the following attributes:Street nameStreet number or range of street numbersP.O Box rangePolitical feature (e.g. county, state, province, civil division, locality, neighborhood)Turn restrictionsNumber of lanes

Thus, the data representation for each road segment includes three sets of attributes. One set of attributes corresponds to both directions of travel of the road (“non-directional” attributes). A second set of attributes corresponds to one direction of travel, and a third set of attributes corresponds to the other, opposing direction of travel (“directional attributes”). For ease of understanding, the following table illustrates three sets of attributes that are associated with a road segment:

Each set of directional attributes is also associated with a target node. The target node is used to determine the precise direction of travel that a set of attributes corresponds to. For example, suppose that a road segment exists between two nodes, node A and node B. The first set of attributes is common to both directions of travel and does not have a target node. The second set of attributes can be associated with node A as the target node. These attributes correspond to lanes of a road carrying traffic from node B to node A. The third set of attributes can be associated with node B as the target node. These attributes correspond to lanes of a road carrying traffic from node A to node B.

To distinguish between one-way and two-way roads segments, each set of directional attributes is marked as corresponding to either an allowed or disallowed direction of travel. If only one of the two sets of directional attributes is marked as corresponding to an allowed direction of travel, then the road is a one-way road segment. If both sets of directional attributes are marked as corresponding to an allowed direction of travel, the road is a two-way road segment. For example, suppose again that a road segment exists between node A and node B. The set of attributes associated with target node B is marked as corresponding to a disallowed direction of travel. The set of attributes associated with target node A is marked as corresponding to an allowed direction of travel. This configuration results in a one-way road segment leading from Node B to Node A.

Next, the segment selection module210displays308the nodes and road segments in the form of a visual map to a user. The visual map can also include a satellite image of the area surrounding the displayed segments. For example,FIG. 4aillustrates a set of nodes and road segments as displayed in a visual map. There is one main road405made up of several nodes and segments that runs from the bottom left hand corner of the figure to the upper right hand corner of the figure. The road also intersects with other road segments410and415. Although not shown in the figure, it is also possible to visually display the directionality of the road segments with graphical indicators such as arrows.

The segment selection module210receives310a user input selecting a road segment having two directions of travel for splitting, which is then highlighted in the display. For example,FIG. 5aillustrates a schematic view of a set of nodes and road segments that are displayed in a visual map. In this figure, two roads are shown intersecting at a T intersection502. The first road is displayed vertically as a single road segment504. The second road is displayed horizontally as a series of road segments, including segments506and508. Road segment506is a two-way road segment that exists between node510and node512. The user has selected a road segment506for splitting, which is here shown as a thicker line for ease of identification.

Next, the node splitting module215instantiates315two new nodes in the database. The node splitting module configures the coordinates of the newly instantiated nodes and the nodes of the originally selected road segment (“selected nodes”) so that it appears as if each of the selected nodes is being divided into two separate nodes. One node appears to be pulled in a direction that is orthogonal to the originally selected segment. The other node appears to be pulled in the direct opposite direction. For example, referring toFIG. 5b, illustrated is a schematic representation of a road where the nodes and road segments have been split. The segment splitting module215instantiates two new nodes530and532. The positional coordinates are also configured so that both new nodes530,532are located to the South of the original position560of the selected road segment. The node splitting module also shifts the position of the selected nodes510,512so that they are located to the North of the original position560of the selected road segment. As a result, it appears as if each of the selected nodes510and512is being divided into two separate nodes. It appears as if node510is being divided into nodes510and530, and it appears as if node512is being divided into nodes512and532. Additionally, the positional coordinates are configured so that the distance562between the new nodes530and532is equal to the distance between the selected nodes510and512.

The positional coordinates of the newly instantiated nodes and the selected nodes can be set so that the distance between the new nodes530,532and the selected nodes510,512varies, depending on the system settings. The positional coordinates can be set so that the distance is equal to a pre-defined distance. For example, the node splitting module215may be configured so that the distance is always be equal to 10 meters. Alternatively, the distance may be calculated from the attributes of the selected road segment, such as priority and speed limit. For example, if a road segment is a highway with a 65 mph speed limit, the physical road corresponding to the road segment is probably relatively wide, so the nodes are placed 20 meters apart. However, if a road segment is a local road with a 15 mph speed limit, the physical road corresponding to the road segment is probably relatively narrow, so the nodes are placed only 8 meters apart.

Segment splitting module220splits the selected road segment into two separate road segments while maintaining the proper attributes, directionality, and geometry for each of the road segments. In one embodiment, the segment splitting module instantiates320one new road segment and modifies the attributes of the selected road segment. In another embodiment, the segment splitting module can instantiate two new segments and delete the originally selected road segment. In both embodiments, the end result is a pair of one-way road segments each having a direction of travel that is opposite to that of the other road segment. A detailed description of one embodiment of the segment splitting module220that instantiates a road segment while modifying the other road segment is explained in the following paragraphs.

First, the segment splitting module220instantiates320a new road segment in the database. When first instantiated, the instantiated segment can be represented as three sets of NULL attributes. The newly instantiated road segment is associated with the newly instantiated nodes so that the newly instantiated nodes define the endpoints of the newly instantiated road segment. For example, referring toFIG. 5b, the node splitting module215has previously instantiated new nodes530and532. The segment splitting module220now instantiates a new road segment546. New road segment546is associated with and connects nodes530and532. Node530is assigned to be the target node of one set of NULL attributes. Node530is assigned to be the target node of another set of NULL attributes.

The system configures the geometry of the newly instantiated segment and the selected road segment (collectively, “the split road segments”) so that it appears as if the selected road segment is being divided into two road segments, each having a geometry (e.g., shape) that is substantially similar to the original road segment. For example, referring toFIG. 6, illustrated is a schematic view of a road segment with a curved appearance after it is split into two road segments. Shown in the figure are a newly instantiated segment605with newly instantiated node620, a selected segment615with a selected node630, and the original position610of the selected segment with the original position of the selected node625. The positions of the endpoints620and630, or nodes, were set previously by the node splitting module215. Each segment also has a geometry consisting of positional coordinates635, as shown by the dark circles in the figure. In practice, the positional coordinates are simply used to re-create the shape of a road segment and are not actually displayed to the user. Due to the configuration of the geometry, the newly instantiated segment605has a curved appearance that is similar to the original shape610of the selected road segment. Similarly, the selected segment615has a curved appearance that is similar to the original shape610of the selected road segment. By contrast, if the geometry was not preserved, segments605and615would simply be straight lines along their entirety.

To preserve the geometry in the instantiated segment, the system copies the original geometry635of the selected segment into the instantiated segment. The coordinates of the geometry in the instantiated segment605are then adjusted to ensure that the shape of the instantiated segment610matches the original shape610of the selected segment. Similarly, the geometry of the selected segment615can be maintained by adjusting the coordinates of its geometry to match the original shape610of the selected segment.

Next, the segment splitting module220assigns325the proper direction of travel to the newly instantiated and selected road segments (the “split road segments”). Assuming the selected segment is a two-way road segment, the resulting split road segments will have opposite directions of travel. The directionality assigned to the split road segments depends on the driving rules of the country in which the roads are located. In countries where cars drive on the right hand side of the road, e.g. the United States, the segment splitting module220determines that traffic should travel in a counter-clockwise loop. In countries where cars drive on the left hand side of the road, e.g. the U.K., the segment splitting module220determines that traffic should travel in a clockwise loop.

For example, referring toFIG. 5b, illustrated is a set of split road segments after directionality is assigned. Assuming that the road segments represent roads in the United States, the segment splitting module determines that the flow of traffic on the split road segments should be in a counter-clockwise loop. Thus, it determines that the direction of travel on road segment506should be westbound from node512to node510. This direction of travel is assigned to segment506. Segment506is currently a segment with two directions of travel. It has one set of attributes associated with target node512and another set of attributes associated with target node510. To assign the westbound direction of travel to segment506, segment506is converted into a one-way road segment. Target node512and its associated attributes are marked as corresponding to a disallowed direction of travel. Target node506and its associated attributes are maintained as corresponding to an allowed direction of travel. The segment splitting module also determines that the direction of travel on road segment546should be in the opposite direction, eastbound, from node530to node532. The east-bound direction of travel is assigned to segment546by marking target node532as corresponding to an allowed direction of travel. Target node530is marked as corresponding to a disallowed direction of travel.

After directions of travel are assigned, the segment splitting module220allocates328attributes between the split road segments so that each resulting road segment has the proper attributes that correspond to its assigned direction of travel. Attributes of the selected road segment that are common to both directions of travel are copied330to the newly instantiated road segment. Attributes that correspond only to the direction of travel of the newly instantiated road segment are migrated335to the new road segment. Migrating means that attributes are copied from the original road segment to the new road segment and deleted from the original road segment. These changes in the attributes are stored in the database.

For example, referring toFIG. 7a-b, illustrated are the attributes associated with the split road segments506and546ofFIG. 5b.FIG. 7aillustrates the attributes associated with the split road segments after a new road segment546has been instantiated, but before it is associated with any attributes. The selected road segment506is still associated with three sets of attributes, and the newly instantiated road segment546is not yet associated with any attributes.FIG. 7billustrates the attributes associated with the split road segments after the attributes are allocated. The segment splitting module copies750attributes that are associated with both directions of travel to the newly instantiated segment546. Attributes associated only with the east-bound direction of travel towards node512are migrated752from the original segment to the newly instantiated segment. These changes are then stored to the database. The resulting tables of attributes represent two separate road segments, each of which corresponds to different lanes of a physical road having opposite directions of travel. Road segment506corresponds to lanes of a road having a west-bound direction of travel towards node510. Road segment546corresponds to lanes of a road having an east-bound direction of travel towards node532.

Up to this point, the operation of the segment splitting module220has been described with respect to splitting a two-way road segment. In one embodiment, the segment splitting module220can also be used to split a one-way road segment. Although the need to split road segments arises primarily with two-way road segments, it is sometimes necessary to split one-way road segments. For example, some highways have divided carpool lanes that run in the same direction as the highway but are separated from the highway by a barrier or road marking. To split a one-way segment, the steps of assigning325a direction of travel and allocating328attributes are slightly different than what has been described above. After instantiating a new segment, segment splitting module220assigns325the same direction of travel to both of the split road segments. The segment splitting module220then allocates328attributes by copying all of the attributes of the selected road segment to the instantiated road segment.

In another embodiment, segment splitting module220splits not only the selected road segment, but further splits road segments that share a common node with the selected road segment. For example, referring toFIG. 5a, the user has selected a segment506to be split. The selected segment506shares a common node512with another road segment508. However, referring toFIG. 5b, splitting just segment506to create segment540would result in a gap in the road between nodes532and502. Thus, the segment splitting module instantiates a new road segment538to fill this gap, assigns the proper directionality to segments508and538, and copies and migrates attributes to the new segment538from segment508. These changes are then stored to the database.

In another embodiment, after the user selects a segment to be split, node splitting module215instantiates315only one new node instead of two new nodes. The segment splitting module220then instantiates320a new road segment between the new node and one of the original nodes of the selected road segment, assigns325the proper directionality to the new road segment and the selected road segment, and copies330and migrates335attributes to the new segment. For example, referring toFIG. 5b, the user has selected a segment550for splitting. Segment550has a beginning node502and an ending node534. Referring toFIG. 5c, illustrated are the road segments ofFIG. 5bafter segment550is split. The node splitting module instantiates a single node572. Then, the segment splitting module instantiates a new road segment580to connect newly instantiated node572with node534. The segment splitting module assigns the direction of travel towards node534to the new road segment580and assigns the direction of travel towards node502to the selected road segment550. The segment splitting module also copies and migrates attributes to the new road segment580from the user selected segment550.

In yet another embodiment, instead of selecting only one segment for splitting, the user selects multiple road segments for splitting. For example, referring toFIG. 5A, the user can select both segment506and508for splitting. The map editor then splits each of the selected nodes and road segments according to the process described above.

At this point in the process, a selected road segment has been split into two separate road segments, each having its own attributes, directionality, and geometry. Returning toFIG. 2, the adjustment module222now fine-tunes the split segments by adjusting338the placement of the split nodes and split road segments. The adjustment module222first overlays the split nodes and road segments onto a satellite image, which is displayed to a user. The user visually determines if the nodes and road segments are in their proper locations. If the placement of a node is not correct, the user moves the node to its correct location in the display. For example, the user can use a mouse to select the node and drag it to a different location, or use keyboard inputs to achieve the same result. If the geometry of a road segment is not correct, the user alters the shape of the segment in the display. For example, the user can use a mouse to select a portion of a road segment and move it to a different location, thereby changing the shape of the segment. Additionally, the user can adjust the distance between the split nodes and split road segments. For example, the user may press the up arrow to increase the split distance or down arrow to decrease the split distance. As the nodes and road segments are adjusted, the adjustment module222updates the positional coordinates of the nodes and the geometry data of the road segments to match their new placement in the display. The updated map data is stored in the database.

The intersection connection module225connects340the split road segments in order to account for any intersections with the split road segments. In one embodiment, a map of the split nodes and road segments is displayed to the user. The user then visually determines whether another road intersects with the portion of the road that was just split. If so, the user enters a command to connect the split road segments. In response, the intersection connection module225instantiates a new segment to connect the nodes that were just split by the node splitting module215. For example, referring toFIG. 5c, the vertically oriented road segment504intersects with the split road segment550at node502. Without a connecting road segment592, the map is not completely accurate because there is a gap between node502and572. As a result, it appears as if a car traveling south on road segment504cannot turn left onto road segment580. To remedy this problem, a user enters a command to connect the road segments. The intersection connection225module then instantiates a new road segment592to connect nodes502and572.

In another embodiment, the intersection connection module225automatically connects the nodes of a split road segment after each split without any user input. Automatically connecting intersections can be enabled or disabled by a configuration setting in the map editor.

In a further embodiment, the intersection connection module automatically identifies intersections with the split road segments and connects340the split road segments only if an intersection exists. To identify an intersection, the intersection module evaluates each node of the selected road segment to determine whether the node is connected to more than two road segments. If so, each road segment is evaluated to determine if they have different street names. If so, an intersection exists at that node. Once an intersection is identified, the intersection connection module instantiates a new road segment to connect the node with one of the newly instantiated nodes.

The next segment identification module230facilitates faster operation of the road splitting process by identifying345another road segment to be split. Identifying the next road segment is an optional step that is activated by a user command or setting in a configuration file. The next segment identification module230identifies a next segment by finding a segment that shares a common node with the selected road segment. If more than one segment shares a common node with the selected segment, the system also compares the attributes of the selected segment and each of the potential candidates in order to identify the segment with the fewest changes in attributes. The system can also consider the change in angular direction between the current segment and the next segment to identify the segment with the smallest change in angular direction. For example, inFIG. 5b, the user selects a road segment550and splits it, resulting in the map as shown inFIG. 5c. The next segment identification module230determines that road segment590shares a common node534with road segment550. It also determines that road segment504shares a common node502with segment550. However, segment590has same name as road segment550, whereas segment504has a different name. Thus, road segment590is identified as the next segment to be split.

Once the next segment is identified, the segment can be presented to a user, who determines whether to split the next segment. Alternatively, the identified segment can automatically be split without any user input by the node splitting module215and segment splitting module220according to the above-described process.

The output module235generates350an output of the nodes and road segments. The output can be in the form of a visual road map that is displayed 3 on a screen. For example,FIG. 4billustrates a visual road map generated by the output module235. The figure shows a road405with several road segments that have been split by the map editor. The nodes and segments are displayed along with a satellite image of the surrounding area. The split road segments also intersect with another road415. Alternatively, the output module can store the newly instantiated and modified map data in the map data database110.

Additional Configuration Considerations