Close-packed, uniformly adjacent multiresolutional, overlapping spatial data ordering
View Patent ↗A method, apparatus, system and data structure is disclosed for mapping of spatial data to linear indexing for efficient computational storage, retrieval, integration, transmission, visual display, analysis, fusion, and modeling. These inventions are based on space being decomposed into uniform discrete closely packed (hexagonal) cell areas ( 85 ). Each resolution of close-packed cells can be further divided into incongruent but denser clusters of close-packed cells. The spatial indexing ( 86 ) is applied in such a manner as to build a relationship with the spatially close cells of any resolution.
1. A computer-implemented method of storing two-dimensional data in system memory, the method comprising:
a) defining a hierarchical series of tessellations of uniform aperture three hexagonal cells using a processor, each tessellation having a resolution and being stored in the system memory;
b) mapping one or more attributes from a continuous space to the cells of each tessellation;
c) assigning each cell in a lowest resolution tessellation a unique index comprising an identifying value;
d) associating each cell in a given tessellation that is not the lowest resolution with a parent cell contained in the next lower resolution tessellation based on the location of the parent cell relative to a grandparent cell contained in a tessellation of one lower resolution than the parent cell; and
e) assigning each cell not in the lowest resolution tessellation a unique hierarchical index comprising an index of the parent cell associated therewith and an identifying value.
2. The method of claim 1 , wherein the parent cell associated with a particular cell is determined as follows:
a) if a centroid point of the particular cell is located at a centroid point of a lower resolution cell contained in a tessellation of lower resolution than the tessellation containing the particular cell, the parent cell for the particular cell is the lower resolution cell; and
b) if a centroid point of the particular cell is located on a vertex point of one or more lower resolution cells contained in a tessellation of lower resolution from the tessellation containing the particular cell, then the parent cell for the particular cell is a lower resolution cell that has a centroid point which is a centroid point of the grandparent cell.
3. The method of claim 1 , wherein each parent cell is associated with either only one child cell or seven children cells contained in a tessellation of one higher resolution than the tessellation containing the parent cell, the one child cell having a centroid point that is located at the centroid point of the parent cell and the seven children cells having centroid points located at each vertex and the centroid point of the parent cell.
4. The method of claim 3 , wherein the parent cell is associated with the seven children cells when the parent cell has a centroid point which is a centroid point of the grandparent cell.
5. The method of claim 3 , wherein the parent cell is associated with the only child cell when the parent cell has a centroid point which is located at a vertex of the grandparent cell.
6. The method of claim 3 , wherein the identifiers of six of the seven children cells that have a centroid point located at each vertex have a first common characteristic.
7. The method of claim 3 , wherein the identifiers of child cells that have a centroid point located at the centroid point of the parent cell have a second common characteristic.
8. The method of claim 1 , further comprising determining an index of at least one adjacent cell to a given cell in the same resolution based on the identifier of the given cell and an addition table.
9. The method of claim 1 , further comprising laying the cells of each tessellation onto the faces of an icosahedron and projecting the data from the faces of the icosahedron to a geodesic spheroid.
10. The method of claim 9 , wherein a shape, orientation, and projection of the series of hierarchical tessellations conforms to the Icosahedron Snyder Equal Area Aperture 3 Hexagon Grid and the method further comprises:
dividing the icosahedron surface by introducing one point on each icosahedron vertex, resulting in pentagonal shaped Voronoi regions with shared cell vertices centered on each face of the icosahedron, and then defining a second generation hexagonal cell at each of the shared cell vertices and a second generation pentagonal cell at each icosahedron vertex.
11. A grid system comprising:
a) a processing unit;
a system memory storing a hierarchical series of tessellations of uniform aperture three hexagonal cells, each tessellation having a resolution and each cell having a unique index, each cell in a given tessellation that is not the lowest resolution being associated with a parent cell contained in the next lower resolution tessellation based on the location of the parent cell relative to a grandparent cell contained in a tessellation of one lower resolution than the parent cell; and
b) a system bus operatively coupling the system memory to the processing unit,
wherein,
for each cell in a lowest resolution tessellation, the unique index comprises an identifying value,
for each cell that is not in the lowest resolution tessellation, the unique index comprises an index of the parent cell associated therewith and an identifying value.
12. The system of claim 11 , wherein the parent cell associated with a particular cell is determined as follows:
a) if a centroid point of the particular cell is located at a centroid point of a lower resolution cell contained in a tessellation of lower resolution than the tessellation containing the particular cell, the parent cell for the particular cell is the lower resolution cell; and
b) if a centroid point of the particular cell is located on a vertex point of one or more lower resolution cells contained in a tessellation of lower resolution from the tessellation containing the particular cell, then the parent cell for the particular cell is a lower resolution cell that has a centroid point which is a centroid point of the grandparent cell.
13. The system of claim 11 , wherein each parent cell is associated with either only one child cell or seven children cells contained in a tessellation of one higher resolution than the tessellation containing the parent cell, the one child cell having a centroid point that is located at the centroid point of the parent cell and the seven children cells having centroid points located at each vertex and the centroid point of the parent cell.
14. The system of claim 13 , wherein the parent cell is associated with the seven children cells when the parent cell has a centroid point which is a centroid point of the grandparent cell.
15. The system of claim 13 , wherein the parent cell is associated with the only child cell when the parent cell has a centroid point which is located at a vertex of the grandparent cell.
16. The system of claim 13 , wherein the identifiers of six of the seven children cells that have a centroid point located at each vertex have a first common characteristic.
17. The system of claim 13 , wherein the identifiers of child cells that have a centroid point located at the centroid point of the parent cell have a second common characteristic.
18. The system of claim 13 , wherein an index of at least one adjacent cell to a given cell in the same resolution is determined based on the identifier of the given cell and an addition table.
19. The system of claim 13 , wherein the cells of each tessellation are laid onto the faces of an icosahedron and the data from the faces of the icosahedron is projected to a geodesic spheroid.
20. The system of claim 13 , wherein a shape, orientation, and projection of the series of hierarchical tessellations conforms to the Icosahedron Snyder Equal Area Aperture 3 Hexagon Grid and the icosahedron surface is divided by:
introducing one point on each icosahedron vertex, resulting in pentagonal shaped Voronoi regions with shared cell vertices centered on each face of the icosahedron, and
defining a second generation hexagonal cell at each of the shared cell vertices and a second generation pentagonal cell at each icosahedron vertex.