Methods and Systems for Fast Scan Location Identification

• US 20090198659A1
• Filed: 02/06/2009
• Published: 08/06/2009
• Est. Priority Date: 02/06/2008
• Status: Active Grant

• Current Assignee: iControl, Inc.
• Original Assignee: iControl, Inc.
• Inventors: Erickson, David Lee
• Granted Patent: US 8,199,972 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06Q 10/025 Coordination of plural reservations, e.g. plural trip segments, transportation combined with accommodation
• CPC Class Codes: G06Q 10/087 Inventory or stock management, e.g. order filling, procurement or balancing against orders

Abstract

An unknown named territory encloses a known physical target location that is specified by a target longitude and a target latitude. An operation is performed to identify a number of rectangular-shaped terrestrial areas that each enclose both the target longitude and the target latitude. Each of the identified rectangular-shaped terrestrial areas respectively encloses a polygonal-shaped named territory. Each polygonal-shaped named territory is defined by a respective circumscribing set of contiguously positioned vectors. An operation is performed to evaluate the circumscribing sets of contiguously positioned vectors of the polygonal-shaped named territories to determine if a given polygonal-shaped named territory includes both the target longitude and the target latitude. When both the target longitude and the target latitude are found to reside within a given polygonal-shaped named territory, the identity of the given polygonal-shaped named territory is conveyed.

Claims

1. A method for determining an identity of a named territory enclosing a physical target location specified by a target longitude and a target latitude, comprising:

identifying a number of rectangular-shaped terrestrial areas that each enclose both the target longitude and the target latitude, wherein each of the number of identified rectangular-shaped terrestrial areas respectively encloses a number of polygonal-shaped named territories, and wherein each polygonal-shaped named territory is defined by a respective circumscribing set of contiguously positioned vectors;

evaluating the circumscribing sets of contiguously positioned vectors of the number of polygonal-shaped named territories to determine if a given polygonal-shaped named territory includes both the target longitude and the target latitude; and

conveying an identity of the given polygonal-shaped named territory as the named territory enclosing the physical target location when both the target longitude and the target latitude are found to reside within the given polygonal-shaped named territory.

2. The method of claim 1, wherein evaluating the circumscribing set of contiguously positioned vectors of a given polygonal-shaped named territory includes determining that the given polygonal-shaped named territory includes both the target longitude and the target latitude when all of the following are true,

the target latitude is not greater than a latitude of a greatest latitudinal point along a closest easterly vector to the physical target location that spans the target longitude,

the target latitude is not less than a latitude of a least latitudinal point along a closest westerly vector to the physical target location that spans the target longitude,

the target longitude is not less than a longitude of a least longitudinal point along a closest northerly vector to the physical target location that spans the target latitude, and

the target longitude is not greater than a longitude of a greatest longitudinal point along a closest southerly vector to the physical target location that spans the target latitude,

wherein each of the closest easterly vector, closest westerly vector, closest northerly vector, and closest southerly vector are vectors within the circumscribing set of contiguously positioned vectors under evaluation.

3. The method of claim 2, wherein the closest easterly vector corresponds to a first vector within the circumscribing set of contiguously positioned vectors that has a shortest straight-line distance to the physical target location as measured from any point along a length of the first vector, and

wherein the closest westerly vector corresponds to a second vector within the circumscribing set of contiguously positioned vectors that has a shortest straight-line distance to the physical target location as measured from any point along a length of the second vector, and

wherein the closest northerly vector corresponds to a third vector within the circumscribing set of contiguously positioned vectors that has a shortest straight-line distance to the physical target location as measured from any point along a length of the third vector, and

wherein the closest southerly vector corresponds to a fourth vector within the circumscribing set of contiguously positioned vectors that has a shortest straight-line distance to the physical target location as measured from any point along a length of the fourth vector.

4. The method of claim 3, wherein the shortest straight-line distance to the physical target location is measured as a perpendicular distance extending from a given vector to the physical target location when the given vector spans the physical target location either longitudinally or latitudinally, and

wherein the shortest straight-line distance to the physical target location is measured as a straight-line distance extending from the physical target location to a closest end of the given vector when the given vector does not span the physical target location either longitudinally or latitudinally.

