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

Claim 3

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.

Claim 4

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.

Claim 5

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.

Claim 6

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.

Claim 9

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.

Claim 10

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.

Claim 11

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.

Claim 12

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.

Claim 13

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.

Claim 14

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.

Claim 15

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.

Claim 16

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.

Claim 17

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.

Claim 18

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.

Claim 19

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.

Claim 20

The method of claim 13, wherein said step B further comprises: checking whether said line intersects said selected region at said geographic point only.

Claim 27

The method of claim 19, wherein step E further comprises: checking whether said line intersects said selected region at said geographic point only.

Claim 33

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.

Claim 34

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.

Claim 35

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.

Claim 36

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.

Claim 37

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.

Claim 38

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.

Claim 39

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.

Claim 40

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.

Claim 41

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.

Claim 42

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.

Claim 43

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

Claim 44

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.

Claim 45

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.

Claim 46

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.

Claim 47

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

Claim 48

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.

Claim 49

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.

Claim 50

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.

Claim 51

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.

Claim 52

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.

Claim 53

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.

Claim 54

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.

Claim 55

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.

Claim 56

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.

Claim 57

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.

Claim 58

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.

Claim 59

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

Claim 60

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.

Claim 61

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.

Claim 62

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.

Claim 63

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.

Claim 64

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.