Encoding Conversion Algorithm of Quaternary Triangular Mesh

Yihang Chen, Zening Cao, Jinxin Wang, Yan Shi, Zilong QinISPRS Int. J. Geo Inf 2022 · DOI

TL;DR

This paper tackles the challenge of interoperability between different Discrete Global Grid Systems (DGGS), specifically focusing on the Quaternary Triangular Mesh (QTM). The authors propose three novel encoding conversion algorithms – resampling, hierarchical, and row-column – to enable seamless data exchange and integration across various QTM implementations, which is crucial for building a unified "digital earth."

What Problem Does This Paper Address?

The increasing need for global information construction has led to the development of numerous Discrete Global Grid Systems (DGGS) by different organizations and for various purposes. While these systems offer advantages in representing Earth data, their heterogeneity, particularly in encoding rules, creates a significant barrier to data exchange, integration, and interoperability. The Quaternary Triangular Mesh (QTM), a popular DGGS due to its simple structure and suitability for digital earth frameworks, suffers from this problem as well, with multiple encoding schemes hindering communication. This paper aims to bridge this gap by developing methods to convert between these different QTM encodings, thereby facilitating data sharing and enabling associative integration of diverse DGGS.

Methods

The paper introduces three primary encoding conversion algorithms for QTM:

  • Resampling Conversion Algorithm: This method converts an encoding from one QTM system (D(A)) to another (D(B)) by first transforming the encoding into spatial coordinates (latitude and longitude) and then re-encoding these coordinates into the target QTM system. This approach is versatile and can handle conversions between different projections and subdivisions.
  • Hierarchical Conversion Algorithm: This algorithm leverages the inherent hierarchical structure of QTM encodings. It works by iteratively replacing the encoding of a parent cell with the encoding of its children, following specific conversion rules between different encoding types (e.g., Goodchild to LS, Goodchild to modified direction, Goodchild to quaternary). This method is generally faster as it avoids floating-point calculations.
  • Row-Column Conversion Method: This approach is designed for QTM encodings that do not strictly adhere to a hierarchical quadtree structure (like TRQ encoding or arithmetic layer encoding). It uses a "row-column number" as an intermediary. The conversion involves transforming the QTM encoding into a row-column representation and then converting this back to the desired QTM encoding. Two sub-methods are presented for this: the "row and column algorithm" and the "three-orientation translating algorithm."

Datasets

The paper does not explicitly mention the use of specific public datasets for training or evaluation. Instead, it describes experimental setups using "all the triangular grids within a hexagram limit (subdivision level 6–12)" and "the 2015 average annual rainfall grid data of Inner Mongolia from the 9th to 13th levels." These appear to be synthetic or derived datasets for testing the algorithms' performance rather than publicly released benchmarks.

Key Insights and Ideas

  • Directionality as a Complexity Metric: The paper proposes "directional complexity" as a measure of how complex an encoding is. It posits that higher directionality leads to more complex conversion algorithms and a negative correlation between directional complexity and encoding conversion efficiency.
  • Hierarchical vs. Resampling Efficiency: The hierarchical conversion algorithm generally outperforms the resampling algorithm in terms of efficiency, especially for conversions between different encodings within the QTM family. This is attributed to the hierarchical method's reliance on integer conversions, avoiding the computational overhead of floating-point operations.
  • Row-Column Intermediary for Non-Hierarchical Encodings: The row-column conversion method is crucial for handling QTM encodings that lack strict hierarchical properties, demonstrating its broader applicability.
  • Trade-offs in Row-Column Algorithms: The paper highlights that for calculating row-column numbers from QTM encodings, the three-orientation coordinate positioning algorithm is superior. Conversely, for converting row-column numbers back to QTM encodings, the row-column algorithm is more efficient.

Key Results

The paper presents comparative analyses of the efficiency of its proposed algorithms. For instance, in the conversion from Goodchild encoding to LS encoding, the hierarchical conversion algorithm was found to be more efficient than the resampling algorithm, with the former being approximately 1.67 times faster in some cases. The efficiency gains are more pronounced at higher subdivision levels. The paper also shows that the three-orientation translating algorithm is generally more efficient for encoding to row-column conversion, while the row-column algorithm is more efficient for row-column to encoding conversion.

Limitations and Future Work

  • Limited Scope of Hierarchical Conversion: The hierarchical conversion method is limited to encodings that follow a quadtree division structure. It cannot be applied to other types of QTM encodings.
  • Complexity of Row-Column Conversion: While the row-column method addresses non-hierarchical encodings, the conversion process, particularly for calculating column numbers, can be more complicated.
  • Future Work: The authors suggest that the proposed row-column conversion algorithm can also be applied to the conversion between QTM and rhombus grids, indicating a potential for broader applications in grid-based data integration. The paper provides a theoretical and technical foundation for QTM encoding interoperability, paving the way for future research in this area.

Summary updated

BibTeX
@article{chen2022encoding,
  author = {Yihang Chen and Zening Cao and Jinxin Wang and Yan Shi and Zilong Qin},
  title = {{Encoding Conversion Algorithm of Quaternary Triangular Mesh}},
  journal = {ISPRS Int. J. Geo Inf.},
  year = {2022},
  doi = {10.3390/ijgi11010033},
}

Loading related content...

Figure