Method for identifying the geographic region of a geographic area which contains a geographic zone

• US 5,978,747 A
• Filed: 04/20/1998
• Issued: 11/02/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): Barlow, John
• Assistant Examiner(s): VO, HIEN XUAN
• Application Number:
  US09/063,417
• Time in Patent Office: 561 Days
• Field of Search: 702/150, 345/133, 345/418, 345/435, 345/438, 701/208, 701/212, 455/422, 455/429
• US Class Current: 702/150
• CPC Class Codes: G01C 21/387 Organisation of map data, e.g. version management or database structures

Abstract

Identifying the geographic region of a geographic area which contains a geographic zone. 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. To determine whether a zone boundary point is located within the selected region, a determination is made as to whether a line of predetermined slope drawn through the zone boundary point intersects the region boundary of the selected region. If the line intersects the selected region, then a determination is made as to whether the zone boundary point is located within the selected region.

Claims

1. 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 a zone, the zone being defined by a plurality of zone boundary points, comprising the steps of:

A. selecting one of the plurality of zone boundary points as a selected zone boundary 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;

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

(1) determining whether a straight line drawn through the selected zone boundary 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 zone boundary point is located between the first boundary point and the second boundary point; and

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

D. repeating step C with another one of the plurality of zone boundary points as the selected zone boundary point.

2. The method of claim 1, 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 zone boundary 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 zone boundary point and the y-coordinate for the selected next consecutive region boundary point is less than the y-coordinate for the selected zone boundary 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 zone boundary point.

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

4. The method of claim 2, 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 zone boundary point or the y-coordinate for the selected next consecutive region boundary is not less than the y-coordinate for the selected zone boundary point, then repeating steps (b)-(d) with a second selected one of the entries.

5. The method of claim 2, 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 zone boundary point to the first entry and the second entry; and

(c) if the x-coordinate of the selected zone boundary 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 zone boundary point is located between the first boundary point and the second boundary point.

6. The method of claim 1, 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 zone boundary 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 zone boundary point and the x-coordinate for the selected next consecutive region boundary point is less than the x-coordinate for the selected zone boundary 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 zone boundary point.

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

8. The method of claim 6, 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 zone boundary point to the first entry and the second entry; and

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

9. 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 a zone, the zone being defined by a plurality of zone boundary points, comprising the steps of:

A. selecting one of the plurality of zone boundary points as a selected zone boundary 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;

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

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

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

D. determining whether a second selected zone boundary point is located within the selected region.

10. The method of claim 9, 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 zone boundary 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 zone boundary point and the x-coordinate of the selected first region boundary point is equal to the x-coordinate of the selected zone boundary point, then determining that the straight line intersects the selected region at the selected first region boundary point.

11. The method of claim 10, 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 zone boundary point to the first entry and the second entry; and

(g) if the x-coordinate and the y-coordinate of the selected zone boundary 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 zone boundary point.

12. 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, and a plurality of non-overlapping geographic zones, each of the 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 the geographic zone with an estimated zone;

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

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

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

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

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

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

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

13. The method of claim 12, wherein if the first determination in step D is that the estimated zone is not located within the selected estimated region, then

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

14. The method of claim 12, wherein if the second determination in step F is that the selected zone boundary point is not located within the selected region, then

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

15. The method of claim 12, wherein step F comprises the steps of:

(1) determining whether a straight line drawn through the selected zone boundary 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 zone boundary point is located between the first boundary point and the second boundary point; and

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

16. The method of claim 15, 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 selected zone boundary 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 zone boundary point and the y-coordinate for the selected next consecutive region boundary point is less than the y-coordinate for the selected zone boundary 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 zone boundary point.

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

18. The method of claim 15, 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 selected zone boundary 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 zone boundary point and the x-coordinate for the selected next consecutive region boundary point is less than the x-coordinate for the selected zone boundary 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 selected zone boundary point.

19. The method of claim 15, 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 selected zone boundary point to the first entry and the second entry; and

(c) if the x-coordinate of the selected zone boundary 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 zone boundary point is located between the first boundary point and the second boundary point.

20. The method of claim 12, wherein step F comprises the steps of:

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

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

21. The method of claim 20, 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 selected zone boundary 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 zone boundary point and the x-coordinate of the selected first region boundary point is equal to the x-coordinate of the selected zone boundary point, then determining that the straight line intersects the selected region at the selected first region boundary point.

22. The method of claim 21, 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 zone boundary point to the first entry and the second entry; and

(g) if the x-coordinate and the y-coordinate of the selected zone boundary 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 zone boundary point.