System and method for identifying the geographic region of a geographic area which contains a geographic point associated with a location

• US 5,961,572 A
• Filed: 04/01/1997
• Issued: 10/05/1999
• Est. Priority Date: 04/01/1997
• Status: Expired due to Term

• Current Assignee: Qualcomm FYX Incorporated (Qualcomm, Inc.)
• Original Assignee: Bellsouth Intellectual Property Corporation (AT&T, Inc.)
• Inventors: Craport, William N., Winters, Bruce C.
• Primary Examiner(s): LOUIS JACQUES, JACQUES H
• Application Number:
  US08/831,023
• Time in Patent Office: 917 Days
• Field of Search: 701/200, 701/207, 701/208, 701/209, 701/210, 701/211, 701/201, 701/202, 340/988, 340/990, 340/995, 73/178 R, 342/451, 342/452, 342/457, 342/357, 702/150, 455/422, 455/429
• US Class Current: 701/207
• CPC Class Codes: G01C 21/3893 Transmission of map data from distributed sources, e.g. from roadside stations
• CPC Class Codes: G01S 5/00 Position-fixing by co-ordinating two or more direction or position line determinations; Position-fixing by co-ordinating two or more distance determinations using active systems G01S13/00, G01S15/00, G01S17/00

Abstract

A system and method for identifying the geographic region of a geographic area which contains a geographic point associated with a location. A description of a location such as an address, a nearby intersection, or a nearby landmark, is used to determine geographic coordinates for a geographic point associated with the location. To identify the geographic region which contains the geographic point, one of the plurality of geographic regions in a geographic area is selected as a selected region and a determination is made as to whether the geographic point is located within the selected region. If the geographic point is located within the selected region, then the geographic region is identified. Different preferred methods correspond to different methods for making a determination as to whether the geographic point is located within the selected region. In the preferred methods, the determination is made by drawing a line of predetermined slope through the geographic point and through the selected region and comparing the geographic point to the intersection points between the line and the boundary of the selected region. Some of the preferred methods use estimated geographic regions.

Claims

1. A method for identifying geographic coordinates for a geographic point associated with a location, comprising the steps of:

A. receiving an address for said location, said address having a zip code;

B. receiving an address match candidate, said address match candidate corresponding to a first geographic point;

C. making an address determination as to whether said address match candidate is associated with said location;

D. if said address determination determines that said address match candidate is not associated with said location, then receiving an intersection near said location;

E. receiving an intersection match candidate, said intersection match candidate corresponding to a second geographic point;

F. making an intersection determination as to whether said intersection match candidate is associated with said location;

G. if said intersection determination determines that said intersection match candidate is not associated with said location, then receiving a landmark near said location;

H. receiving a landmark match candidate, said landmark match candidate corresponding to a third geographic point;

I. making a landmark determination as to whether said landmark match candidate is associated with said location;

J. if said landmark determination determines that said landmark match candidate is not associated with said location, then receiving a fourth geographic point associated with said zip code, said fourth geographic point having geographic coordinates associated with said location; and

K. identifying the geographic coordinates for the fourth geographic point.

2. The method of claim 1, further comprising the step of:

if said address determination is that said address match candidate is associated with said location, then identifying geographic coordinates for said first geographic point.

3. The method of claim 1, further comprising the step of:

if said intersection determination is that said intersection match candidate is associated with said location, then identifying geographic coordinates for said second geographic point.

4. The method of claim 1, further comprising the step of:

if said landmark determination is that said landmark match candidate is associated with said location, then identifying geographic coordinates for said third geographic point.

5. The method of claim 1, wherein said zip code defines a geographic region having a centroid, and wherein said step of identifying geographic coordinates for a fourth geographic point associated with said zip code further comprises:

identifying geographic coordinates corresponding to said centroid of said zip code zone.

6. A method for identifying geographic coordinates for a geographic point associated with an address, comprising the steps of:

A. receiving an address, said address having a street number;

B. making an address match candidate determination as to whether there is an address match candidate associated with said address, said address match candidate corresponding to a first geographic point;

C. if said address match candidate determination determines that there is no address match candidate associated with said address, then deleting said street number from said address to create a modified address;

D. receiving a modified address match candidate, said modified address match candidate corresponding to a second geographic point;

