The previous post introduced the new ConcaveHullOfPolygons class in the JTS Topology Suite. This allows computing a concave hull which is constrained by a set of polygonal geometries. This supports use cases including:
- generalization of groups of polygon
- joining polygons
- filling gaps between polygons
The algorithm developed for ConcaveHullOfPolygons is a novel one (as far as I know). It uses several features recently developed for JTS, including a neat trick for constrained triangulation. This post describes the algorithm in detail.
The construction of a concave hull for a set of polygons uses the same approach as the existing JTS ConcaveHull implementation. The space to be filled by a concave hull is triangulated with a Delaunay triangulation. Triangles are then "eroded" from the outside of the triangulation, until a criteria for termination is achieved. A useful termination criteria is that of maximum outside edge length, specified as either an absolute length or a fraction of the range of edge lengths.
For a concave hull of points, the underlying triangulation is easily obtained via the Delaunay Triangulation of the point set. However, for a concave hull of polygons the triangulation required is for the space between the constraint polygons. A simple Delaunay triangulation of the polygon vertices will not suffice, because the triangulation may not respect the edges of the polygons.
What is needed is a Constrained Delaunay Triangulation, with the edge segments of the polygons as constraints (i.e. the polygon edge segments are present as triangle edges, which ensures that other edges in the triangulation do not cross them). There are several algorithms for Constrained Delaunay Triangulations - but a simpler alternative presented itself. JTS recently added an algorithm for computing Delaunay Triangulations for polygons. This algorithm supports triangulating polygons with holes (via hole joining). So to generate a triangulation of the space between the input polygons, they can be inserted as holes in a larger "frame" polygon. This can be triangulated, and then the frame triangles removed. Given a sufficiently large frame, this leaves the triangulation of the "fill" space between the polygons, out to their convex hull.
The triangulation can then be eroded using similar logic to the non-constrained Concave Hull algorithm. The implementations all use the JTS Tri data structure, so it is easy and efficient to share the triangulation model between them.
The triangles that remain after erosion can be combined with the input polygons to provide the result concave hull. The triangulation and the input polygons form a polygonal coverage, so the union can be computed very efficiently using the JTS CoverageUnion class. If required, the fill area alone can be returned as a result, simply by omitting the input polygons from the union.
A useful option is to compute a "tight" concave hull to the outer boundary of the input polygons. This is easily accomplished by removing triangles which touch only a single polygon.
Like the Concave Hull of Points algorithm, holes are easily supported by allowing erosion of interior triangles.
The algorithm performance is determined by the cost of the initial polygon triangulation. This is quite efficient, so the overall performance is very good.
As mentioned, this seems to be a new approach to this geometric problem. The only comparable implementation I have found is the ArcGIS tool called Aggregate Polygons, which appears to provide similar functionality (including producing a tight outer boundary). But of course algorithm details are not published and the code is not available. It's much better to have an open source implementation, so it can be used in spatial tools like PostGIS, Shapely and QGIS (based on the port to GEOS). Also, this provides the ability to add options and enhanced functionality for use cases which may emerge once this gets some real-world use.
No comments:
Post a Comment