ST_ApproximateMedialAxis returns multilinestring instead of single linestring

Question

ST_ApproximateMedialAxis on POLYGON returns MULTILINESTRING. Shouldn't it be just single LINESTRING?

We use Postgres 11 + PostGIS 2.5.0 (Geos 3.7.0), SFCGAL 1.3.6 (CGAL 4.13), pgrouting 2.6.1.

Please see attached image with the visualization of the input polygon (blue) and output (red).

Answer 1

From wikipedia, the "The medial axis of an object is the set of all points having more than one closest point on the object's boundary." This is a fairly dense definition, but it essentially means that the linestrings connecting the points are equidistant between the edges of the enclosing polygon. A few examples might help to illustrate the point.

1. The medial axis of a circle, is a single point, the center, as this point is equidistant to every point on the exterior.

2. The medial axis of a triangle is three lines from each vertex to the center point.

   

3. For a more complex shape, see you own example, or the example from the scikit-learn skeletonize library, which has the skeleton of a horse, where any extrusion in the boundary has a corresponding spur in the medial axis.

So, in fact, the only shape I can think of that would return a single LINESTRING as its medial axis, would be a bacillus shape.

Unfortunately, my attempts to demonstrate this using Postgis have been unsuccessful, as, a MultiLinestring is always returned, whether with ST_ApproximateMedialAxis or ST_StraightSkeleton, eg,

SELECT AS_AsText(
          ST_StraightSkeleton(
                ST_Buffer(ST_GeomFromText('LINESTRING(0 0, 10 10)')
                , 2, 'endcap=round')
          )
);

the buffer of a linestring with a rounded encap, is a bacillus shape, but this returns:

MULTILINESTRING((8.5857864376269 11.4142135623731,9.93052414277937 9.93052414277937),(-1.41421356237309 1.41421356237309,0.069475857220631 0.069475857220631),(-1.66293922460509 1.1111404660392,0 0),(-1.84775906502257 0.765366864730177,0 0),(-1.9 6157056080646 0.390180644032253,0 0),(-2 0,0 0),(-1.96157056080646 -0.390180644032259,0 0),(-1.84775906502257 -0.765366864730181,0 0),(-1.66293922460509 -1.11114046603921,0 0),(-1.41421356237309 -1.4142135623731,0 0),(-1.1111404660392 -1.66293922 460509,0 0),(-0.76536686473018 -1.84775906502257,0 0) ...

This, in no way undermines the answer, but points more to the fact that a buffer is an approximation, and the skeleton/medial axis is therefore subject to rounding errors.

EDIT: The definition of the difference between the medial axis and the skeleton is somewhat nebulous, see, for example, the skeleton definition from wikipedia: " The shrinking process, the straight skeleton (blue) and the roof model. In geometry, a straight skeleton is a method of representing a polygon by a topological skeleton. It is similar in some ways to the medial axis but differs in that the skeleton is composed of straight line segments, while the medial axis of a polygon may involve parabolic curves". This, definition clearly means in 3D, but, nevertheless, there is not a one to one mapping between them. Nevertheless, the medial axis will still, in most cases, return a MultiLinestring, as in the Postgis docs, except in the case of a trivial regular polygon, such as a rectangle.

In the case of a rectangle, the Skeleton, is a MultiLinestring,

SELECT ST_Astext(ST_StraightSkeleton(ST_Expand(ST_Makepoint(0, 0), 2, 10)));

MULTILINESTRING((-2 -10,0 -8),(2 -10,0 -8),(2 10,0 8),(-2 10,0 8),(0 -8,0 8))

whereas the medial axis is a single LineString, even though, it is return as a MultiLinestring.

SELECT ST_Astext(ST_ApproximateMedialAxis(ST_Expand(ST_Makepoint(0, 0), 2, 10)));

MULTILINESTRING((0 -8,0 8))

This is all rather nebulous and unsatisfactory, and, the big take away would seem to be that the word approximate is relevant, and that, broadly speaking, unless the shape is trivially regular, you will never get a single LineString back.

EDIT 2: From he actual definition of ST_ApproximateMedialAxis in the sfcgal source code. Note that the return type is defined to be

std::auto_ptr< MultiLineString > mx( new MultiLineString );

after which the straight skeleton is calculated. Finally, the function, skeletonToMedialAxis is called, which removes all angles of greater than 45 degrees, between the calculated skeleton and the original polygon edge. This explains both why it is always a MultiLinestring, but, also, why you don't get a single connected linestring back.