How PYXIS Works
Fundamental perspective #1 - Physical space and time exist.
Human interaction fundamentally depends on the reference frames of time and space. We perceive these interactions through sensor perception and work through their meaning with responsive, cognitive, and subconscious/intuitive processes within our neural intelligence systems.
The concepts of cybernetics, which one part is the digital computer, lead humanity towards a collective increase of intelligence by extending these capabilities.
Models of physical time and space are metaphysical. Euclidean precepts of physical space define a mathematical metaphysics on a lattice continuum that, through analytical geometry and algebra, can elegantly recreate many aspects of reality.
However most, perhaps debatably all, aspects of the physical are not continuous but discrete. Hence, it is reasonable that a model of reality as is accomplished within a physical computing machine is much more capable using discrete mathematical concepts than physical models built on a lattice or continuum of points.
There are many examples where computer science has selected and implemented solutions on principles of discrete mathematics for this very reason: modeling varieties of information to common pixels from a graphics card to a display device is a good example.
However, computer science has generally not implemented concepts of discrete mathematics within Geographic Information Systems – ironically the computer science responsible for modeling one of the basic frames we depend on: physical space. Instead, traditional lattice mathematical models of spherical coordinates or projections to Cartesian coordinates have been adopted for encoding spatial data within computing devices. As these systems define points and not discrete pieces we term them Analog Earth Reference Models.
It is the object of PYXIS to define and optimize a discrete partioned model of physical space with a particular implementation focused on geographic reference.
We refer to the results as a Digital Earth Reference Model as it encompasses principals of a digital model namely:
- A discrete uniform partitioning (a tessellation or tiling of cells over the Earth surface);
- A unique linear non floating point index for each discrete cell that encompasses within the index both a parent child hierarchical relationship and a coordinate system that converges to the set of all real numbers;
- A set of mathematical relationships built on the index: algebra, geometry, Boolean operations, image processing, etc; and
- A strategy for quantizing values, preferable integers, to each discrete cell.
Before we scare you off by the vision of a whole new Earth Reference System, you are assured that the optimal solution is of no negative consequence to legacy data, systems or approaches but a powerful enabler of these.
Fundamental perspective #2 – The ISEA3H can be used to model a discrete uniform partitioning of physical space.
The Icosahedral Snyder Equal Area Aperture 3 Hexagonal Grid (ISEA3H) is a method that can partition all space. This is accomplished by projecting a square root three mesh (regular hexagonal tessellation) from an icosahedron to a sphere using a reverse Lambert Equal Area Conformal technique developed by John Snyder1, 1993. The result is infinite irregular but equal volume hexagonal prisms extending from the icosahedral centre. A sphere of any radius will cut through the prisms to form equal area cells.
The process of partitioning a sphere in this manner includes the creation of 12 pentagonal cells at the vertices of the icosahedron 5/6 the spherical cross section of the hexagonal cells. To form an Earth centric reference, it has been recommended that the model be positioned at the centre of a sphere with the vertices arranged to align with minimized effects of the resulting 12 pentagonal artifacts, Kevin Sahr2, et. al. 1998, 2003.
The model used beyond an Earth reference is time dependant, ie the fixed to Earth reference moves as the Earth moves.
The Snyder method, while preserving area, minimizes distortion in the cells through a loss of equal angles (distance). This distortion is maximized, scale dependent (i.e. it exists at every resolution in the same form) and concentrated along a great circle arc from the center of each icosahedron face to the icosahedron vertices as illustrated. The resulting cell edges are not strictly linear as any discrete point along a cell edge will project to the distortion.
Criteria for design of an optimal global grid. Jon Kimerling and Michael Goodchild have prepared several papers on the subject summarized here:
1. John P. Snyder, defines a method for preserving cell equal area and minimizes distortion of cells through loss of equal angles (distance) as recommended by Kimerling and Goodchild. "An Equal-Area Map Projection For Polyhedral Globes", Cartographica, Vol. 29, No. 1, 1992
2. Selection of a square root three subdivision of icosahedron surface (forming multiple resolution hexagonal cells) to form the mesh on the Snyder polyhedral. A recent summative paper by Sahr, White and Kimerling in 2003: Geodesic Discrete Global Grid System
Fundamental Perspective #3 – the PYXIS innovation provides a unique index for each cell within a Square Root Three subdivision.
The basic unit of PYXIS space is a PYXIS Cell. A unique naming convention of each cell is required.
The square root three tiling can be considered as a series of ever finer or coarser tessellations of hexagonal PYXIS Cells on an infinite plane. At any particular tessellation the relationship of a cell to the cells of the next finer resolution can be expressed linearly as an index relating a parent cell to a child cell.
Hexagons can not be divided into congruent smaller hexagons nor aggregated to form larger hexagons as is a common characteristic used for indexing similar tessellations of square and triangular tiles – a.k.a. quad-trees. However, two types of child cells can be identified in the square root three subdivision that assist in building a unique index. A child cell that shares the centroid of the parent cell Centroid Child and a child cell whose centroid is located at the vertex of a parent cell Vertex Child.
A centroid child is simply indexed by including a zero placeholder to the right digit of the parent index. A parent 010020 spawns a centroid child 0100200 or a parent 030204 spawns a centroid child 0302040.
This step does not complete the indexing for tiling of the finer tessellation. There remains indexing of finer hexagonal cells located at each of the vertices of the parent cells [Vertex Child]. However, the vertices within a hexagonal grid are each shared by three cells and so, adopting a parentage when there are 3 potential parents sharing the same centroid cell, presents a dilemma. The core contribution of the PYXIS innovation indexing is the recognition that of the three potential parents, only one of the three was itself a centroid child of the next coarser tessellation. In other words, only parent cells that were themselves centroid children are permitted to spawn vertex children [Vertex Parent]. This is the PYXIS innovation.
A vertex child is simply indexed by including a direction digit (1 to 6) to the right of the parent index. A parent 010020 spawns six new vertex children 0100201, 0100202, 0100203, 0100204, 0100205 and 0100206. Note parent 030204 is a vertex child cell (the last digit is not 0 but a 4 indicating it as a vertex cell) and therefore does not spawn new vertex cells.
An efficient trie structure is formed
Within the result is a unique index for each cell [PYXIS Index] - as an example 02003010040 – that embeds a series of digit directions and implied magnitudes (modulus by square root three) that converge to all real numbers by square root three divisions. Λ<-0200301004->Ω
Fundamental Perspective #4 – the implied relationship within PYXIS indices
The PYXIS Tile
A PYXIS TILE is a basic implied relationship wherein all the cells contained in the hierarchy at a given resolution below the root PYXIS Depth of a specified PYXIS Index is known. As a tile of cells can never be congruent with the parent hexagon cell, two forms exist, one tile generated from a) a vertex parent exhibits cells inside the parent spatial domain and one tile generated from b) a centroid parent exhibits cells inside and outside the parent spatial domain.
These different tiles elegantly fit together to fill space. Further, a group of cells which fall within a vertex parent at one level will fall within a centroid parent on the next resolution and then oscillating back to a vertex parent on the next finer resolution, permitting an averaging of error within a Gaussian distribution.
An Algebraic Relationship within the PYXIS Indices
It is of substantial value to determine the relationship between one cell and its neighbours across the entire plane. Arithmetic functions can be completed over the PYXIS indexing using the following approach.
A unique indexing and algebra was defined by Gibson and Lucas on a similar, but base 7 not 3, hexagonal grid, called Generalized Balanced Ternary. GBT presents hexagons only at the original resolution and aggregates groupings of pseudo-hexagons to form coursed resolutions. “Spatial Data Processing Using Generalized Balanced Ternary”, Proceedings of the IEEE Computer Society Conference on Pattern Recognition and Image Processing, 1982
Another approach to arithmetic operations on PYXIS involves translating the PYXIS hexagonal grid to a regular Cartesian rectangular coordinates, use Cartesian arithmetic operations and then translate the results back to PYXIS indexing. This approach provides conformity with processes already in use on a computer and is therefore faster than the PYXIS addition table approach.
Conversion between Rectangular and Hexagonally referenced space
Mathematically, the PYXIS Innovation is a discrete numbering system based on balanced ternary. In PYXIS, under given precision, the real number set is approached and represented by an integer based indexing system. In two dimensions, PYXIS links to hierarchical close packing geometry, which results in a coordinate system on a multiple resolution hexagonal grid.
As the PYXIS lattices maintain regular hexagonal cells at each resolution, the conversion between Cartesian and PYXIS coordinates is actually the conversion between rectangular and hexagonal coordinates.
An expression for conversion between Cartesian coordinates and the indexing on a PYXIS tile has been developed by Yong Du see An Algebraic Expression for PYXIS innovation. Essentially, the conversion between PYXIS and traditional rectangular coordinates rests on the existence of one point in space and this point is represented by different 2D coordinate systems. When the relation between the different coordinate systems is found, the two systems can be converted between each other. Generally speaking, the relation between two different coordinate systems is unique, which could be represented in different expressions. The algorithms of conversion based on the found relation could be different as well depending on the design of program or procedure.
Fundamental perspective #5 - Reference to the Sphere
The preceding discussions have been in reference to operations on the PYXIS tile. To provide an Earth reference the tiles must be related to an icosahedron and then projected as per the ISEA. To explain how this is accomplished we consider that from each of the 12 vertices of the icosahedron, are connected 5 triangular faces as shown in the steps in this figure.
A PYXIS Tile is referenced by centering it on a vertex with tile vertices on each of these five faces; as such one/sixth section of the tile must be removed to form a pentagonal cap as shown. This can be accomplished algorithmically simply by removing one root of the first resolution vertex children.
Addition over the gap can be dealt with by “rolling” the index to an equivalent gap index and then applying the tabular mathematics as described above. As an example, if adding across from 010203 to 030404 where a gap exists at 02 then rolling counterclockwise (from 01 to 03) change 010203 to 020304 and complete a conventional add. If adding from 040106 to 020103 then rolling clockwise (from 04 to 02) change 040106 to 030605 and complete a conventional add.
The third picture shows that within this arrangement there are succeeding whole PYXIS tiles generated from the vertices of what is now levels of a pentagonal shape – red, blue, yellow then green individual tiles shown – with a single pentagonal cell remaining centered on the icosahedral vertex.
Connecting the twelve pentagonal caps is accomplished by defining a connectivity table between arbitrary labels. Further, as indexing is developed off of each vertex, an overlap occurs at the center of the icosahedron face from the tile generated from the three vertices that make up the triangular face – in the figure this is the red tile. This is dealt with by assigning a fixed index value for each of the 20 faces and defining a cardinal direction for each of these Hexagon Face Tiles. The result is uniform indexing from whatever start point is used. These fixed indices for the 20 faces are added to the 12 icosahedral vertices in the connectivity table.
The entire grid can be laid out on a plane of an unfolded icosahedron as shown in the bottom figure. This provides a direct reference to a Cartesian grid used by the Snyder projection and also a planar reference for PYXIS data for tasks such as generating 2D rendering for texture mapping or simplified display.