E. making a modified address determination as to whether said modified address match candidate is associated with said location;

F. if said modified address determination determines that said modified address match candidate is associated with said location, then receiving geographic coordinates for said second geographic point; and

G. identifying the geographic coordinates for the second geographic point.

7. The method of claim 6, wherein said address has a zip code, further comprising the step of:

if said modified address determination is that said modified address match candidate is not associated with said location, then identifying geographic coordinates for a third geographic point associated with a zip code for said address.

8. A computer-readable medium on which is stored a computer program for identifying geographic coordinates for a geographic point associated with a location, comprising instructions which, when executed by a computer, perform the steps of:

A. receiving an address for said location, said address including a street number and a zip code;

B. making an address match candidate determination as to whether there is an address match candidate associated with said address, said address match candidate corresponding to a first geographic point;

C. if said address match candidate determination determines that there is no address match candidate associated with said address, then deleting said street number from said address to create a modified address;

D. receiving a modified address match candidate, said modified address match candidate corresponding to a second geographic point;

E. making a modified address determination as to whether said modified address match candidate is associated with said location;

F. if said modified address determination determines that said modified address match candidate is not associated with said location, then receiving an intersection near the location;

G. receiving an intersection match candidate, said intersection match candidate corresponding to a third geographic point;

H. making an intersection determination as to whether said intersection match candidate is associated with said location;

I. if said intersection determination determines that said intersection match candidate is not associated with said location, then receiving a landmark near the location;

J. receiving a landmark match candidate, said landmark match candidate corresponding to a fourth geographic point;

K. making a landmark determination as to whether said landmark match candidate is associated with said location; and

L. if said landmark determination determines that said landmark match candidate is not associated with said location, then identifying geographic coordinates for a fifth geographic point associated with said zip code.

9. The computer-readable medium of claim 8, further comprising:

if said address match candidate determination is that there is an address match candidate associated with said address, then

(a) receiving said address match candidate; and

(b) making an address determination as to whether said address match candidate is associated with said location.

10. The computer-readable medium of claim 8, wherein said zip code defines a zip code zone having a centroid, and wherein said step of identifying geographic coordinates for a geographic point associated with said zip code further comprises:

identifying geographic coordinates for a geographic point corresponding to said centroid of said zip code zone.

11. In a geographic area divided into a plurality of non-overlapping geographic regions, a method for identifying the geographic region which contains a geographic point, comprising the steps of:

A. selecting one of said plurality of non-overlapping geographic regions as a selected region, said selected region being defined by a boundary of a plurality of boundary points;

B. making a determination as to whether said geographic point is located within said selected region by

drawing a line of predetermined slope through said geographic point and through said selected region so that said line intersects a first boundary point of said selected region and a second boundary point of said selected region,

checking whether said geographic point lies on said line between said first boundary point and said second boundary point, and if said geographic point lies on said line between said first boundary point and said second boundary point, then defining said determination to be that said geographic point is located within said selected region; and

C. if said determination determines that said geographic point is located within said selected region, then identifying said selected region.

12. The method of claim 11, wherein said step B further comprises:

if said geographic point does not lie on said line between said first boundary point and said second boundary point, then defining said determination to be that said geographic point is not located within said selected region.

16. The method of claims 11 or 13 wherein each geographic region of said plurality of non-overlapping geographic regions has a name, and wherein said step C further comprises identifying said selected region by the name of said selected region.

17. The method of claims 12 or 14 wherein said determination in said step B is that said geographic point is not located within said selected region, and wherein said step B further comprises:

repeating said step A followed by said step B with another one of said plurality of non-overlapping geographic regions as said selected region until said determination in said step B changes to be that said geographic point is located within said selected region.

13. In a geographic area divided into a plurality of non-overlapping geographic regions, a method for identifying the geographic region which contains a geographic point, comprising the steps of:

A. selecting one of said plurality of non-overlapping geographic regions as a selected region, said selected region being defined by a boundary of a plurality of boundary points;

B. making a determination as to whether said geographic point is located within said selected region by drawing a line of predetermined slope through said geographic point, checking whether said line intersects said selected region at said geographic point, and if said line intersects said selected region at said geographic point, then defining said determination to be that said geographic point is located within said selected region; and

C. if said determination determines that said geographic point is located within said selected region, then identifying said selected region.

