Path finding in a map editor
First Claim
Patent Images
1. A computer-implemented method for map editing in a map editor, comprising:
- storing road segments in a computer database, each road segment having a length and attribute data describing features of the segment, a portion of the attribute data being incomplete;
displaying the road segments on a map;
receiving a user input selecting a first road segment from the road segments displayed on the map and receiving a user input selecting a second road segment from the road segments displayed on the map, the first road segment and the second road segment separated by one or more other road segments;
identifying a path comprising a plurality of the road segments connecting the first and second segments by minimizing a cost based upon lengths of the road segments in the path and changes in one or more attributes between adjacent ones of the road segments in the path;
displaying the identified path on the map;
receiving, responsive to displaying the identified path, a user input associating a common attribute with each of the road segments in the identified path, wherein the common attribute is at least one of a road name, speed limit, surface type, road width, one-wayness or address range; and
storing the common attribute in the computer database to modify the incomplete portion of the attribute data.
2 Assignments
0 Petitions
Accused Products
Abstract
A system and method for automatically finding a path between two selected road segments. A map editor displays road segments in a visual map to a user. The user selects a beginning segment and an ending segment from the displayed segments. The map editor then identifies the best path between these two segments by applying a path-finding algorithm. The path finding algorithm identifies the best path based on the total length of the path and the changes in attributes between adjacent road segments in the path. The path identified by the map editor is then displayed to the user.
-
Citations
18 Claims
-
1. A computer-implemented method for map editing in a map editor, comprising:
-
storing road segments in a computer database, each road segment having a length and attribute data describing features of the segment, a portion of the attribute data being incomplete; displaying the road segments on a map; receiving a user input selecting a first road segment from the road segments displayed on the map and receiving a user input selecting a second road segment from the road segments displayed on the map, the first road segment and the second road segment separated by one or more other road segments; identifying a path comprising a plurality of the road segments connecting the first and second segments by minimizing a cost based upon lengths of the road segments in the path and changes in one or more attributes between adjacent ones of the road segments in the path; displaying the identified path on the map; receiving, responsive to displaying the identified path, a user input associating a common attribute with each of the road segments in the identified path, wherein the common attribute is at least one of a road name, speed limit, surface type, road width, one-wayness or address range; and storing the common attribute in the computer database to modify the incomplete portion of the attribute data. - View Dependent Claims (2, 3, 4, 5, 6, 7, 17)
-
-
8. The method of 1, wherein minimizing a cost based upon lengths of the road segments in the path and changes in the one or more attributes between adjacent ones of the road segments in the path comprises minimizing a cost function based upon angular changes in direction between adjacent ones of the road segments that have different names, wherein angular changes between adjacent ones of the road segments having a common name do not affect the cost.
-
9. A non-transitory computer-readable medium storing instructions, the instructions when executed by a processor cause the processor to:
-
store road segments in a computer database, each road segment having a length and attribute data describing features of the segment, a portion of the attribute data being incomplete; display the road segments on a map; receive a user input selecting a first road segment from the road segments displayed on the map and receiving a user input selecting a second road segment from the road segments displayed on the map, the first road segment and the second road segment separated by one or more other road segments; identify a path comprising a plurality of the road segments connecting the first and second segments by minimizing a cost based upon lengths of the road segments in the path and changes in one or more attributes between adjacent ones of the road segments in the path; display the identified path on the map; receive, responsive to displaying the identified path, a user input associating a common attribute with each of the road segments in the identified path, wherein the common attribute is at least one of a road name, speed limit, surface type, road width, one-wayness or address range; and store the common attribute in the computer database to modify the incomplete portion of the attribute data.
-
-
10. A computer system for editing map data, comprising:
-
a processor; and a non-transitory computer readable medium storing instructions, the instructions when executed by the processor cause the processor to; store road segments in a computer database, each road segment having a length and attribute data describing features of the segment, a portion of the attribute data being incomplete; display the road segments on a map; receive a user input selecting a first road segment from the road segments displayed on the map and receiving a user input selecting a second road segment from the road segments displayed on the map, the first road segment and the second road segment separated by one or more other road segments; identify a path comprising a plurality of the road segments connecting the first and second segments by minimizing a cost based upon lengths of the road segments in the path and changes in one or more attributes between adjacent ones of the road segments in the path; receive, responsive to displaying the identified path, a user input associating a common attribute with each of the road segments in the identified path, wherein the common attribute is at least one of a road name, speed limit, surface type, road width, one-wayness or address range; and store the common attribute in the computer database to modify the incomplete portion of the attribute data.
-
-
11. A computer-implemented method for map editing in a map editor, comprising:
-
storing nodes and road segments in a computer database, each road segment having a length and attribute data describing features of the segment, a portion of the attribute data being incomplete; displaying the nodes and road segments on a map; receiving a user input selecting a first node from the nodes displayed on the map and receiving a user input selecting a second node from the nodes displayed on the map, the first node and the second node separated by one or more of the road segments; identifying a path comprising a plurality of the road segments connecting the first and second nodes by minimizing a cost based upon lengths of the road segments in the path and changes in one or more attributes between adjacent ones of the road segments in the path; displaying the identified path on the map; receiving, responsive to displaying the identified path, a user input associating a common attribute with each of the road segments in the identified path, wherein the common attribute is at least one of a road name, speed limit, surface type, road width, one-wayness or address range; and storing the common attribute in the computer database to modify the incomplete portion of the attribute data. - View Dependent Claims (12, 13, 18)
-
-
14. The method of 11, wherein minimizing a cost based upon lengths of the road segments in the path and changes in the one or more attributes between adjacent ones of the road segments in the path comprises minimizing a cost function based upon angular changes in direction between the adjacent ones of the road segments that have different names, wherein angular changes between adjacent ones of the road segments having a common name do not affect the cost.
-
15. A non-transitory computer-readable medium storing instructions, the instructions when executed by a processor cause the processor to:
-
store nodes and road segments in a computer database, each road segment having a length and attribute data describing features of the segment, a portion of the attribute data being incomplete; display the nodes and road segments on a map; receive a user input selecting a first node from the nodes displayed on the map and receiving a user input selecting a second node from the nodes displayed on the map, the first node and the second node separated by one or more of the road segments; identify a path comprising a plurality of the road segments connecting the first and second nodes by minimizing a cost based upon lengths of the road segments in the path and changes in one or more attributes between adjacent ones of the road segments in the path; display the identified path on the map; receive, responsive to displaying the identified path, a user input associating a common attribute with each of the road segments in the identified path, wherein the common attribute is at least one of a road name, speed limit, surface type, road width, one-wayness or address range; and store the common attribute in the computer database to modify the incomplete portion of the attribute data.
-
-
16. A computer system for editing map data, comprising:
-
a processor; and a non-transitory computer readable medium storing instructions, the instructions when executed by the processor cause the processor to; store nodes and road segments in a computer database, each road segment having a length and attribute data describing features of the segment, a portion of the attribute data being incomplete; display the nodes and road segments on a map; receive a user input selecting a first node from the nodes displayed on the map and receiving a user input selecting a second node from the nodes displayed on the map, the first node and the second node separated by one or more of the road segments; identify a path comprising a plurality of the road segments connecting the first and second nodes by minimizing a cost based upon lengths of the road segments in the path and changes in one or more attributes between adjacent ones of the road segments in the path; display the identified path on the map; receive, responsive to displaying the identified path, a user input associating a common attribute with each of the road segments in the identified path, wherein the common attribute is at least one of a road name, speed limit, surface type, road width, one-wayness or address range; and store the common attribute in the computer database to modify the incomplete portion of the attribute data.
-
Specification