5. The method of claim 1, wherein the rectangular-shaped terrestrial areas and corresponding polygonal-shaped named territories are each defined by a number of vector coordinates within a searchable database, wherein each vector coordinate is defined by a latitude value and a longitude value.

6. The method of claim 5, wherein identifying the number of rectangular-shaped terrestrial areas and evaluating the circumscribing sets of contiguously positioned vectors of the number of polygonal-shaped named territories are both performed by querying the searchable database.

7. The method of claim 1, wherein each rectangular-shaped terrestrial area is defined to enclose its corresponding polygonal-shaped named territory as tightly as possible.

8. The method of claim 1, wherein at least one boundary of each identified rectangular-shaped terrestrial areas crosses at least one boundary of another identified rectangular-shaped terrestrial area.

9. The method of claim 1, wherein the identity of each polygonal-shaped named territory is either a country, a territory, a state, a county, a city, a district, or any other named municipality.

10. The method of claim 1, wherein the identity of the given polygonal-shaped named territory is conveyed through a digital data communication from which the identity is displayed in either a graphical or textual manner.

11. A method for generating a database to determine an identity of a named territory enclosing a physical target location specified by a target longitude and a target latitude, comprising:

obtaining vectorized descriptions of polygonal-shaped named territories;

storing the vectorized descriptions of the polygonal-shaped named territories within a searchable database on a computer readable medium;

defining a respective rectangular-shaped terrestrial area for each polygonal-shaped named territory such that each rectangular-shaped terrestrial area encloses its corresponding polygonal-shaped named territory as tightly as possible;

storing a vectorized description of each rectangular-shaped terrestrial area within the searchable database on the computer readable medium; and

defining the searchable database on the computer readable medium such that vectorized descriptions of the rectangular-shaped terrestrial areas and their corresponding polygonal-shaped named territories are searchable to determine which polygonal-shaped named territory includes the target longitude and target latitude.

12. The method of claim 11, wherein the vectorized description of a given polygonal-shaped named territory is defined by a respective circumscribing set of contiguously positioned vectors, wherein each vector is defined by a pair of line segment end-points, wherein each end-point is defined by a latitude value and a longitude value.

13. The method of claim 11, wherein each rectangular-shaped terrestrial area is defined by a corresponding set of minimum longitude, maximum longitude, minimum latitude, and maximum latitude.

14. The method of claim 13, wherein the minimum longitude of a given rectangular-shaped terrestrial area is equal to a least longitudinal value of any vector coordinate within the vectorized description of the polygonal-shaped named territory corresponding to the given rectangular-shaped terrestrial area, and

wherein the maximum longitude of the given rectangular-shaped terrestrial area is equal to a greatest longitudinal value of any vector coordinate within the vectorized description of the polygonal-shaped named territory corresponding to the given rectangular-shaped terrestrial area, and

wherein the minimum latitude of the given rectangular-shaped terrestrial area is equal to a least latitudinal value of any vector coordinate within the vectorized description of the polygonal-shaped named territory corresponding to the given rectangular-shaped terrestrial area, and

wherein the maximum latitude of the given rectangular-shaped terrestrial area is equal to a greatest latitudinal value of any vector coordinate within the vectorized description of the polygonal-shaped named territory corresponding to the given rectangular-shaped terrestrial area.

15. The method of claim 11, wherein multiple rectangular-shaped terrestrial areas are defined for a common polygonal-shaped named territory, such that the multiple rectangular-shaped terrestrial areas do not overlap each other, and such that each of the multiple rectangular-shaped terrestrial areas encloses its corresponding portion of the common polygonal-shaped named territory as tightly as possible, and

wherein each of the multiple rectangular-shaped terrestrial areas is stored within the searchable database on the computer readable medium in association with the common polygonal-shaped named territory.

16. The method of claim 15, wherein the multiple rectangular-shaped terrestrial areas are defined to minimize a difference between a combined area of the multiple rectangular-shaped terrestrial areas and an overall area of the common polygonal-shaped named territory.

17. The method of claim 11, wherein the identity of each polygonal-shaped named territory is either a country, a territory, a state, a county, a city, a district, or any other named municipality.

18. A method for determining an identity of a named route closest to a physical target location specified by a target longitude and a target latitude, comprising:

identifying a number of rectangular-shaped terrestrial areas that each enclose both the target longitude and the target latitude, wherein each of the number of identified rectangular-shaped terrestrial areas respectively encloses a portion of polygonal-shaped named route, and wherein each polygonal-shaped named route is defined by a respective circumscribing set of contiguously positioned vectors;

evaluating the circumscribing sets of contiguously positioned vectors of the number of polygonal-shaped named routes to determine if a given polygonal-shaped named route includes both the target longitude and the target latitude; and

conveying an identity of the given polygonal-shaped named route as the named route enclosing the physical target location when both the target longitude and the target latitude are found to reside within the given polygonal-shaped named route.

19. The method of claim 18, wherein evaluating the circumscribing set of contiguously positioned vectors of a given polygonal-shaped named route includes determining that the given polygonal-shaped named route includes both the target longitude and the target latitude when all of the following are true,

the target latitude is not greater than a latitude of a greatest latitudinal point along a closest easterly vector to the physical target location that spans the target longitude,

the target latitude is not less than a latitude of a least latitudinal point along a closest westerly vector to the physical target location that spans the target longitude,

the target longitude is not less than a longitude of a least longitudinal point along a closest northerly vector to the physical target location that spans the target latitude, and

the target longitude is not greater than a longitude of a greatest longitudinal point along a closest southerly vector to the physical target location that spans the target latitude,

wherein each of the closest easterly vector, closest westerly vector, closest northerly vector, and closest southerly vector are vectors within the circumscribing set of contiguously positioned vectors under evaluation.

20. The method of claim 19, wherein the closest easterly vector corresponds to a first vector within the circumscribing set of contiguously positioned vectors that has a shortest straight-line distance to the physical target location as measured from any point along a length of the first vector, and

wherein the closest westerly vector corresponds to a second vector within the circumscribing set of contiguously positioned vectors that has a shortest straight-line distance to the physical target location as measured from any point along a length of the second vector, and

wherein the closest northerly vector corresponds to a third vector within the circumscribing set of contiguously positioned vectors that has a shortest straight-line distance to the physical target location as measured from any point along a length of the third vector, and

wherein the closest southerly vector corresponds to a fourth vector within the circumscribing set of contiguously positioned vectors that has a shortest straight-line distance to the physical target location as measured from any point along a length of the fourth vector.

21. The method of claim 20, wherein the shortest straight-line distance to the physical target location is measured as a perpendicular distance extending from a given vector to the physical target location when the given vector spans the physical target location either longitudinally or latitudinally, and

wherein the shortest straight-line distance to the physical target location is measured as a straight-line distance extending from the physical target location to a closest end of the given vector when the given vector does not span the physical target location either longitudinally or latitudinally.

22. The method of claim 18, wherein the rectangular-shaped terrestrial areas and corresponding polygonal-shaped named routes are each defined by a number of vector coordinates within a searchable database, wherein each vector coordinate is defined by a latitude value and a longitude value.

23. The method of claim 22, wherein identifying the number of rectangular-shaped terrestrial areas and evaluating the circumscribing sets of contiguously positioned vectors of the number of polygonal-shaped named routes are both performed by querying the searchable database.

24. The method of claim 18, wherein each rectangular-shaped terrestrial area is defined to enclose its corresponding polygonal-shaped named route as tightly as possible.

25. The method of claim 18, wherein the identity of each polygonal-shaped named route is either a waterway, a road, a railway, or any other named route of conveyance that is substantially stationary.

26. The method of claim 18, wherein multiple rectangular-shaped terrestrial areas are defined for a common polygonal-shaped named route, such that the multiple rectangular-shaped terrestrial areas do not overlap each other, and such that each of the multiple rectangular-shaped terrestrial areas encloses its corresponding portion of the common polygonal-shaped named route as tightly as possible, and

wherein each of the multiple rectangular-shaped terrestrial areas is associated with the common polygonal-shaped named route.

27. The method of claim 26, wherein each of the multiple rectangular-shaped terrestrial areas is associated with a uniquely named segment of the common polygonal-shaped named route.

28. The method of claim 18, wherein the identity of the given polygonal-shaped named route is conveyed through a digital data communication from which the identity is displayed in either a graphical or textual manner.