Global tiling grid approximating equal-area while maintaining a simple latitude/longitude aligned rectangular tile layout (not quite a DGGS)

[jerstlouis]

Based on recommendations from Testbed 13 Vector Tiles ER ( http://docs.opengeospatial.org/per/17-041.pdf ):

A global tiling grid combining the advantages of approximating equal-area while maintaining the simplicity of a rectangular tile layout (sort of a half-way compromise between a DGGS and a classic rectangular tile layout). http://ogc.standardstracker.org/show_request.cgi?id=520 http://ogc.standardstracker.org/show_request.cgi?id=518 (TileMatrixSet flexibility)

[perrypeterson]

I support the need for vector tiling. However, there would be no particular reason a DGGS cannot be optimized for visualization purposes and used as a vector tile. We do this presently using a patented process we call a geopacket - https://patents.google.com/patent/US9600538 - which encodes both the vectors and the data as summaries in progressively coarser resolutions of a DGGS.

I believe the scheme that is suggested by Jerome could also be implemented on a DGGS without any loss in functionality. I think HEALPiX DGGS is both quadtree and rectilinear. We use rhombus tiles on the ISEA hexagonal DGGS for visualization, too, though the indexing is UV coordinates not quadtree.

An important note about using quadtree indices as coordinates (I am not saying this is what is being done in Gnosis). The quadtree index itself should not be used to represent the vector geometry itself - ie the endpoint of a line should not be located using the quadtree index. The quadtree indexing and the coordinates that reference the vectors are both needed to reassemble the vector. However, in some DGGS, the index is also a coordinate at which each additional digit the value converges monotonically. With a quadtree you can diverge further from the Real value with a successive subdivision. Illustrated here: https://drive.google.com/file/d/0B2VWzPFQMd9uSy0wV2Uza3FMbWM/view?usp=sharing

[jerstlouis]

Perry, the GNOSIS Global Grid is a quad-tree (subdividing in equal portions of latitudes and longitudes) except for tiles touching the poles which subdivide only in 3 (the portions touching the pole always remains a single tile, so that in effect you always have 4 tiles at the poles).

I also encourage whichever vector tiles extensions that are settled on to support DGGS, all that is required is a cell identifier which is much akin to a tile identifier. As I pointed out in the ad-hoc discussions, the current tile matrix definitions work with 3 parameters (level, row, column) so it would be easiest for DGGS that can describe a cell in this way. Though certainly just like we may need other identifiers for additional dimensions, additional parameters could be used for DGGS requiring more than 3 identifiers.

I am curious about the HEALPiX DGGS being rectilinear and quadtree? Doesn't that prevent from achieving equal area (because you can't tessellate a sphere with squares, plus you'd have to keep the squares aligned)? If I recall our previous conversations the fact that our grid does not have cells of equal area on the ground disqualifies it as a DGGS, right?

I'm not sure I fully understand your considerations locating with the quadtree index? From looking at the video it seems to be about the 'center' of the quad which can be further away from a vector element within the tile at different zoom levels? We would consider the entire extent of the tile when locating features, not only its center. That sure is a neat trick that your hexagons seem to pull off there!

[perrypeterson]

Thank you for your explanation. Yes, DGGS must be equal area cells. HEALPiX preserves area in a rectilinear cell. There are other ways to perform this - the rhombus DGGS sometimes called a diamond DGGS achieve the same.

Sorry for my poor explanation of the pitfalls of storing vectors geometries using quadtree ordinates. The essence of the problem is that the points can move away from the "Real" location instead of move closer at refinements/higher resolutions. A line for example will move around and away from the actual location as you zoom in (does not converge monitonically) like coordinates do with each additional digit/decimal place. I can show you sometime when we are together.

[rggibb]

My apologies I've just joined the conversation which is really interesting .. There are indeed a number of potential geometries for achieving rectlinear tesselations that may be used to as the basis of equal area tiles on the surface of ellipsoids (or spheroids).

1. The original HEALPix - Heirarchical Equal Area isoLatitudinal Pixelation - as used by the astronomical community is technically a rhombus tiling. The illustration on the HEALPix webpage above shows with four rhombii sharing a common node at each pole and four equatorial rhombii which is an initial global tesselation of 3rows x 4columns of rhombii. The illustration also shows the subsequent three rhombic quadtree tesselations.
2. The rHEALPix tesselation differs in two ways. These are illustrated in fig 14a of OGC AS Topic 21 DGGS. The first difference is that It uses a cubic arrangement of rectilinear cells that are isolatitudinally aligned, with 1x cell centered at each pole and 4x cells along the equator. Secondly it uses a 3x3 tesselation of each face for the subsequent tesselations. rHEALPix uses a 3x3 Morton (or Z-curve) for cell indexes which makes it simple to compute lat long from the cell-id.
3. The Quadrilateralised Spherical Cube trades isolatitudanal cells in favour of geometric similarity between all the cells and pure use of great circles. To create a DGGS tiling scheme from this initial spherical tesselation a 2x2 or 3x3 recursive tesselation of each face could be used.

Any of these could be used for global vector tiling schemes, and at the simplest implementation each tile could be used to store whatever vector format you care for .. shape, geopackage etc without further alteration of their formats or even normalisation of their native projection. However obviously depending on implementation progressively more benefits are derived from enforcing particular subsets of file types. OGC AS Topic 21 DGGS anticipates variants of these formats where the traditional coordinate pairs are replaced by cell-ids at appropriate resolution for the precision of the data, thus providing a fully self symmetric solution. The use of DGGS cells for tiles and/or coordinate geometry is covered in the standard in the section on quantisation.

The pitfall described by Perry of using quadtrees for vector geometry, is (I believe) avoided by any tesselation scheme that produces a child cell at the centre of its parent cell. So the 3x3 tesselation in the rHEALpix description above is one example. If you want to use a 2x2 tesselation, the child cells can be offset so that one is centered on its parent and the surrounding ones therefore overlap the parents boundary rather than being perfectly nested. 3x3 is the smallest number that perfectly nests and is child centric.

[jerstlouis]

Thanks for the input Robert. As I mentioned in the Vector Tiles ad-hoc and was saying in the earlier comment, I strongly support the idea of being able to use a DGGS as the 'tiling scheme'. I think this comes down to the consideration that it should be possible to use something other than a 'TileMatrixSet' to define a tiling scheme (what we are currently considering as the basis for tiles, mainly because it is already widely used in WMTS).

I don't think the services or tiling standard should enforce any particular file types either, it really isn't the purpose to throw in limitations at this level (though encouraging support for commonly used formats or formats with certain clear advantages would be a good thing).

However to get back to the purpose of this 'idea' itself, it is not about a DGGS so I would suggest opening a separate idea to continue DGGS / vector tiles related discussions.

I realize I should edit the title as this grid only 'approximates' equal area. The GNOSIS global grid may not be of much interest to the DGGS community. But I will argue it does have its own very practical advantages. If you're interested to learn more about this grid, some additional explanations, graphics and sample implementation source code are found in the Testbed 13 Vector Tiles ER, Appendix A:

http://docs.opengeospatial.org/per/17-041.pdf#page=118

[perrypeterson]

Yes @rggibb you are correct re centroid child.

[jerstlouis]

The GNOSIS Global Grid, and other variable-width tile matrix sets (e.g. the CDB Global Grid), can now be described by the Tile Matrix Set standard 1.0:

http://docs.opengeospatial.org/is/17-083r2/17-083r2.html#14 http://schemas.opengis.net/tms/1.0/json/examples/GNOSISGlobalGrid.json

[jerstlouis]

An open question is to what extent Variable Width Tile Matrices, attempting to approximate equal area (such as the CDB Global Grid and the GNOSIS Global Grid), qualify as DGGS per Topic 21 - Part 4: Axis-Aligned? And do they qualify in any way for Part 1, if they only approximate or tend towards Equal Area?

[rggibb]

@jerstlouis Part 4 - Axis Aligned will not have any equal area constraint. Broadly Pt4 will require that all cell edges are parallel with the axes of the underlying CRS. For such a geometry to also be a DGGS there are a bunch of additional requirements that aren't just about cell geometry. Pt 1 describes a set of core DGGS requirements that are common to DGGS following any of the Pts 1-4, and it also adds requirements for Equal Area Earth DGGS. Similarly Axis Aligned DGGS will need to be compliant with the core in Pt 1 and the new requirements for Axis Aligned that are currently being drafted. If you look at the core in Pt 1,you will find requirements that cover multi-resolution cell geometry, cell/zoneids - which in this case tile nomenclature, and also the operations that are performed on zoneids. All these aspects are needed to have a DGGS.. ie the total package as a System as distinct from a single global grid.

[jerstlouis]

@rggibb Thanks for the feedback! From that I gather that it is possible that a system implementing non-variable TileMatrixSets (e.g. WorldCRS84Quad) might actually satisfy the Part 1 Core + Part 4 Axis-Aligned. Many 2DTMS address multi-resolution cell-geometry, and all address the cell/zones IDs as tiles as you pointed out.

Operations themselves are not really covered by the 2DTMS standard, but an implementation would likely support operations such as storage and retrieval per tile/cell ID, mapping vector or raster data to their corresponding tiles/zones, 'cutting' the data to only include the parts within the tile/zone, generalizing the data to be suitable to a tile/zone level.

But what about variable width TileMatrixSets, which go a step further and try to approximate equal areas (by coalescing polar tiles into fewer tiles)? Are there any additional conformance classes in Part 1 that they could conform to?

[perrypeterson]

Jerome,

Excellent discussion. While I may not addressing this latest question directly, I do want to add a general statement that may get at the core of it. While DGGSs seem to easily categorize into any grid/tile/coverage scheme/spatial indexing etc implementation that appears as discrete or gridded models, I have always been cautious. Even the inclusion of Part 4 is problematic and I like that you avoid it. I would always stick to the Goodchild and Kimerling Criterion for a DGGS. Those schemes that "try" to conform to their criteria, while even imperfect, are types of DGGS to me. My interpretation of their intention is to produce a discrete location atom of which all location phenomenon can be represented - Goodchild writes about this often - and this object is a high-level object in a database. A coordinate system is continuous and can not be a high-level object (and we perpetually struggle with this) unless manipulated into a tiling scheme or a vector topology. DGGS is a "digital" (discrete) as opposed to "analog" (Continuous) Earth reference. But it is for and foremost an Earth reference. That location - atom, pixel, tile, cell, raster - its geometry and tesselation - how it refines - must be a discrete repeatable convergent consistent atomic shape for location everywhere at all scales. It must by its purpose allow disparate data to be assigned to it - thus it solves geographic data integration/fusion/merging/combining. Aggregating these location atoms form geometry and summarizing their data attributes characterize the geometry thus DGGS are used to define phenomena. Implementation of the DGGS standard going forward should bear that out. If that is the intent of a tiling design then I think it is a DGGS.

Best regards, Perry

On Wed, Feb 3, 2021 at 3:08 AM Jerome St-Louis notifications@github.com wrote:

@rggibb https://github.com/rggibb Thanks for the feedback! From that I gather that it is possible that a system implementing non-variable TileMatrixSets (e.g. WorldCRS84Quad) might actually satisfy the Part 1 Core

• Partattempt 4 Axis-Aligned. Many 2DTMS address multi-resolution cell-geometry, and all address the cell/zones IDs as tiles as you pointed out.

Operations themselves are not really covered by the 2DTMS standard, but an implementation would likely support operations such as storage and retrieval per tile/cell ID, mapping vector or raster data to their corresponding tiles/zones, 'cutitng' the data to only include the parts within the tile/zone, generalizing the data to be suitable to a tile/zone level.

But what about variable width TileMatrixSets, which go a step further and try to approximate equal areas? Are there any additional conformance classes in Part 1 that they could conform to?

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/opengeospatial/ideas/issues/59#issuecomment-772427029, or unsubscribe https://github.com/notifications/unsubscribe-auth/ADRZK6T73L557MTEDYIWL23S5EVB3ANCNFSM4FDMZ2UA .

[rggibb]

@perrypeterson I absolutely agree with your points for a full DGGS, however a vector tiling schema with DGGS compliant geometry is a hybrid system. It only implements asDataTile quantisation/data import and doesn't attempt to convert it's data to DGGS form.

[perrypeterson]

Thank you, Robert.

I think at this time I want to acknowledge that there should exist fair disagreement especially when we are discussing fundamental relationships and definitions - after all these are conceptual and imaginative. However, generations from now, it will all be a done deal. But to its importance, I am reminded that Mike has written about having a DGGS standard:

“I’m very much in favour of this effort, I’ve argued for something along these lines, I think it’s very relevant to the hypothetical question ’What if we could organize another Meridian Convention, what would have a similar enabling impact?’”

I also appreciate that OGC is an organization dedicated to consensus and that necessitates compromise. In so far as DGGS goes, creating efficient Equal Area Partitioning of the DGGS is technically challenging, it goes against the grain of traditional approaches to spatial analysis, quantizing is distracting to those who hold data, and even with DGGS powerful capabilities demonstrated and acknowledged, adoption is slow. This makes DGGS purity vulnerable to even more compromise such as that spurned on by an axis based grid. Others will happily look only at the term Discrete Global Grid System and insist, "mine, too, it is discrete it is global it is a system, there you have it mine is also a DGGS." Part 4 in my opinion is another way of affirming that we are evangelizing and happy to incorporate local culture if it means we gain a baptism, to use a very insensitive metaphor - my apology. Now we will add the term Equal Area to DGGS which always assumed equal area. What do we let go of next, quantization are you suggesting? A DGGS hybrid system? Compromise is a slippery slope and we may throw the baby out with the water.

I would therefore return to the statement of purpose as another anchor - is the hybrid designed to represent phenomenon through the aggregation of cells and summary statistics on data? When we define by purpose compromise becomes apparent. Conventional coordinates are designed for navigation, if a version fails to return someone to the same location it fails as an implementation. Tiles are designed for efficient transmission and rendering of imagery or geometric constructs, if one fails to deliver imagery at the speed users expect it is a failed implementation. Spatial indexing is designed for partitioning n-space for efficient data retrieval operations, if one fails to return useful values in a timely manner it would be a failed implementation. DGGS are designed to align disparate data sources for spatial analysis, if one is not able to produce analysis-ready data representing spatial phenomena over multiple disparate data sources, it is a failed implementation.

To be clear, I am not proposing a roadblock. I am very happy to trust the process and hope our efforts lead to better decisions and thus a better world.

Sincere regards, Perry

On Wed, Feb 3, 2021 at 11:25 AM Robert Gibb notifications@github.com wrote:

@perrypeterson https://github.com/perrypeterson I absolutely agree with your points for a full DGGS, however a vector tiling schema with DGGS compliant geometry is a hybrid system. It only implements asDataTile quantisation/data import and doesn't attempt to convert it's data to DGGS form.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/opengeospatial/ideas/issues/59#issuecomment-772751895, or unsubscribe https://github.com/notifications/unsubscribe-auth/ADRZK6TUUWLSNTOZI2VZ233S5GOC3ANCNFSM4FDMZ2UA .

[rggibb]

@jerstlouis @perrypeterson The original intent, in my mind, of allowing a system to implement AsDataTile on it's own, was to allow non-DGGS data to be tiled and retained in its original form, with the same tiling schema as a full DGGS. This could be thought of as a staging point prior to full DGGS conversion, where the data could equally be used by a DGGS for import and by traditional systems. If the intent is to use a set of global grids purely for vector tiling and the schema isn't suitable for use in descretising the data for analysis, then I'm not sure what the advantage is of claiming that the tiling system is loosely DGGS compliant - except to score a compliance tick. In other words, if you want an equal area DGGS you wouldn't start with the CDB or GNOSIS Global Grids. However, what you might want to do is to recognise the usefulness of CDB say and the richness of existing applications, and evolve it towards being truly equal area and fully DGGS compliant, so that it is no longer just a tiling schema but is also designed full DGGS data and DGGS processing. Such an evolutionary path could lead to more efficient processing for CDB based applications, and there could be an intermediate evolutionary phase where hybrid vector/DGGS data and processing is supported. If that is perceived as a useful pathway then there may also be advantages in extending 2DTMS to recognise DGGS tiling schema. At this point I'll also note that DGGS tiling schemas are dimension agnostic.. ie the DGGS core inherently supports 2D, 3D, 2D+T & 3D+T data and tiling for vector, raster, point cloud, tag cloud, and map data. So they offer a pathway for 2DTMS to extend beyond its existing scope.

[jerstlouis]

@rggibb @perrypeterson I would like to clarify a couple things: The use of 2DTMS and variable width grids such as the GNOSIS Global Grid and CDB Global Grid are not limited to "vector" tiling -- we tile many thing with it: imagery, coverages (2D, 3D, 4D, nD), vector data (again can contain 3D information), 3D models, point clouds, and they are also not limited to visualization, but also used for data integration analytics and processing, where different tiles can be processed in a distributed/parallel manner, and where you can control the accuracy of the results by using different levels.

Although there is a distortion in the area distribution within a tile and between tiles, that distortion is known and can be accounted for to provide results accurate to a desired precision.

I am not trying to get 2DTMS to tick the DGGS compliance, I am trying to understand based on the Topic 21 definition to what extent they are considered DGGS, because as far as I understand the goals and use cases are exactly the same. For the next update to the CDB standard in particular we are trying to clarify the relationship with Topic 21. If applicable the next revision of 2DTMS as well could highlight any relationship.

The only difference is the approach on where the calculation complexity lies at different steps, and in my opinion this could be an implementation decision of a particular DGGS system (e.g. choosing more equal area hexagons vs. lat/lon-aligned square tiles tending roughly towards equal area).