Mapping uncertain geometries to graticules

• US 9,719,790 B2
• Filed: 07/09/2013
• Issued: 08/01/2017
• Est. Priority Date: 03/15/2013
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Ganti, Raghu K., Agrawal, Dakshi, Srivatsa, Mudhakar
• Primary Examiner(s): Rostami, Mohammad S
• Application Number:
  US13/937,500
• Publication Number:
  US 20140278228A1
• Time in Patent Office: 1,484 Days
• CPC Class Codes: G01C 21/3867 Geometry of map features, e.g. shape points, polygons or for simplified maps
• CPC Class Codes: G06F 16/29 Geographical information databases

Abstract

A geohash based cover for a geometry whose uncertainty is described as a circle with center point and a radius is disclosed. In one example, a geohash cover is computed that does not require any expensive geodesic calculations, providing roughly an order of magnitude improvement in speed up of cover calculation. In another example, distance computations are exact compared to a conventional process. In another example, the geohashes returned by the technique can vary between 4 to 9—with a median 6 (a certain conventional process would always return 9 hashes (all the 8 neighbors and the self geohash)). In another example, results are accurate, while still avoiding expensive geodesic computations.

Claims

1. A method for covering an uncertain geometry by a plurality of bounding boxes, the method comprising:

obtaining, by a processor, data identifying a radius of a circle corresponding to the uncertain geometry;

obtaining, by the processor, data identifying a point at which the uncertain geometry is centered;

obtaining, by the processor, data identifying a latitude circle radius associated with a latitude of the point at which the uncertain geometry is centered; and

determining, by the processor, a resolution of the bounding boxes, wherein the resolution of the bounding boxes is determined by;

determining a number of bits of a geohash in a latitude dimension at the latitude of the point at which the uncertain geometry is centered;

determining a number of bits in the geohash in a longitude dimension at the latitude of the point at which the uncertain geometry is centered;

determining a bit length of the geohash by adding the number of bits in the latitude dimension of the geohash with the number of bits in the longitude dimension of the geohash; and

dividing, by the processor, the latitude circle into 2^N segments, where N is equal to the bit length of the geohash.

2. The method of claim 1, further comprising outputting, by the processor, the resolution of each of the 2^N segments as the resolution of the bounding boxes.

3. The method of claim 2, wherein the resolution of the bounding boxes is of a length greater than or equal to the radius of the circle and less than or equal to 2 times the radius of the circle.

4. The method of claim 1, further comprising determining, with the processor, a location of the point at which the uncertain geometry is centered relative to a first one of the bounding boxes.

5. The method of claim 4, wherein the determining the location of the point at which the uncertain geometry is centered relative to the first one of the bounding boxes comprises finding a difference between a number of bits corresponding to the point and the bits of the first bounding box.

6. The method of claim 5, wherein the finding the difference between a number of bits corresponding to the point and the bits of the first bounding box comprises determining a distance in the latitude dimension from the point to the first bounding box and a distance in the longitude dimension from the point to the first bounding box.

7. The method of claim 6, wherein the distance in the latitude dimension from the point to the first bounding box and the distance in the longitude dimension from the point to the first bounding box are determined based upon the radius of the earth and the latitude of the point at which the uncertain geometry is centered.

8. The method of claim 4, further comprising determining, by the processor, a plurality of bounding boxes which are neighbors of the first bounding box.

9. The method of claim 8, further comprising outputting, by the processor, as the cover the first bounding box and the neighbors of the first bounding box.

10. The method of claim 1, wherein the processor obtains the data identifying the radius of the circle corresponding to the uncertain geometry via at least one of:

(a) input from a user; and

(b) reading of the data from an electronic file.

11. The method of claim 1, wherein the processor obtains the data identifying the point at which the uncertain geometry is centered via at least one of:

(a) input from a user; and

(b) reading of the data from an electronic file.

12. The method of claim 1, wherein the processor obtains the data identifying the latitude circle radius associated with the point at which the uncertain geometry is centered via at least one of:

(a) input from a user; and

