DGGS Operations‎ > ‎

Multi-Resolution Topological Relations

The Dimensionally Extended nine-Intersection Model (DE-9IM) is a model to define topological relationships between regions. On this page, we are going to explore several options to create a similar idea over DGGS structure.

Play with DGGS example of DE-9IM



Introduction to DE-9IM

the DE-9IM give us a tool to extend our language to define relationships between 2 geometries. Our language defines simple terms such as intersects, contained or distinct. However, terms like touch or overlaps can be several interpretations. In order to define those terms in a non ambiguous manner we define the following regions for each region:
  1. External - area that are outside of the region
  2. Border - the border of the region. we would explore in more depth that this term can be defined in several ways.
  3. Interior - area that is inside the region.
By define those 3 aspects. we can create a matrix that define the topological relations between two geometries. For example, we can define "Distinct" as relatation when "interior,interior","interior,border", "border,interior" and ""border,border" are all empty sets.



The DE-9IM start from set theory, and the current implementations and understanding are assuming a continues lattice to define the regions. As the result, the definition of a border can be defined as a pure line or points. However, DGGS uses multi-resolution tessellation of earth. As the result, DE-9IM for DGGS would have to assume finite number of cells for each resolution. Therefore, the Border of a region in DGGS is not a line, but a collection of cells.

Lets explore several ideas on how to port DE-9IM into DGGS:
  1. Simple Sets - we can define a region in a DGGS as a collection of cells. and therefore, we can assume DE-9IM as simple set operations. this method doesn't allow us to define a "border". and therefore, reduce the amount of DE-9IM expressions we can define.
  2. Morphological Sets - we can use DGGS cells connectivity to define a border of a set.  starting from a simple set, we can perform morphological erosion to define the region iterator, which also define region border. Moreover, by applying dilation step we can also define "touch" semantic. 
  3. Cell Coverage Sets - The previous method assume that a cell can only be inside or outside of a set. However, when quantize vector geometries, border cells are partially cover. We can detect the partial cover by interesting the vector with the cell geometry or by leverage multi-resolution aspect of the DGGS and perform a simple raster on higher resolution and aggregate it into lower resolution. By adding coverage information for each cell we can perform more accurate definition of border. 

Simple DE-9IM

This method assume input for the DE-9IM as two set of cells on the DGGS. If the two sets are not on the same resolution, a DGGS zoom-in or zoom-out can be performed on the set of cells. Therefore, we will assume both sets are on the same resolution. 

Because we start from simple set of cells we can define the following:
  1. Interator = Set of cells
  2. External = All cells in resolution - set of cells
  3. Border = empty sets.
Because the border is always an empty sets, this method can only define a sub-set of DE-9IM, As been visualized in the following matrix:


Therefore, "Intersect", "Equals", "Distinct" and "Overlaps" - can be defined. However, "Touch" and other relationships based on border can not be expressed using this method.
 

Morphological DE-9IM


Morphological operation over DGGS can be used to extend the definition of border. For example, we can perform erosion on set of cells to define the interior of a region. all cells been removed by the erosion operation would be defined as a border. 

Erosion based DE-9IM

There are few point worth mentioning when compering this method and one defined for vector DE-9IM:
  1. The definition of border for lines is not the same. in other DE-9IM definition,the border of a line are the end-points of that line, and the interior are all all points at the line without the border end-points. However, by apply erosion operation a line would have no interior but border only.
  2. Touch operation can be expressed using this method. However, touch mean that there is overlaps only on border cells. To express cells that are near each oher (neigboor cells) as touch we can leverage dilation operation to extend the defintion of border.
There are 2 ways to extend our method to include dilation method:
  1. Extended Border - we ca define border as dilation(region) - erosion(region). In order words, extend the border to include all cells touching the original set. this would enable touch operations to be more inclusive. However, distinct operation might require the regions to be more far apart before defined those.
  2. Define "Near" - We can define near as dilation(region) - region. by extending our matrix to 4x4 we can now express the same DE-9IM operations we different levels of inclusion (or relaxation).
Erosion and dilation based DE-9IM

Coverage DE-9IM

Another way to define border cells is to include more information about the coverage of a cell. In other words, how much of the cell are is included in the region. We can use this number to improve our matrix definition:
  1. Cells with 0% coverage considered  to be exterior.
  2. Cells with 100% coverage considered to be interior.
  3. Cells with coverage between 0-to-100% coverage consider to be border cells.
Moreover, for a given cell. if coverage(A)+coverage(B) > 100, we can include that region A and B have to intersects at that cell.


Comments