14. The method of claim 13, wherein said step B further comprises:

if said line does not intersect said selected region at said geographic point, then defining said determination to be that said geographic point is not located within said selected region.

15. The method of claim 13, wherein said step B further comprises:

checking whether said line intersects said selected region at said geographic point only.

18. A method for identifying the geographic region of a geographic area which contains a geographic point, comprising the steps of:

A. dividing said geographic area into a plurality of non-overlapping geographic regions, each of said non-overlapping geographic regions corresponding to a respective estimated geographic region so as to provide a plurality of estimated geographic regions;

B. selecting one of said plurality of estimated geographic regions as a selected estimated region;

C. making a first determination as to whether said geographic point is located within said selected estimated region;

D. if said geographic point is located within said selected estimated region, then selecting a selected region, said selected region being the geographic region of said plurality of non-overlapping geographic regions that corresponds to said selected estimated region, and said selected region being defined by a boundary of a plurality of boundary points;

E. making a second determination as to whether said geographic point is located within said selected region by drawing a line of predetermined slope through said geographic point and through said selected region so that said line intersects a first boundary point of said selected region and a second boundary point of said selected region, checking whether said geographic point lies on said line between said first boundary point and said second boundary point, and if said geographic point lies on said line between said first boundary point and said second boundary point, then defining said second determination to be that said geographic point is located within said selected region; and

F. if said second determination determines that said geographic point is located within said selected region, then identifying said selected region.

21. The method of claims 18 or 19 further comprising:

if said second determination in said step E determines that said geographic point is not located within said selected region, then

repeating said steps B, C, D and E with another one of said plurality of estimated geographic regions as said selected estimated region until said second determination in said step E is that said geographic point is located within said selected region.

22. The method of claims 18 or 19, further comprising the step of:

if said geographic point is not located within said estimated geographic region, then repeating said step B followed by said step C with another one of said plurality of estimated geographic regions as said selected estimated region.

23. The method of claims 18 or 19 wherein each region of said plurality of non-overlapping geographic regions has a name, and wherein said step of identifying said selected region further comprises identifying said selected region by the name of said selected region.

19. A method for identifying the geographic region of a geographic area which contains a geographic point, comprising the steps of:

A. dividing said geographic area into a plurality of non-overlapping geographic regions, each of said non-overlapping geographic regions corresponding to a respective estimated geographic region so as to provide a plurality of estimated geographic regions;

B. selecting one of said plurality of estimated geographic regions as a selected estimated region;

C. making a first determination as to whether said geographic point is located within said selected estimated region;

D. if said geographic point is located within said selected estimated region, then selecting a selected region, said selected region being the geographic region of said plurality of non-overlapping geographic regions that corresponds to said selected estimated region, and said selected region being defined by a boundary of a plurality of boundary points;

E. making a second determination as to whether said geographic point is located within said selected region by drawing a line of predetermined slope through said geographic point, checking whether said line intersects said selected region at said geographic point, and if said line intersects said selected region at said geographic point, then defining said second determination to be that said geographic point is located within said selected region; and

F. if said second determination determines that said geographic point is located within said selected region, then identifying said selected region.

20. The method of claim 19, wherein step E further comprises:

checking whether said line intersects said selected region at said geographic point only.

24. The method of 18 or 19 wherein each of said estimated geographic regions of said step A, totally encompasses each of said corresponding non-overlapping geographic regions.

25. A computer-readable medium on which is stored a computer program for identifying the geographic region of a geographic area which contains a geographic point comprising instructions which, when executed by a computer, perform the steps of:

A. dividing said geographic area into a plurality of non-overlapping geographic regions;

B. selecting one of said plurality of non-overlapping geographic regions as a selected region, said selected region being defined by a boundary of a plurality of boundary points;

C. making a determination as to whether said geographic point is located within said selected region by

drawing a line of predetermined slope through said geographic point and through said selected region so that said line intersects a first boundary point of said selected region and a second boundary point of said selected region,

checking whether said geographic point lies on said line between said first boundary point and said second boundary point,

if said geographic point lies on said line between said first boundary point and said second boundary point, then defining said determination to be that said geographic point is located within said selected region, and

if said geographic point does not lie on said line between said first boundary point and said second boundary point, then defining said determination to be that said geographic point is not located within said selected region; and

