The previous post discussed **polygonal coverages** and outlined the plan to support them in the **JTS Topology Suite**. This post presents the first step of the plan: algorithms to validate polygonal coverages. This capability is essential, since coverage algorithms rely on valid input to provide correct results. And as will be seen below, coverage validity is usually not obvious, and cannot be taken for granted.

As described previously, a polygonal coverage is a set of polygons which fulfils a specific set of geometric conditions. Specifically, a set of polygons is **coverage-valid** if and only if it satisfies the following conditions:

**Non-Overlapping**- polygon interiors do not intersectalso called**Edge-Matched**(**Vector-Clean**and**Fully-Noded**)

**Non-Overlapping**condition ensures that no point is covered by more than one polygon. The

**Edge-Matched**condition ensures that coverage topology is stable under transformations such as reprojection, simplification and precision reduction (since even if vertices are coincident with a line segment in the original dataset, this is very unlikely to be the case when the data is transformed).

*An invalid coverage which violates both (L) Non-Overlapping and (R) Edge-Matched conditions (note the different vertices in the shared boundary of the right-hand pair)*

#### Computing Coverage Validation

**invalid**situations occur:

**Interiors Overlap:**- the polygon linework crosses the boundary of the adjacent polygon
- a polygon vertex lies within the adjacent polygon
- the polygon is a duplicate of the adjacent polygon
**Edges do not Match:**- two segments in the boundaries of the polygons intersect and are collinear, but are not equal

**coverage-valid**with respect to the adjacent polygon. If all polygons are coverage-valid against every adjacent polygon then the coverage as a whole is valid.

#### JTS Coverage Validation

*nearly*valid, since only one invalid polygon was found. The invalid boundary linework returned by CoverageValidator allows easily visualizing the location of the issue.

*A polygonal dataset of 91,384 polygons, containing a single coverage-invalid polygon*

*The invalid polygon is a tiny sliver, with a single vertex lying a very small distance inside an adjacent polygon.*

*The discrepancy is only visible using t*

*he JTS TestBuilder Reveal Topology mode.*

#### Real-world testing

Source | City of Vancouver |

Dataset | Zoning Districts |

This dataset contains 1,498 polygons with 57,632 vertices. There are 379 errors identified, which mainly consist of very small discrepancies between vertices of adjacent polygons.

Source | British Ordnance Survey OpenData |

Dataset | Boundary-Line |

File | unitary_electoral_division_region.shp |

*An example of overlapping polygons in the Electoral Division dataset*

*An example of overlapping polygons (and a gap) in the*VerwaltungsEinheit

*dataset*

**UPDATE**: my colleague Paul Ramsey pointed out that he has already ported this code to GEOS. Now for some performance testing!