(b) reading of the data from an electronic file.

13. The method of claim 1, wherein the number of bits in the latitude dimension (Bits_Lat) is computed, on the latitude circle, using the equation:

Bits_Lat=exp(R₀*(π

/R)),

where R₀ is the radius of the earth and R is the radius of the circle corresponding to the uncertain geometry.

14. The method of claim 1, wherein the number of bits in the longitude dimension (Bits_Lon) is computed using the equation:

Bits_Lon=exp(2*π

*(R_lat/R)),

where R_lat is the latitude circle radius and R is the radius of the circle corresponding to the uncertain geometry.

15. A computer program product comprising a non-transitory computer readable storage medium, tangibly embodying a program of instructions executable by the computer for performing a method of covering an uncertain geometry by a plurality of bounding boxes, the program of instructions, when executing, configure the computer to perform:

obtaining data identifying a radius of a circle corresponding to the uncertain geometry;

obtaining data identifying a point at which the uncertain geometry is centered;

obtaining data identifying a latitude circle radius associated with a latitude of the point at which the uncertain geometry is centered; and

determining a resolution of the bounding boxes, wherein the resolution of the bounding boxes is determined by;

determining a number of bits of a geohash in a latitude dimension at the latitude of the point at which the uncertain geometry is centered;

determining a number of bits in the geohash in a longitude dimension at the latitude of the point at which the uncertain geometry is centered;

determining a bit length of the geohash by adding the number of bits in the latitude dimension of the geohash with the number of bits in the longitude dimension of the geohash; and

dividing the latitude circle into 2^N segments, where N is equal to the bit length of the geohash.

16. The computer readable storage medium of claim 15, wherein the program of instructions, when executing, further configure the computer to perform outputting the resolution of each of the 2^N segments as the resolution of the bounding boxes.

17. The computer readable storage medium of claim 16, wherein the program of instructions, when executing, further configure the computer to perform:

determining a location of the point at which the uncertain geometry is centered relative to a first one of the bounding boxes;

determining a plurality of bounding boxes which are neighbors of the first bounding box; and

outputting as the cover the first bounding box and the neighbors of the first bounding box.

18. A computer-implemented system for covering an uncertain geometry by a plurality of bounding boxes, the system comprising:

a memory storage device;

a hardware processor coupled to said memory storage device and configured to;

obtain data identifying a radius of a circle corresponding to the uncertain geometry;

obtain data identifying a point at which the uncertain geometry is centered;

obtain data identifying a latitude circle radius associated with a latitude of the point at which the uncertain geometry is centered; and

determine a resolution of the bounding boxes, wherein to determine the resolution of the bounding boxes, said hardware processor is further configured to;

determine a number of bits of a geohash in a latitude dimension at the latitude of the point at which the uncertain geometry is centered;

determine a number of bits in the geohash in a longitude dimension at the latitude of the point at which the uncertain geometry is centered;

determine a bit length of the geohash by adding the number of bits in the latitude dimension of the geohash with the number of bits in the longitude dimension of the geohash; and

divide the latitude circle into 2^N segments, where N is equal to the bit length of the geohash.

19. The system of claim 18, wherein said hardware processor is further configured to:

output the resolution of each of the 2^N segments as the resolution of the bounding boxes;

determine a location of the point at which the uncertain geometry is centered relative to a first one of the bounding boxes;

determine a plurality of bounding boxes which are neighbors of the first bounding box; and

output as the cover the first bounding box and the neighbors of the first bounding box.

20. The system of claim 18, wherein said hardware processor is further configured to:

obtain the data identifying the radius of the circle corresponding to the uncertain geometry via at least one of;

(a) input from a user; and

(b) reading of the data from an electronic file;

obtain the data identifying the point at which the uncertain geometry is centered via at least one of;

(a) input from a user; and

(b) reading of the data from an electronic file; and

obtain the data identifying the latitude circle radius associated with the point at which the uncertain geometry is centered via at least one of;

(a) input from a user; and

(b) reading of the data from an electronic file.