D. if said determination determines that said geographic point located within said selected region, then identifying said selected region.

26. The computer readable medium of claim 25, wherein said step C further comprises the steps of:

if said determination in said step C determines that said geographic point is not located within said selected region, then repeating said steps B and C with another one of said plurality of estimated geographic regions as said selected estimated region until said determination in said step C is that said geographic point is located within said selected region.

27. The computer readable medium of claim 25, wherein each region of said plurality of non-overlapping geographic regions has a name, and wherein said step of identifying said selected region further comprises identifying said selected region by the name of said selected region.

28. A computer-readable medium on which is stored a computer program for identifying the geographic region of a geographic area which contains a geographic point associated with a location, said geographic area being divided into a plurality of geographic regions, comprising instructions which, when executed by a computer, perform the steps of:

A. receiving an address for said location;

B. making an address determination as to whether said address is associated with an address match candidate, said address match candidate corresponding to a first geographic point;

C. if said address determination determines that said address is associated with said address match candidate, then selecting said first geographic point as said selected geographic point;

D. selecting one of said plurality of non-overlapping geographic regions as a selected region, said selected region being defined by a boundary of a plurality of boundary points;

E. making a determination as to whether said selected geographic point is located within said selected region by

drawing a line of predetermined slope through said selected geographic point and through said selected region so that said line intersects a first boundary point of said selected region and a second boundary point of said selected region, and

checking whether said selected geographic point lies on said line between said first boundary point and said second boundary point;

F. if said selected geographic point lies on said line between said first boundary point and said second boundary point, then defining said determination to be that said selected geographic point is located within said selected region; and

G. if said determination determines that said selected geographic point is located within said selected region, then identifying said selected region.

29. The computer readable medium of claim 28, further comprising the steps of:

H. if said address determination is that said address is not associated with said address match candidate, then receiving an intersection;

I. receiving an intersection match candidate, said intersection match candidate corresponding to a second geographic point;

J. making an intersection determination as to whether said address is associated with an intersection match candidate;

K. if said intersection determination is that said address is not associated with said intersection match candidate, then receiving a landmark;

L. receiving a landmark match candidate, said landmark match candidate corresponding to a third geographic point;

M. making a landmark determination as to whether said address is associated with a landmark match candidate; and

N. if said landmark determination is that said address is not associated with said landmark match candidate, then selecting a fourth geographic point associated with said zip code as said selected geographic point.

30. In a coordinate system having a plurality of points, each point defined by an x-coordinate and a y-coordinate, a method for identifying which of a plurality of non-overlapping regions of an area contains one of the points, comprising the steps of:

A. selecting one of the plurality of points as a selected point;

B. selecting one of the plurality of regions as a selected region, the selected region being defined by a plurality of region boundary points; and

C. determining whether the selected point is located within the selected region by;

(1) determining whether a straight line drawn through the selected point intersects the selected region at a first boundary point and a second boundary point;

(2) if the straight line intersects the selected region at the first boundary point and the second boundary point, then determining whether the selected point is located between the first boundary point and the second boundary point; and

(3) if the selected point is located between the first boundary point and the second boundary point, then determining that the selected point is located within the selected region.

31. The method of claim 30, wherein the straight line is a non-vertical line, and wherein step C(1) comprises the steps of:

(a) building a table of region boundary sides having a plurality of entries, each of the entries having a first region boundary point and a next consecutive region boundary point;

(b) comparing the selected point to a selected one of the entries;

(c) if the y-coordinate for the selected first region boundary point is greater than the y-coordinate for the selected point and the y-coordinate for the selected next consecutive region boundary point is less than the y-coordinate for the selected point, then determining that the straight line intersects the selected region at the first boundary point; and

(d) if the straight line intersects the selected region at the first boundary point, then determining the x-coordinate of the first boundary point using the x-coordinate and the y-coordinate of the selected first region boundary point, the x-coordinate and the y-coordinate of the selected next consecutive region boundary point, and the y-coordinate of the selected point.

32. The method of claim 31, wherein the steps (b)-(d) are repeated for the second boundary point.

33. The method of claim 31, further comprising the step of:

if the y-coordinate for the selected first region boundary point is not greater than the y-coordinate for the selected point or the y-coordinate for the selected next consecutive region boundary is not less than the y-coordinate for the selected point, then repeating steps (b)-(d) with a second selected one of the entries.

