US6816779B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Programmatically computing street intersections using street geometry
Assignee: International Business Machines Corp
•
Filing: 2002-02-15
•
Granted: 2004-11-09
•
Expires: 2022-02-15
Abstract
Abstract Techniques are disclosed for programmatically deriving street intersections from address data which is presented in textual format, or alternatively, from street geometry data which has been derived from such address data. Preferred embodiments leverage built-in functions and data types of a spatially-enabled object relational database system. Information about streets is analyzed to determine which streets intersect, as well as the intersection locations. This information is stored in a spatially-enabled table for subsequent retrieval. The derived street intersections data supports retrievals which do not rely on proprietary file formats or binary files, thereby enabling faster retrievals and reduced resource consumption requirements. The derived street intersection information may be used in many ways, such as to compute a path from one location to another.
Inventors
- 👤 Feng-wei Chen
- 👤 Robert R. Cutlip
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 05:15
CPC Classifications
G; G06; G06T; G06T17/00; G06T17/05
Claims Analysis
Total Claims: 20
Claim 1
Independent Claim
157 words
A method of programmatically computing street intersections using street geometry, comprising steps of: obtaining street geometry information for a first street; comparing the obtained street geometry information for the first street to obtained street geometry information for one or more other streets to determine intersecting ones of the one or more other streets, further comprising steps of: comparing a bounding box corresponding to a geometric line representation of the first street to the bounding box corresponding to the geometric line representation of a selected one of the one or more other streets; and if the step of comparing the bounding boxes determines a potential intersection, comparing the geometric line representation of the first street to the geometric line representation of the selected one of the other streets; for each of the intersecting ones, storing a geographic location of a point of intersection, along with an identification of the first street and the identification of the intersecting one.
Claim 2
Independent Claim
157 words
A method of programmatically computing street intersections using street geometry, comprising steps of: obtaining street geometry information for a first street; comparing the obtained street geometry information for the first street to obtained street geometry information for one or more other streets to determine intersecting ones of the one or more other streets, further comprising steps of: comparing a bounding box corresponding to a geometric line representation of the first street to the bounding box corresponding to the geometric line representation of a selected one of the one or more other streets; and if the step of comparing the bounding boxes determines a potential intersection, comparing the geometric line representation of the first street to the geometric line representation of the selected one of the other streets; for each of the intersecting ones, storing a geographic location of a point of intersection, along with an identification of the first street and the identification of the intersecting one.
Claim 3
Dependent Claim
18 words
The method according to claim 1 , wherein the obtained street geometry information originates from textual address information.
Claim 4
Dependent Claim
20 words
The method according to claim 1 , wherein the geographic location comprises latitude and longitude values of the intersection point.
Claim 5
Dependent Claim
17 words
The method according to claim 1 , wherein the storing step stores geographic locations as geometric data.
Claim 6
Dependent Claim
43 words
The method according to claim 1 , wherein the storing step further comprises the step of storing a reciprocal comprising the geographic location of the point of intersection, along with the identification of the intersecting one and the identification of the first street.
Claim 7
Dependent Claim
19 words
The method according to claim 1 , wherein the obtained street geometry information is retrieved from a database table.
Claim 8
Dependent Claim
20 words
The method according to claim 1 , wherein the obtained street geometry information is dynamically computed from textual address information.
Claim 9
Dependent Claim
30 words
The method according to claim 1 , further comprising the step of repeating the obtaining, comparing, and storing steps for at least one of the one or more other streets.
Claim 10
Dependent Claim
26 words
The method according to claim 1 , wherein the storing step further comprises the step of creating or updating a row in a relational database table.
Claim 11
Independent Claim
197 words
A system for programmatically computing street intersections using street geometry, comprising: means for obtaining street geometry information for a first street; means for comparing the obtained street geometry information for the first street to obtained street geometry information for one or more other streets to determine intersecting ones of the one or more other streets, further comprising: means for comparing a bounding box corresponding to a geometric line representation of the first street to the bounding box corresponding to the geometric line representation of a selected one of the one or more other streets; and means for comparing the geometric line representation of the first street to the geometric line representation of the selected one of the other streets if the means for comparing the bounding boxes determines a potential intersection; for each of the intersecting ones, means for storing (1) a geographic location of a point of intersection, along with an identification of the first street and the identification of the intersecting one, in a relational database table; and (2) a reciprocal comprising the geographic location of the point of intersection, along with the identification of the intersecting one and the identification of the first street.
Claim 12
Independent Claim
197 words
A system for programmatically computing street intersections using street geometry, comprising: means for obtaining street geometry information for a first street; means for comparing the obtained street geometry information for the first street to obtained street geometry information for one or more other streets to determine intersecting ones of the one or more other streets, further comprising: means for comparing a bounding box corresponding to a geometric line representation of the first street to the bounding box corresponding to the geometric line representation of a selected one of the one or more other streets; and means for comparing the geometric line representation of the first street to the geometric line representation of the selected one of the other streets if the means for comparing the bounding boxes determines a potential intersection; for each of the intersecting ones, means for storing (1) a geographic location of a point of intersection, along with an identification of the first street and the identification of the intersecting one, in a relational database table; and (2) a reciprocal comprising the geographic location of the point of intersection, along with the identification of the intersecting one and the identification of the first street.
Claim 13
Dependent Claim
20 words
The system according to claim 10 , wherein the geographic location comprises latitude and longitude values of the intersection point.
Claim 14
Dependent Claim
269 words
A computer program product for programmatically computing street intersections using street geometry, the computer program product embodied on one or more computer-readable media and comprising: computer-readable program code means for obtaining street geometry information for a first street; computer-readable program code means for comparing the obtained street geometry information for the first street to obtained street geometry information for one or more other streets to determine intersecting ones of the one or more other streets, further comprising: computer-readable program code means for comparing a bounding box corresponding to a geometric line representation of the first street to the bounding box corresponding to the geometric line representation of a selected one of the one or more other streets; and computer-readable program code means for comparing the geometric line representation of the first street to the geometric line representation of the selected one of the other streets if the computer-readable program code means for comparing the bounding boxes determines a potential intersectionl; for each of the intersecting ones, computer-readable program code means for storing (1) a geographic location of a point of intersection, along with an identification of the first street and the identification of the intersecting one, in a relational database table; and (2) a reciprocal comprising the geographic location of the point of intersection, along with the identification of the intersecting one and the identification of the first street; and computer-readable program code means for repeating operation of the computer-readable program code means for obtaining, computer-readable program code means for comparing, and computer-readable program code means for storing, for at least one of the one or more other streets.
Claim 15
Dependent Claim
269 words
A computer program product for programmatically computing street intersections using street geometry, the computer program product embodied on one or more computer-readable media and comprising: computer-readable program code means for obtaining street geometry information for a first street; computer-readable program code means for comparing the obtained street geometry information for the first street to obtained street geometry information for one or more other streets to determine intersecting ones of the one or more other streets, further comprising: computer-readable program code means for comparing a bounding box corresponding to a geometric line representation of the first street to the bounding box corresponding to the geometric line representation of a selected one of the one or more other streets; and computer-readable program code means for comparing the geometric line representation of the first street to the geometric line representation of the selected one of the other streets if the computer-readable program code means for comparing the bounding boxes determines a potential intersectionl; for each of the intersecting ones, computer-readable program code means for storing (1) a geographic location of a point of intersection, along with an identification of the first street and the identification of the intersecting one, in a relational database table; and (2) a reciprocal comprising the geographic location of the point of intersection, along with the identification of the intersecting one and the identification of the first street; and computer-readable program code means for repeating operation of the computer-readable program code means for obtaining, computer-readable program code means for comparing, and computer-readable program code means for storing, for at least one of the one or more other streets.
Claim 16
Independent Claim
89 words
A method of programmatically computing street intersections using street geometry, comprising steps of: comparing a bounding box corresponding to a geometric line representation of a first street to the bounding box corresponding to the geometric line representation of at least one selected one of one or more other streets; and for each bounding box comparison that determines a potential intersection, comparing the geometric line representation of the first street to the geometric line representation of the selected street to determine whether the first street and the selected street intersect.
Claim 17
Independent Claim
89 words
A method of programmatically computing street intersections using street geometry, comprising steps of: comparing a bounding box corresponding to a geometric line representation of a first street to the bounding box corresponding to the geometric line representation of at least one selected one of one or more other streets; and for each bounding box comparison that determines a potential intersection, comparing the geometric line representation of the first street to the geometric line representation of the selected street to determine whether the first street and the selected street intersect.
Claim 18
Dependent Claim
47 words
The method according to claim 13 , wherein the step of comparing the geometric line representations further comprises the step of determining a point of intersection between the first street and the selected street when it is determined that the first street and the selected street intersect.
Claim 19
Independent Claim
96 words
A method of programmatically computing street intersections using street geometry, comprising steps of: comparing a bounding box corresponding to a geometric line representation of a first street to the bounding box corresponding to the geometric line representation of each of one or more other streets; for each bounding box comparison that determines a potential intersection, comparing the geometric line representation of the first street to the geometric line representation of the other street; and for each geometric line representation comparison that determines an actual intersection, determining a geographic location of a point of the actual intersection.
Claim 20
Independent Claim
96 words
A method of programmatically computing street intersections using street geometry, comprising steps of: comparing a bounding box corresponding to a geometric line representation of a first street to the bounding box corresponding to the geometric line representation of each of one or more other streets; for each bounding box comparison that determines a potential intersection, comparing the geometric line representation of the first street to the geometric line representation of the other street; and for each geometric line representation comparison that determines an actual intersection, determining a geographic location of a point of the actual intersection.
References Cited (Backward Citations)
US6498982B2
Cited
US6249740B1
Cited
US20010025222A1
Cited
US6339746B1
Cited
US6510382B2
Cited
US6424911B2
Cited
US6587782B1
Cited
US6526348B1
Cited
US6415224B1
Cited
US20030060970A1
Cited
US20030083805A1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2007-11-09 | 2008-05-10 | 2008-11-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2011-11-09 | 2012-05-10 | 2012-11-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2015-11-09 | 2016-05-10 | 2016-11-09 | $7700.00 | Window Closed / Lapsed |