How robust is your spatial query? A formal taxonomy to express spatial intersections

Presentation | Presented

  • Yao Cui, Government of British Columbia
  • Michael Ross, Government of British Columbia

For any geospatial software, it is essential to implement spatial API for binary predicates and spatial functions, such as those defined by the Open Geospatial Consortium (OGC) Simple Feature Specification for SQL. To ensure accurate and robust spatial query results, the implementation such a spatial API should be validated by a comprehensive test suite.

In order to compile and organize test cases as part of a comprehensive test suite, a taxonomy was defined to express permutations of spatial intersections. It is based on Dimensionally Extended Nine-Intersection Model (DE-9IM) and has a geometric hierarchy of taxonomy. At the root of the geometric hierarchy, a geometry is identified by instantiable geometric types. For a given geometry type, it is identified by its interior, boundary and exterior. Each of the interior, boundary or exterior component of a give geometry in a given dimension is classified as primitive intersection components that are used in spatial intersections.

Backus Naur Form (BNF) notation is used to define the grammar for a language to express the intersections. The grammar was formally validated. By enumerating through the taxonomic hierarchy, it is interesting to discover that there are more than 60,000 possible intersection test cases.

The taxonomy was used as a guide to create and organize over 400 actual representative test cases for the validation of Java Topology Suite (JTS). It is recommended the test suite to be expanded for the validation of other free and open source geospatial software.

Supporting Files