34. The method of claim 30, wherein step C(2) comprises:

(a) building a table of intersection points having a first entry comprising an odd intersection label and the first boundary point and a second entry comprising an even intersection label and the second boundary point;

(b) comparing the selected point to the first entry and the second entry; and

(c) if the x-coordinate of the selected point is located between the x-coordinate of the first boundary point and the x-coordinate of the second boundary point, then determining that the selected point is located between the first boundary point and the second boundary point.

35. The method of claim 30, wherein the straight line is a vertical line, and wherein step C(1) comprises the steps of:

(a) building a table of region boundary sides having a plurality of entries, each of the entries having a first region boundary point and a next consecutive region boundary point;

(b) comparing the selected point to a selected one of the entries;

(c) if the x-coordinate for the selected first region boundary point is greater than the x-coordinate for the selected point and the x-coordinate for the selected next consecutive region boundary point is less than the x-coordinate for the selected point, then determining that the vertical line intersects the selected region at the first boundary point; and

(d) determining the y-coordinate of the first boundary point using the x-coordinate and the y-coordinate of the selected first region boundary point, the x-coordinate and the y-coordinate of the selected next consecutive region boundary point, and the x-coordinate of the selected point.

36. The method of claim 35, wherein the steps (b)-(d) are repeated for the second boundary point.

37. The method of claim 30, wherein step C(2) comprises:

(a) building a table of intersection points having a first entry comprising an odd intersection label and the first boundary point and a second entry comprising an even intersection label and the second boundary point;

(b) comparing the selected point to the first entry and the second entry; and

(c) if the y-coordinate of the selected point is located between the first entry and the second entry, then determining that the selected point is located between the first boundary point and the second boundary point.

38. In a coordinate system having a plurality of points, each point defined by an x-coordinate and a y-coordinate, a method for identifying which of a plurality of non-overlapping regions of an area contains one of the points, comprising the steps of:

A. selecting one of the plurality of points as a selected point;

B. selecting one of the plurality of regions as a selected region, the selected region being defined by a plurality of region boundary points; and

C. determining whether the selected point is located within the selected region by;

(1) determining whether a straight line drawn through the selected point intersects the selected region only at the selected point; and

(2) if the straight line intersects the selected region only at the selected point, then determining that the selected point is located within the selected region.

39. The method of claim 38, wherein step C(1) comprises the steps of:

(a) building a table of region boundary sides having a plurality of entries, each of the entries having a first region boundary point and a next consecutive region boundary point;

(b) comparing the selected point to a selected one of the entries; and

(c) if the y-coordinate of the selected first region boundary point is equal to the y-coordinate of the selected point and the x-coordinate of the selected first region boundary point is equal to the x-coordinate of the selected point, then determining that the straight line intersects the selected region at the selected first region boundary point.

40. The method of claim 39, further comprising the steps of:

(d) building a table of intersection points having a first entry comprising an odd intersection label and the selected first region boundary point;

(e) if the straight line is tangential to the selected first region boundary point and the straight line does not intersect an immediately adjacent region boundary point, then creating a second entry in the table of intersection points comprising an even intersection label and the selected first region boundary point;

(f) comparing the selected point to the first entry and the second entry; and

(g) if the x-coordinate and the y-coordinate of the selected point is equal to the x-coordinate and the y-coordinate of the first entry and the second entry, then determining that the straight line intersects the selected region only at the selected point.

41. In a geographic area divided into a plurality of non-overlapping geographic regions, each of the geographic regions being defined by a region boundary of a plurality of region boundary points, a method for identifying the geographic region which contains a geographic point, comprising the steps of:

A. selecting one of the plurality of non-overlapping geographic regions as a selected region;

B. estimating the selected region with a selected estimated region;

C. making a first determination as to whether the geographic point is located within the selected estimated region;

D. if the geographic point is located within the selected estimated region, making a second determination as to whether the geographic point is located within the selected region; and

E. if the second determination in step D is that the geographic point is located within the selected region, then identifying the selected region.

42. The method of claim 41, wherein if the first determination in step C is that the geographic point is not located within the selected estimated region, then

repeating steps A, B and C with another one of the non-overlapping geographic regions until the first determination in the step C is that the estimated zone is located within the selected estimated region.

