The **JTS Topology Suite** recently gained the ability to compute **concave hulls**. The Concave Hull algorithm computes a polygon enclosing a set of points using a parameter to determine the "tightness". However, for polygonal inputs the computed concave hull does not always respect the polygon boundaries. So the concave hull may not actually contain the input polygon.

It would be useful to be able to compute the **"outer concave hull"** of a polygon. This is a **valid polygon** formed by a **subset of the vertices** of the input polygon which **fully contains** the input polygon. Vertices can be eliminated as long as the resulting boundary does not self-intersect, and does not cross into the original polygon.

*An outer concave hull of a polygon representing Switzerland*

*A sequence of outer hulls of New Zealand's North Island*

The outer hull concept extends to handle holes and MultiPolygons. In all cases the hull boundaries are constructed so that they do not cross each other, thus ensuring the validity of the result.

*An outer hull of a MultiPolygon for the coast of Denmark. The hull polygons do not cross.*

It's also possible to construct **inner hulls** of polygons, where the constructed hull is fully **within** the original polygon.

*An inner hull of Switzerland*

Inner hulls also support holes and MultiPolygons. At an extreme value of the control parameter, holes become convex hulls, and a polygon shell reduces to a triangle (unless blocked by the presence of holes).

*An inner hull of a lake with islands. The island holes become convex hulls, and prevent the outer shell from reducing fully to a triangle*

A hull can provide a significant reduction in the vertex size of a polygon for a minimal change in area. This could allow faster evaluation of spatial predicates, by pre-filtering with smaller hulls of polygons.

*An outer hull of Brazil provides a 10x reduction in vertex size, with only ~1% change in area.*

This has been on the JTS To-Do list for a while (I first proposed it back in 2009). At that time it was presented as a way of simplifying polygonal geometry. Of course JTS has had the TopologyPreservingSimplifier for many years. But it doesn't compute a strictly outer hull. Also, it's based on Douglas-Peucker simplification, which isn't ideal for polygons.

It seems there's quite a need for this functionality, as shown in these GIS-StackExchange posts (1, 2, 3, 4). There's even existing implementations on Github: rdp-expansion-only and simplipy (both in Python) - but both of these sound like they have some significant issues.

Recent JTS R&D (on concave hulls and polygon triangulation) has provided the basis for an effective, performant polygonal concave hull algorithm. This is now released as the PolygonHull class in JTS.

### The PolygonHull API

Polygon hulls have the following characteristics:

- Hulls can be constructed for Polygons and MultiPolygons, including holes.
- Hull geometries have the same structure as the input. There is a one-to-one correspondence for elements, shells and holes.
- Hulls are valid polygonal geometries.
- The hull vertices are a subset of the input vertices.

The PolygonHull algorithm supports computing both **outer** and **inner** hulls.

**Outer hulls***contain*the input geometry. Vertices forming concave corners (convex for holes) are removed. The maximum outer hull is the convex hull(s) of the input polygon(s), with holes reduced to triangles.**Inner hulls**are contained*within*the input geometry. Vertices forming convex corners (concave for holes) are removed. The minimum inner hull is a triangle contained in (each) polygon, with holes expanded to their convex hulls.

The number of vertices removed is controlled by a numeric parameter. Two different parameters are provided:

- the
**Vertex Number Fraction**specifies the desired result vertex count as a fraction of the number of input vertices. The value 1 produces the original geometry. Smaller values produce simpler hulls. The value 0 produces the maximum outer or minimum inner hull. - the
**Area Delta Ratio**specifies the desired maximum change in the ratio of the result area to the input area. The value 0 produces the original geometry. Larger values produce simpler hulls.

### Algorithm Description

The algorithm removes vertices via "corner clipping". Corners are triangles formed by three consecutive vertices in a (current) boundary ring of a polygon. Corners are removed when they meet certain criteria. For an **outer hull**, a corner can be removed if it is **concave** (for shell rings) or **convex** (for hole rings). For an **inner hull** the removable corner orientations are reversed.

In both variants, corners are removed only if the triangle they form does *not* contain other vertices of the (current) boundary rings. This condition prevents self-intersections from occurring within or between rings. This ensures the resulting hull geometry is topologically valid. Detecting triangle-vertex intersections is made performant by maintaining a spatial index on the vertices in the rings. This is supported by an index structure called a VertexSequencePackedRtree. This is a **semi-static R-tree** built on the list of vertices of each polygon boundary ring. Vertex lists typically have a high degree of **spatial coherency**, so the constructed R-tree generally provides good **space utilization**. It provides **fast bounding-box search**, and supports **item removal** (allowing the index to stay consistent as ring vertices are removed).

Corners that are candidates for removal are kept in a **priority queue ordered by area**. Corners are removed in order of smallest area first. This minimizes the amount of change for a given vertex count, and produces a better quality result. Removing a corner may create new corners, which are inserted in the priority queue for processing. Corners in the queue may be invalidated if one of the corner side vertices has previously been removed; invalid corners are discarded.

This algorithm uses techniques originated for the Ear-Clipping approach used in the JTS PolgyonTriangulator implementation. It also has a similarity to the Visvalingham-Whyatt simplification algorithm. But as far as I know using this approach for computing outer and inner hulls is novel. (After the fact I found a recent paper about a similar construction called a Shortcut Hull [Bonerath et al 2020], but it uses a different approach).

### Further Work

It should be straightforward to use this same approach to implement a Topology-Preserving Simplifier variant using the corner-area-removal approach (as in **Visvalingham-Whyatt simplification**). The result would be a simplified, topologically-valid polygonal geometry. The simplification parameter limits the number of result vertices directly, or the net change in area. The resulting shape should be a good approximation of the input, but would not necessarily be either wholly inside or outside.

## No comments:

Post a Comment