Programmatically calculating paths from a spatially-enabled database
First Claim
Patent Images
1. A method of programmatically calculating paths comprising steps of:
- identifying 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 bounding 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
Technics 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.
16 Citations
34 Claims
-
1. A method of programmatically calculating paths comprising steps of:
-
identifying 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 bounding 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 (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
13. 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 intersects the street on which the destination is located. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20, 21, 22, 23)
-
-
24. 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 when the street on which the origin is located intersects the street on which the dstination is located. - View Dependent Claims (25, 26, 27, 28, 29, 30, 31, 32, 33, 34)
-
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.
-
Primary Examiner(s)Cuchlinski, Jr., William A.
-
Assistant Examiner(s)Hernandez, Olga
-
Application NumberUS10/077,146Publication NumberTime in Patent Office1,117 DaysField of Search701200-202, 701/205, 701208-211, 731/78.RUS Class Current701/209CPC Class CodesG01C 21/3446 Details of route searching ...