43. The method of claim 41, wherein if the second determination in step D is that the geographic point is not located within the selected region, then

repeating steps A, B, C, and D with another one of the non-overlapping geographic regions until the second determination in step D is that the geographic point is located within the selected region.

44. The method of claim 41, wherein step D comprises the steps of:

(1) determining whether a straight line drawn through the geographic point intersects the selected region at a first boundary point and a second boundary point;

(2) if the straight line intersects the selected region at the first boundary point and the second boundary point, then determining whether the geographic point is located between the first boundary point and the second boundary point; and

(3) if the geographic point is located between the first boundary point and the second boundary point, then determining that the geographic point is located within the selected region.

45. The method of claim 44, wherein the straight line is a non-vertical line, and wherein the step (1) comprises the steps of:

(a) building a table of region boundary sides having a plurality of entries, each of the entries having a first region boundary point and a next consecutive region boundary point;

(b) comparing the geographic point to a selected one of the entries;

(c) if the y-coordinate for the selected first region boundary point is greater than the y-coordinate for the geographic point and the y-coordinate for the selected next consecutive region boundary point is less than the y-coordinate for the geographic point, then determining that the straight line intersects the selected region at the first boundary point; and

(d) if the straight line intersects the selected region at the first boundary point, then determining the x-coordinate of the first boundary point using the x-coordinate and the y-coordinate of the selected first region boundary point, the x-coordinate and the y-coordinate of the selected next consecutive region boundary point, and the y-coordinate of the geographic point.

46. The method of claim 45, wherein steps (b)-(d) are repeated for the second boundary point.

47. The method of claim 44, wherein the straight line is a non-vertical line, and wherein the step (1) comprises the steps of:

(a) building a table of region boundary sides having a plurality of entries, each of the entries having a first region boundary point and a next consecutive region boundary point;

(b) comparing the geographic point to a selected one of the entries;

(c) if the x-coordinate for the selected first region boundary point is greater than the x-coordinate for the geographic point and the x-coordinate for the selected next consecutive region boundary point is less than the x-coordinate for the geographic point, then determining that the straight line intersects the selected region at the first boundary point; and

(d) if the straight line intersects the selected region at the first boundary point, then determining the y-coordinate of the first boundary point using the x-coordinate and the y-coordinate of the selected first region boundary point, the x-coordinate and the y-coordinate of the selected next consecutive region boundary point, and the x-coordinate of the geographic point.

48. The method of claim 44, wherein the step (2) comprises:

(a) building a table of intersection points having a first entry comprising an odd intersection label and the first boundary point and a second entry comprising an even intersection label and the second boundary point;

(b) comparing the geographic point to the first entry and the second entry; and

(c) if the x-coordinate of the geographic point is located between the x-coordinate of the first boundary point and the x-coordinate of the second boundary point, then determining that the geographic point is located between the first boundary point and the second boundary point.

49. The method of claim 41, wherein step D comprises the steps of:

(1) determining whether a straight line drawn through the geographic point intersects the selected region only at the geographic point; and

(2) if the straight line intersects the selected region only at the geographic point, then determining that the geographic point is located within the selected region.

50. The method of claim 49, wherein step (1) comprises the steps of:

(a) building a table of region boundary sides having a plurality of entries, each of the entries having a first region boundary point and a next consecutive region boundary point;

(b) comparing the geographic point to a selected one of the entries; and

(c) if the y-coordinate of the selected first region boundary point is equal to the y-coordinate of the geographic point and the x-coordinate of the selected first region boundary point is equal to the x-coordinate of the geographic point, then determining that the straight line intersects the selected region at the selected first region boundary point.

51. The method of claim 50, further comprising the steps of:

(d) building a table of intersection points having a first entry comprising an odd intersection label and the selected first region boundary point;

(e) if the straight line is tangential to the selected first region boundary point and the straight line does not intersect an immediately adjacent region boundary point, then creating a second entry in the table of intersection points comprising an even intersection label and the selected first region boundary point;

(f) comparing the geographic point to the first entry and the second entry; and

(g) if the x-coordinate and the y-coordinate of the geographic point is equal to the x-coordinate and the y-coordinate of the first entry and the second entry, then determining that the straight line intersects the selected region only at the geographic point.