Projecting geographic data from a spherical surface to two-dimensional cartesian space

• US 8,896,601 B1
• Filed: 02/15/2011
• Issued: 11/25/2014
• Est. Priority Date: 10/12/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Norman, Phil
• Primary Examiner(s): CHOW, JEFFREY J
• Application Number:
  US13/027,905
• Time in Patent Office: 1,379 Days
• Field of Search: 345/419, 345/427, 345/582, 345/648, 345/584, 345/586, 345/649, 345/585, 345/672
• US Class Current: 345/427
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06T 15/10 Geometric effects
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects
• CPC Class Codes: G06T 17/05 Geographic models
• CPC Class Codes: G06T 19/00 Manipulating 3D models or images for computer graphics
• CPC Class Codes: G06T 2219/021 Flattening

Abstract

A method for projecting geographic data (e.g., latitude and longitude coordinates) from a spherical surface onto a two-dimensional Cartesian space is provided. Such a capability can employ a coordinate testing and transformation method to map the projected geographic data within the two-dimensional Cartesian space so that distances measured on the spherical surface remain relatively consistent with distances measured in the two-dimensional Cartesian space. Further, this capability allows for the use of efficient search algorithms to find projected geographic points within a particular geographic search area.

Claims

1. A computer-implemented method for projecting geographic data from a spherical surface to a two-dimensional Cartesian space, comprising:

projecting the geographic data from the spherical surface onto faces of a three-dimensional polyhedron;

arranging the faces of the three-dimensional polyhedron within the two-dimensional Cartesian space according to a cutout pattern corresponding to a shape of the three-dimensional polyhedron, wherein geographic data points associated with the spherical surface are mapped to a first set of Cartesian coordinates associated with the arranged faces within two-dimensional Cartesian space; and

mapping one or more data points in the geographic data points to a second set of Cartesian coordinates outside of the cutout pattern and within the two-dimensional Cartesian space based on the arranging so that relative distances among the geographic data points remain consistent between the spherical surface and the two-dimensional Cartesian space.

2. The method of claim 1, wherein at least one face in the arranged faces has folding symmetry across each dimension of the two-dimensional Cartesian space.

3. The method of claim 1, wherein the three-dimensional polyhedron is a cube and the cutout pattern is a cube cutout pattern.

4. The method of claim 1, further comprising:

performing a search for a specific geographic data point associated with the spherical surface using the first and second sets of Cartesian coordinates within the two-dimensional Cartesian space.

5. The method of claim 4, wherein the specific geographic data point is within a bounded geographic search area including a first area within the cutout pattern and a second area outside the cutout pattern.

6. The method of claim 5, wherein the performing further comprises:

adjusting a size of the bounded geographic search area in order to minimize density errors associated with the corner of the face so that the relative distances among the geographic data points within the bounded geographic search area remain consistent between the spherical surface and the two-dimensional Cartesian space.

7. The method of claim 1, wherein the mapping comprises:

identifying a first face and a second face in the arranged faces based on the cutout pattern, wherein a first edge of the first face adjoins a second edge of the second face on the three-dimensional polyhedron but not within the two-dimensional Cartesian space;

transforming a first section of the identified first face to a first location in the two-dimensional Cartesian space;

transforming a second section of the identified second face to a second location in the two-dimensional Cartesian space so that the first edge of the first face adjoins the second edge of the second face within the two-dimensional Cartesian space, wherein the second set of Cartesian coordinates is associated with the transformed first and second sections of the respective first and second faces within the two-dimensional Cartesian space; and

mapping the one or more data points from the arranged faces to the second set of Cartesian coordinates associated with the transformed first and second sections of the respective first and second faces, wherein the one or more data points are mapped to the first set of Cartesian coordinates and the second set of Cartesian coordinates.

8. The method of claim 7, wherein the transforming further comprises:

applying a first transformation to the first section of the first face based on a first face-dependent rotation associated with the first face; and

applying a second transformation to the second section of the second face based on a second face-dependent rotation associated with the second face.

9. The method of claim 8, wherein the applying the first and second transformations comprises:

determining a quadrant of the two-dimensional Cartesian space for each data point in the one or more data points corresponding to the first and second sections of the respective first and second faces; and

rotating and transposing the first and second sections within the determined quadrant based on the respective first and second face-dependent rotations associated with the respective first and second faces.

10. The method of claim 9, wherein the first and second face-dependent rotations are determined based on the projected geographic data associated with each of the respective first and second faces.

11. The method of claim 10, wherein the first and second face-dependent rotations are each multiples of 90 degrees.

12. The method of claim 11, wherein the first face-dependent rotation is 90 degrees in a first direction and the second face-dependent rotation is 90 degrees in a second direction opposite to the first direction.

13. The method of claim 11, wherein the first face-dependent rotation is 180 degrees in a first direction and the second face-dependent rotation is 180 degrees in a second direction opposite to the first direction.

