System and method for storing and retrieving geospatial data

• US 8,650,220 B2
• Filed: 06/21/2012
• Issued: 02/11/2014
• Est. Priority Date: 06/05/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Rohlf, John H., Hancher, Matthew Dexter
• Primary Examiner(s): Chen, Susan
• Application Number:
  US13/529,433
• Publication Number:
  US 20130325903A1
• Time in Patent Office: 600 Days
• Field of Search: 707/755, 702/5, 715/201, 379/201.04, 345/419, 342/179, 342/357.04
• US Class Current: 707/797
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/83 Querying
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: G06T 17/05 Geographic models

Abstract

Systems and methods for storing and retrieving geospatial data in a geographic information system are provided. Geospatial data can be spatially partitioned along axes of a spherical coordinate system associated with a virtual globe or other spheroid into a plurality of discrete geospatial volumes pursuant to a hierarchical spatial partitioning scheme. For instance, geospatial data can be spatially partitioned into geospatial volumes along surfaces of constant latitude, longitude, and altitude defined by the spherical coordinate system. The discrete geospatial volumes can be stored as nodes in a hierarchical tree data structure. Additional methods are provided for portioning geospatial objects, such as tiles or discrete geospatial volumes, in tritree to reduce polar distortions.

Claims

1. A computer-implemented method of displaying a three-dimensional representation of a geographic location in a geographic information system for a spheroid, comprising:

receiving a request for a view of the three-dimensional representation to be displayed in a user interface of a display device; and

traversing a hierarchical tree data structure stored in a memory to identify drawable payload data within the view of the three-dimensional representation to be displayed in the user interface, the hierarchical tree data structure comprising an octree data structure having a plurality of nodes, the plurality of nodes comprising;

a first node having a payload comprising first geospatial data corresponding to a first geospatial volume, the first geospatial volume defined by surfaces of constant latitude, longitude, and altitude along axes in a spherical coordinate system defined relative to the spheroid; and

a second node having a payload comprising second geospatial data corresponding to a second geospatial volume, the second node being a child node of the first node in the hierarchical tree data structure, the second geospatial volume being a sub-volume of the first geospatial volume, the sub-volume obtained by spatially partitioning the first geospatial volume according to a hierarchical spatial partitioning scheme along surfaces of constant latitude, longitude, and altitude along axes in the spherical coordinate system defined relative to the spheroid;

wherein the hierarchical spatial partitioning scheme recursively partitions geospatial data associated with the spheroid along surfaces of constant latitude, longitude, and altitude along axes in the spherical coordinate system defined relative to the spheroid.

2. The computer-implemented method of claim 1, wherein the method comprises rendering the identified drawable payload data in the user interface of the display device.

3. The computer-implemented method of claim 1, wherein the method comprises determining a view specification for the three-dimensional representation to be displayed in the user interface of the display device.

4. The computer-implemented method of claim 3, wherein the payload of each node comprises data indicative of a bounding sphere associated with the node.

5. The computer-implemented method of claim 4, wherein traversing the hierarchical tree data structure to identify drawable data comprises comparing the view specification to the bounding sphere of one or more nodes in the hierarchical tree data structure.

6. The computer-implemented method of claim 3, wherein the payload of each node comprises data indicative of a bounding box associated with the node, the bounding box defined in Cartesian coordinates defined by a local coordinate system associated with the node.

7. The computer-implemented method of claim 6, wherein traversing the hierarchical tree data structure comprises comparing the view specification to the bounding box of one or more nodes in the hierarchical tree data structure.

8. The computer-implemented method of claim 1, wherein traversing the hierarchical tree data structure to identify drawable data comprises:

determining the availability drawable data associated with a payload of a node in the memory; and

providing a request via a network interface for any unavailable drawable data identified while traversing the hierarchical tree data structure.