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 is built only using the polygon vertices, and so does not always respect the polygon boundaries. This means the concave hull may not contain the input polygon.
It would be useful to be able to compute the "outer 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 hull of a polygon representing Switzerland
As with point-set concave hulls, the vertex reduction is controlled by a numeric parameter. This creates a sequence of hulls of increasingly larger area with smaller vertex counts. At an extreme value of the parameter, the outer hull is the same as the convex hull of the input.
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.
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).
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 PolygonHullSimplifier class in JTS.
The PolygonHullSimplifier 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 PolygonHullSimplifier 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 variant of Topology-Preserving Simplifier 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, or the net change in area. The resulting shape would be a good approximation of the input, but is not necessarily be either wholly inside or outside.
No comments:
Post a Comment