TECHNIQUES FOR DENSITY MAPPING

• US 20110170799A1
• Filed: 01/12/2010
• Published: 07/14/2011
• Est. Priority Date: 01/12/2010
• Status: Active Grant

• Current Assignee: Palantir Technologies Incorporated
• Original Assignee: Palantir Technologies Incorporated
• Inventors: Carrino, John Antonio, Cervelli, Daniel Patrick
• Granted Patent: US 8,564,596 B2
• Time in Patent Office: Days
• US Class Current: 382/285
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06T 17/05 Geographic models
• CPC Class Codes: G09B 29/007 using computer methods

Abstract

Techniques in a data processor for drawing a density surface on a map in a manner that more accurately accounts for projection distortion in the map. According to one embodiment, data is maintained that represents a geotagged event. A map plane is divided into a plurality of cells and an origin cell corresponding to the geotagged event is identified. Density values are allocated to cells surrounding the origin cell based on geodetic distances between geographic coordinates corresponding to surrounding cells and the geographic coordinate of the geotagged event. A density surface based on the cell allocations is then displayed on a map. By allocating density values to cells based on geodetic distances, the resulting density surface displayed on the map more accurately accounts for projection distortions in the area of the map on which density surface is displayed.

Claims

1. A method for displaying a density surface on a map, the method comprising:

maintaining data that represents an association between a value and a first geographic coordinate;

dividing a map plane into a plurality of cells;

identifying a first cell of said plurality of cells based at least in part on said first geographic coordinate;

for at least one cell of said plurality of cells in proximity to said first cell,

determining a first planar coordinate in said map plane that corresponds to the at least one cell,

transforming said first planar coordinate into a second geographic coordinate,

computing a geodetic distance between said second geographic coordinate and a geographic coordinate corresponding to said first cell,

determining a density value to be allocated to the at least one cell based at least in part on said geodetic distance, and

allocating the density value to the at least one cell;

causing a density surface to be displayed on a map based at least in part on the density value allocated to the at least one cell; and

wherein the method is performed by one or more computing devices.

2. The method of claim 1, wherein identifying the first cell of said plurality of cells based on said first geographic coordinate comprises:

transforming said first geographic coordinate into a second planar coordinate in said map plane; and

identifying, as the first cell, a cell of said plurality of cells that contains said second planar coordinate.

3. The method of claim 2,

wherein the second planar coordinate corresponds to the center of said first cell.

4. The method of claim 1, wherein said first geographic coordinate and said geographic coordinate corresponding to the first cell is the same geographic coordinate.

5. The method of claim 1, wherein said first planar coordinate corresponds to the center of the at least one cell.

6. The method of claim 1, wherein transforming said first planar coordinate into the second geographic coordinate comprises transforming said first planar coordinate into the second geographic coordinate using an inverse map projection function.

7. The method of claim 1, wherein allocating the density value to the at least one cell comprises adding the density value to a density value previously allocated to the at least one cell.

23. The method of claim 1, wherein computing the geodetic distance between the second geographic coordinate and the geographic coordinate corresponding to the first cell comprises computing a great circle distance between the second geographic coordinate and the geographic coordinate corresponding to the first cell.

8. A non-transitory computer-readable medium storing instructions which, when executed by one or more processors, cause the one or more processors to perform:

maintaining data that represents an association between a value and a first geographic coordinate;

dividing a map plane into a plurality of cells;

identifying a first cell of said plurality of cells based at least in part on said first geographic coordinate;

for at least one cell of said plurality of cells in proximity to said first cell,

determining a first planar coordinate in said map plane that corresponds to the at least one cell,

transforming said first planar coordinate into a second geographic coordinate,

computing a geodetic distance between said second geographic coordinate and a geographic coordinate corresponding to said first cell,

determining a density value to be allocated to the at least one cell based at least in part on said geodetic distance, and

allocating the density value to the at least one cell; and

causing a density surface to be displayed on a map based at least in part on the density value allocated to the at least one cell.

