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

• US 5,796,634 A
• Filed: 04/01/1997
• Issued: 08/18/1998
• Est. Priority Date: 04/01/1997
• Status: Expired due to Term

• Current Assignee: Qualcomm FYX Incorporated (Qualcomm, Inc.)
• Original Assignee: BellSouth Corporation (AT&T, Inc.)
• Inventors: Craport, William N., Winters, Bruce C.
• Primary Examiner(s): Voeltz, Emanuel Todd
• Assistant Examiner(s): Vo, Hien
• Application Number:
  US08/831,040
• Time in Patent Office: 504 Days
• Field of Search: 364/559, 345/133, 345/418, 345/435, 455/4.2, 455/429, 455/422, 340/988, 340/995, 701/208, 701/212, 342/357, 379/221
• US Class Current: 702/150
• CPC Class Codes: G01C 21/387 Organisation of map data, e.g. version management or database structures

Abstract

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

Claims

1. A method for identifying the geographic region of a geographic area which contains a geographic zone, said geographic zone being defined by a zone boundary of a plurality of zone boundary points, comprising the steps of:

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

B. selecting one of said plurality of zone boundary points of said geographic zone as a selected zone boundary point;

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

D. making a first determination as to whether said selected zone boundary point is located within said selected region by

drawing a line of predetermined slope through said selected zone boundary 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 selected zone boundary point lies on said line between said first boundary point and said second boundary point, and

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

E. if said first determination is that said selected zone boundary point is located within said selected region, then repeating said step D with another one of said plurality of zone boundary points as a selected zone boundary point; and

F. if at least a predetermined percentage of said plurality of zone boundary points is located within said selected region, then identifying said selected region.

2. The method of claim 1 wherein said step D further comprises:

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

8. The method of claims 1 or 3 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.

9. The method of claims 2 or 7, wherein said first determination in said step D is that said selected zone boundary point is not located within said selected region, further comprising,

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

3. A method for identifying the geographic region of a geographic area which contains a geographic zone, said geographic zone being defined by a zone boundary of a plurality of zone boundary points, comprising the steps of:

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

B. selecting one of said plurality of zone boundary points of said geographic zone as a selected zone boundary point;

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

D. making a first determination as to whether said selected zone boundary point is located within said selected region by

drawing a line of predetermined slope through said selected zone boundary point and through said selected region,

checking whether said line intersects said selected region at said selected zone boundary point, and

if said line intersects said selected region at said selected zone boundary point, then defining said first determination to be that said selected zone boundary point is located within said s elected region;

E. if said first determination is that said selected zone boundary point is located within said selected region, then selecting another one of said plurality of zone boundary points as a selected zone boundary point and making a second determination as to whether said selected zone boundary point is located within said selected region; and

F. if at least a predetermined percentage of said plurality of zone boundary points is located within said selected region, then identifying said selected region.

4. The method of claim 3 wherein step D further comprises:

checking whether said line intersects said selected region at said selected zone boundary point only.

5. The method of claim 3 wherein said step E of making a second determination as to whether said selected zone boundary point is located within said selected region further comprises:

drawing a line of predetermined slope through said selected zone boundary 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 selected zone boundary point lies on said line between said first boundary point and said second boundary point; and

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

6. The method of claim 3 wherein said step E of making a second determination as to whether said selected zone boundary point is located within said selected region further comprises:

drawing a line of predetermined slope through said selected zone boundary point and through said selected region;

checking whether said line intersects said selected region at said selected zone boundary point; and

if said line intersects said selected region at said selected zone boundary point, then defining said first determination to be that said selected zone boundary point is located within said selected region.

7. The method of claim 3 wherein step D further comprises:

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

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

A. estimating said geographic zone with an estimated zone;

B. selecting one of said plurality of non-overlapping geographic regions as a selected region;

C. estimating said selected region with a selected estimated region;

D. making a first determination as to whether said estimated zone is located within said selected estimated region;

E. if said estimated zone is located within said selected estimated region, selecting one of said plurality of zone boundary points of said geographic zone as a selected zone boundary point;

