PROGRAMMATICALLY CALCULATING PATHS FROM A SPATIALLY-ENABLED DATABASE
First Claim
Patent Images
1. A method of programmatically calculating paths, comprising steps of:
- identify an origin and a destination;
determining a first street on which the origin is located and a second street on which the destination is located; and
computing a path from the origin on the first street to the destination on the second street using intersection data by iteratively performing, until completing the path, steps of;
computing a hounding box between the origin and the destination;
computing a shortest linear path (“
SLP”
) between the origin and the destination; and
selecting, from the intersection data when the path is not yet complete, an intersection point closest to the SLP to replace the origin for subsequent iterations of the iteratively performed steps, wherein the path is complete when the street on which the origin is located intersects the street on which the destination is located.
1 Assignment
0 Petitions
Accused Products
Abstract
Techniques are disclosed for programmatically calculating directions (or other types of paths between points) without reliance on proprietary file formats or binary shape files, and without requiring application programmers to write code that performs complex manipulations of directed graphs. Preferred embodiments leverage built-in functions of a spatially-enabled object relational database system. Information about intersections between streets is used in a novel manner to compute paths between points. The intersection information is preferably obtained from precomputed information stored in a spatially-enabled relational database table.
11 Citations
37 Claims
-
1. A method of programmatically calculating paths, comprising steps of:
-
identify an origin and a destination;
determining a first street on which the origin is located and a second street on which the destination is located; and
computing a path from the origin on the first street to the destination on the second street using intersection data by iteratively performing, until completing the path, steps of;
computing a hounding box between the origin and the destination;
computing a shortest linear path (“
SLP”
) between the origin and the destination; and
selecting, from the intersection data when the path is not yet complete, an intersection point closest to the SLP to replace the origin for subsequent iterations of the iteratively performed steps, wherein the path is complete when the street on which the origin is located intersects the street on which the destination is located. - View Dependent Claims (3, 4, 5, 6, 7, 8, 9, 10, 15, 16, 37)
-
-
2. (canceled)
-
11. A system for programmatically calculating paths comprising:
-
means for identifying an origin and a destination;
means for determining a first street on which the origin is located and a second street on which the destination is located; and
means for computing a path from the origin on the first street to the destination on the second street using intersection data by iteratively performing, until completing the path, operation of;
means for computing a bounding box between the origin and the destination;
means for computing a shortest linear path (“
SLP”
) between the origin and the destination; and
means for selecting, from the intersection data when the path is not yet complete, an intersection point closest to the SLP to replace the origin for subsequent iterations of the iteratively performed operations, wherein the path is complete when the street on which the origin is located interests the street on which the destination is located. - View Dependent Claims (17, 18, 19, 20, 21, 22, 23, 24, 25, 26)
-
-
12. (canceled)
-
13. A computer program product for programmatically calculating paths, the computer program product embodied on one or more computer-readable media and comprising:
-
computer-readable program code means for identifying an origin and a destination;
computer-readable program code means for determining a first street on which the origin is located and a second street on which the destination is located; and
computer-readable program code means for computing a path from the origin on the first street to the destination on the second street using intersection data by iteratively performing, until completing the path, operation of;
computer-readable program code means for computing a bounding box between the origin and the destination;
computer-readable program code means for computing a shortest linear path (“
SLP”
) between the origin and the destination; and
computer-readable program code means for selecting, from the intersection data when the path is not yet complete, an intersection point closest to the SLP to replace the origin for subsequent iterations of the iteratively performed operations, wherein the path is complete wen the street on which the origin is located intersects the street on which the designation is located. - View Dependent Claims (27, 28, 32, 33, 34, 35, 36)
-
-
14. (canceled)
- 29. The computer program product according to Clam 13, wherein the computer-readable program code means for selecting gives preference to intersection points whose SLP is not longer than a quantified percentage more than the SLP between the origin on the first street and the destination on the second street.
Specification
-
- Resources
Litigation Campaign Assessment
Thank you for your request. You will receive a custom alert email when the Litigation Campaign Assessment is available.
×
-
Current AssigneeInternational Business Machines Corporation
-
Original AssigneeInternational Business Machines Corporation
-
InventorsChen, Feng-Wei, Cutlip, Robert R.
-
Granted Patent
-
Time in Patent OfficeDays
-
Field of Search
-
US Class Current701/209
-
CPC Class CodesG01C 21/3446 Details of route searching ...