9. The non-transitory computer-readable medium of claim 8, wherein identifying the first cell of said plurality of cells based on said first geographic coordinate comprises:

transforming said first geographic coordinate into a second planar coordinate in said map plane; and

identifying, as the first cell, a cell of said plurality of cells that contains said second planar coordinate.

10. The non-transitory computer-readable medium of claim 9,

wherein the second planar coordinate corresponds to the center of said first cell.

11. The non-transitory computer-readable medium of claim 8, wherein said first geographic coordinate and said geographic coordinate corresponding to the first cell is the same geographic coordinate.

12. The non-transitory computer-readable medium of claim 8, wherein said first planar coordinate corresponds to the center of the at least one cell.

13. The non-transitory computer-readable medium of claim 8, wherein transforming said first planar coordinate into the second geographic coordinate comprises transforming said first planar coordinate into the second geographic coordinate using an inverse map projection function.

14. The non-transitory computer-readable medium of claim 8, wherein allocating the density value to the at least one cell comprises adding the density value to a density value previously allocated to the at least one cell.

24. The non-transitory computer-readable medium of claim 8, wherein computing the geodetic distance between the second geographic coordinate and the geographic coordinate corresponding to the first cell comprises computing a great circle distance between the second geographic coordinate and the geographic coordinate corresponding to the first cell.

15. A computer system comprising:

a processor;

a memory;

density surface generation logic; and

density surface display driving logic;

the memory configured to maintain data that represents an association between a value and a first geographic coordinate;

the density surface generation logic coupled to said memory and configured to transform a state of said memory by;

dividing a map plane into a plurality of cells;

identifying a first cell of said plurality of cells based at least in part on said first geographic coordinate;

for at least one cell of said plurality of cells in proximity to said first cell,

determining a first planar coordinate in said map plane that corresponds to the at least one cell,

transforming said first planar coordinate into a second geographic coordinate,

computing a geodetic distance between said second geographic coordinate and a geographic coordinate corresponding to said first cell,

determining a density value to be allocated to the at least one cell based at least in part on said geodetic distance,

allocating the density value to the at least one cell; and

the density surface display driving logic coupled to said memory and configured to cause, based at least in part on the density value allocated to the at least one cell, display of a density surface on a map on a computer display device.

16. The computer system of claim 15, wherein identifying the first cell of said plurality of cells based on said first geographic coordinate comprises:

transforming said first geographic coordinate into a second planar coordinate in said map plane; and

identifying, as the first cell, a cell of said plurality of cells that contains said second planar coordinate.

17. The computer system of claim 16,

wherein the second planar coordinate corresponds to the center of said first cell.

18. The computer system of claim 15, wherein said first geographic coordinate and said geographic coordinate corresponding to the first cell is the same geographic coordinate.

19. The computer system of claim 15, wherein said first planar coordinate corresponds to the center of the at least one cell.

20. The computer system of claim 15, wherein transforming said first planar coordinate into the second geographic coordinate comprises transforming said first planar coordinate into the second geographic coordinate using an inverse map projection function.

21. The computer system of claim 15, wherein allocating the density value to the at least one cell comprises adding the density value to a density value previously allocated to the at least one cell.

25. The computer system of claim 15, wherein computing the geodetic distance between the second geographic coordinate and the geographic coordinate corresponding to the first cell comprises computing a great circle distance between the second geographic coordinate and the geographic coordinate corresponding to the first cell.

22. A method implemented in a computer having a processor and memory, the method comprising:

maintaining data that represents an association between a value and a first geographic coordinate;

dividing a map plane into a first plurality of cells;

identifying a first cell of said first plurality of cells based on said first geographic coordinate;

allocating density values to a second plurality of cells of said first plurality of cells that surround said first cell based on geodetic distances between geographic coordinates that correspond to said second plurality of cells and a geographic coordinate that corresponds to said first cell; and

causing a density surface to be displayed on a map based on the density values allocated to the second plurality of cells.