F. making a second determination as to whether said selected zone boundary point is located within said selected region by

drawing a line of predetermined slope through said selected zone boundary 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 selected zone boundary point lies on said line between said first boundary point and said second boundary point, and

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

G. if said second determination in said step F is that said selected zone boundary point is located within said selected region, then repeating said step F with another one of said plurality of zone boundary points as a selected zone boundary point; and

H. if at least a predetermined percentage of said plurality of zone boundary points is located within said selected region, then identifying said selected region.

12. The method of claims 10 or 11, wherein if said first determination in said step D is that said estimated zone is not located within said selected estimated region, then

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

13. The method of claims 10 or 11, wherein if said second determination in said step F is that said selected zone boundary point is not located within said selected region, then

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

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

A. estimating said geographic zone with an estimated zone;

B. selecting one of said plurality of non-overlapping geographic regions as a selected region;

C. estimating said selected region with a selected estimated region;

D. making a first determination as to whether said estimated zone is located within said selected estimated region;

E. if said estimated zone is located within said selected estimated region, selecting one of said plurality of zone boundary points of said geographic zone as a selected zone boundary point;

F. making a second determination as to whether said selected zone boundary point is located within said selected region by

drawing a line of predetermined slope through said selected zone boundary point and through said selected region, and

checking whether said line intersects said selected region at said selected zone boundary point, and

if said line intersects said selected region at said selected zone boundary point, then defining said second determination to be that said selected zone boundary point is located within said selected region;

G. if said second determination in said step F is that said selected zone boundary point is located within said selected region, then selecting another one of said plurality of zone boundary points as a selected zone boundary point and making a third determination as to whether said selected zone boundary point is located within said selected region; and

H. if at least a predetermined percentage of said plurality of zone boundary points is located within said selected region, then identifying said selected region.

14. The method of claim 11, wherein said step F further comprises

checking whether said line intersects said selected region at said selected zone boundary point only.

15. The method of claim 11 wherein said step of making a third determination as to whether said selected zone boundary point is located within said selected region comprises:

drawing a line of predetermined slope through said selected zone boundary 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 selected zone boundary point lies on said line between said first boundary point and said second boundary point; and

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

16. The method of claim 11 wherein said step of making a third determination as to whether said selected zone boundary point is located within said selected region comprises:

drawing a line of predetermined slope through said selected zone boundary point and through said selected region, and

checking whether said line intersects said selected region at said selected zone boundary point, and

if said line intersects said selected region at said selected zone boundary point, then defining said third determination to be that said selected zone boundary point is located within said selected region.

17. The method of claims 11 or 12 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.

18. The method of claims 11 or 12 wherein said estimated zone totally encompasses said geographic zone.

19. The method of claims 11 or 12 wherein said selected estimated region totally encompasses said selected region.

20. A computer-readable medium on which is stored a computer program for identifying the geographic region of a geographic area which contains a geographic zone, said geographic area being divided into a plurality of non-overlapping geographic regions, each of said geographic regions being defined by a region boundary of a plurality of region boundary points, and a plurality of non-overlapping geographic zones, each of said geographic zones being defined by a zone boundary of a plurality of zone boundary points comprising instructions which, when executed by a computer, perform the steps of:

A. selecting one of said plurality of zone boundary points of said geographic zone as a selected zone boundary point;

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

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

drawing a line of predetermined slope through said selected zone boundary 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 selected zone boundary point lies on said line between said first boundary point and said second boundary point,

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

if said selected zone boundary 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 selected zone boundary point is not located within said selected region;

D. if said determination in said step C is that said selected zone boundary point is located within said selected region, then repeating said step C with another one of said plurality of zone boundary points as said selected zone boundary point; and

E. if at least a predetermined percentage of said plurality of zone boundary points is located within said selected region, identifying said selected region.

21. The computer-readable medium of claim 20 wherein said determination in said step C is that said selected zone boundary point is not located within said selected region, and

wherein said step D of operating upon said determination further comprises:

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

22. The computer-readable medium of claim 20 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.