Processing and storage of spatial data

• US 9,411,898 B1
• Filed: 09/17/2014
• Issued: 08/09/2016
• Est. Priority Date: 01/17/2012
• Status: Active Grant

• Current Assignee: Moonshadow Mobile, Inc.
• Original Assignee: Moonshadow Mobile, Inc.
• Inventors: Ward, Roy W.
• Primary Examiner(s): Cheema, Azam
• Application Number:
  US14/489,430
• Time in Patent Office: 692 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries

Abstract

Generating and storing, for a multitude of polygonal areas, spatial coordinates of a multitude of piecewise-linear spatial boundary segments. The polygonal boundary of each area comprises boundary segments; each boundary segment forms a portion of the polygonal boundary of at most two adjacent spatial areas. Can further include one or both of (i) an indicator, for each spatial boundary segment, of the at most two corresponding adjacent spatial areas that are separated by that boundary segment or (ii) an indicator, for each spatial area, of one or more boundary segments that together form the entire polygonal boundary of that spatial area. The electronic indicia of the second dataset can be used, inter alia, (i) to determine in which of a multitude of at least partly contiguous spatial areas is located a given spatial point, or (ii) to graphically render the polygonal borders of the areas.

Claims

1. A computer-implemented method comprising:

(a) reading or receiving from a first computer-readable storage medium electronic indicia of a first dataset, said first dataset comprising, for each one of a multitude of at least partly contiguous spatial areas, a corresponding set of spatial coordinates of a closed, polygonal boundary of that spatial area;

(b) using one or more computer processors programmed therefor and operatively coupled to the storage medium, generating electronic indicia of a second dataset, said second dataset comprising, for each one of a multitude of piecewise-linear spatial boundary segments, a corresponding set of spatial coordinates of that spatial boundary segment; and

(c) storing the electronic indicia of the second dataset on a second computer-readable storage medium operatively coupled to the processor,

wherein;

(d) the polygonal boundary of each spatial area comprises one or more corresponding boundary segments;

(e) each boundary segment forms a portion of the closed, polygonal boundary of at most two adjacent spatial areas and separates those spatial areas; and

(f) space on the second storage medium occupied by the electronic indicia of the second dataset is less than space on the first storage medium occupied by the electronic indicia of the first dataset.

2. The method of claim 1 wherein the second dataset further comprises one or both of (i) an indicator, for each spatial boundary segment, of the at most two corresponding adjacent spatial areas that are separated by that boundary segment or (ii) an indicator, for each spatial area, of one or more boundary segments that together form the entire polygonal boundary of that spatial area.

3. The method of claim 2 wherein the second dataset comprises, for each spatial boundary segment, an indicator of the at most two corresponding adjacent spatial areas that are separated by that boundary segment.

4. The method of claim 2 wherein the second dataset comprises, for each spatial area, an indicator of one or more boundary segments that together form the entire polygonal boundary of that spatial area.

5. The method of claim 1 wherein the set of spatial coordinates of each polygonal boundary or each boundary segment comprises spatial coordinates for each vertex of that boundary or segment.

6. The method of claim 1 wherein the set of spatial coordinates of each polygonal boundary or each boundary segment comprises spatial coordinates for a first vertex of that boundary or segment and offset coordinates for other vertices of that boundary or segment.

7. The method of claim 6 wherein the offset coordinates of each vertex are relative to an immediately adjacent vertex of the corresponding boundary or segment.

8. The method of claim 6 wherein the offset coordinates of each vertex are relative to the first vertex of the corresponding boundary or segment.

9. The method of claim 6 wherein the offset coordinates comprise rectilinear offsets.

10. The method of claim 6 wherein the offset coordinates comprise a distance and direction.

11. The method of claim 1 wherein the areas are geographical areas and the spatial coordinates are geographical coordinates.

12. A computer system comprising one or more processors and one or more computer memories structured and connected to perform the method of claim 1.

13. An article comprising a tangible, non-transitory medium encoding computer-readable instructions that, when applied to a computer system, instruct the computer system to perform the method of claim 1.

14. An article comprising a tangible, non-transitory computer-readable medium encoded to store the electronic indicia of the second dataset generated and stored by the method of claim 1.

15. The method of claim 1 wherein space on the first storage medium occupied by the electronic indicia of the first dataset is about twice as large as space on the second storage medium occupied by the electronic indicia of the second dataset.

16. The method of claim 1 wherein the first and second storage media are the same storage medium.

17. A computer-implemented method for graphically rendering polygonal borders of a multitude of at least partly contiguous spatial areas, the method comprising:

(a) reading or receiving from a computer-readable storage medium electronic indicia of a first dataset, said first dataset comprising, for each one of a multitude of piecewise-linear spatial boundary segments, a corresponding set of spatial coordinates of that spatial boundary segment, wherein (i) a closed, polygonal boundary of each spatial area comprises one or more of the boundary segments and (ii) each boundary segment forms a portion of the polygonal boundary of at most two adjacent spatial areas and separates those spatial areas; and

(b) using one or more computer processors programmed therefor and operatively coupled to the storage medium and to a display device, and using the first dataset, graphically rendering on the display device each of the boundary segments, thereby graphically rendering on the display device the multitude of spatial areas,

(c) wherein the multitude of spatial areas is rendered on the display device in less time than would be required to render the multitude of spatial areas on the display device, using the one or more processors, using a second dataset comprising spatial coordinates of the closed, polygonal boundaries of the multitude of spatial areas.

18. The method of claim 17 wherein the areas are geographical areas and the spatial coordinates are geographical coordinates.

19. The method of claim 18 further comprising overlaying the rendered boundary segments on a map, chart, or globe.

20. A computer system comprising one or more processors and one or more computer memories structured and connected to perform the method of claim 17.

21. An article comprising a tangible, non-transitory medium encoding computer-readable instructions that, when applied to a computer system, instruct the computer system to perform the method of any one of claim 17.

22. The method of claim 17 wherein the multitude of spatial areas is rendered on the display device in about half the time that would be required to render the multitude of spatial areas on the display device, using the one or more processors, using a second dataset comprising spatial coordinates of the closed, polygonal boundaries of the multitude of spatial areas.

23. The method of claim 17 wherein each of the boundary segments is rendered only a single time in the course of rendering the multitude of spatial areas.