14. The method of claim 1, wherein several of the geographic data points mapped to the first set of Cartesian coordinates are not mapped to the second set of Cartesian coordinates outside of the cutout pattern.

15. A computer-implemented method to transform geographic data from a spherical surface to Cartesian space, comprising:

projecting geographic coordinates associated with the spherical surface onto a cube cutout shape centered on the two-dimensional Cartesian space, the cube cutout shape comprising a plurality of faces that form a virtual cube when folded, wherein the cube cutout shape has folding symmetry across each dimension in the two-dimensional Cartesian space, and wherein the geographic coordinates associated with the spherical surface are mapped to a first set of Cartesian coordinates associated with the cube cutout shape;

transforming sections of faces in the plurality of faces from the cube cutout shape to locations within the two-dimensional Cartesian space so that sides of the faces that adjoin on the virtual cube also adjoin within the two-dimensional Cartesian space; and

mapping geographic data points associated with the sections of faces in the plurality of faces to a second set of Cartesian coordinates outside of the cube cutout shape and within the two-dimensional Cartesian space based on the transforming, wherein the geographic data points associated with the transformed sections are mapped to the first and second sets of Cartesian coordinates, and relative distances among the geographic data points remain consistent between the spherical surface and the two-dimensional Cartesian space.

16. A system for projecting geographic data from a spherical surface to a two-dimensional Cartesian space, comprising:

data projector to project the geographic data from the spherical surface onto faces of a three-dimensional polyhedron, to arrange the faces of the three-dimensional polyhedron within the two-dimensional Cartesian space according to a cutout pattern corresponding to a shape of the three-dimensional polyhedron, wherein geographic data points associated with the spherical surface are mapped to a first set of Cartesian coordinates associated with the arranged faces within two-dimensional Cartesian space; and

a tab mapping unit to map one or more data points in the geographic data points to a second set of Cartesian coordinates outside of the cutout pattern and within the two-dimensional Cartesian space based on the arranging so that relative distances among the geographic data points remain consistent between the spherical surface and the two-dimensional Cartesian space.

17. The system of claim 16, wherein at least one face in the arranged faces has folding symmetry across each dimension of the two-dimensional Cartesian space.

18. The system of claim 16, wherein the three-dimensional polyhedron is a cube and the cutout pattern is a cube cutout pattern.

19. The system of claim 16, further comprising:

a boundary generator to perform a search for a specific geographic data point associated with the spherical surface using the first and second sets of Cartesian coordinates within the two-dimensional Cartesian space.

20. The system of claim 19, wherein the specific geographic data point is within a bounded geographic search area including a first area within the cutout pattern and a second area outside the cutout pattern.

21. The system of claim 20, further comprising:

a density correction unit to adjust a size of the bounded geographic search area in order to minimize density errors associated with the corner of the face so that the relative distances among the geographic data points within the bounded geographic search area remain consistent between the spherical surface and the two-dimensional Cartesian space.

22. The system of claim 16, wherein the tab mapping unit is configured to:

identify a first face and a second face in the arranged faces based on the cutout pattern, wherein a first edge of the first face adjoins a second edge of the second face on the three-dimensional polyhedron but not within the two-dimensional Cartesian space,

transform a first section of the identified first face to a first location in the two-dimensional Cartesian space,

transform a second section of the identified second face to a second location in the two-dimensional Cartesian space so that the first edge of the first face adjoins the second edge of the second face within the two-dimensional Cartesian space, wherein the second set of Cartesian coordinates is associated with the transformed first and second sections of the respective first and second faces within the two-dimensional Cartesian space, and

map the one or more data points from the arranged faces to the second set of Cartesian coordinates associated with the transformed first and second sections of the respective first and second faces, wherein the one or more data points are mapped to the first set of Cartesian coordinates and the second set of Cartesian coordinates.

23. The system of claim 22, wherein the tab mapping unit is further configured to:

apply a first transformation to the first section of the first face based on a first face-dependent rotation associated with the first face, and

apply a second transformation to the second section of the second face based on a second face-dependent rotation associated with the second face.

24. The system of claim 23, wherein the tab mapping unit is configured to:

determine a quadrant of the two-dimensional Cartesian space for each data point in the one or more data points corresponding to the first and second sections of the respective first and second faces, and

rotate and transpose the first and second sections within the determined quadrant based on the respective first and second face-dependent rotations associated with the respective first and second faces.

25. The system of claim 24, wherein the first and second face-dependent rotations are determined based on the projected geographic data associated with each of the respective first and second faces.

26. The system of claim 25, wherein the first and second face-dependent rotations are each multiples of 90 degrees.

27. The system of claim 26, wherein the first face-dependent rotation is 90 degrees in a first direction and the second face-dependent rotation is 90 degrees in a second direction opposite to the first direction.