Detecting branched polygon shape?

Question

I have a vector layer with millions of polygons making continuous coverage. I need to classify them according to their shape. I am already using several shape indexes from landscape ecology like compactness (4piA/P^2), mean width (2A/P), shape number (P/sqrt(A)), I also saw this answer to Calculating roundness/compactness of polygon?

My problem is that all these metrics are using some ratio of area and perimeter only. Even the Fractal Dimension index is using only area and perimeter (2ln(0.25P)/ln(A)). But how can I distinguish two polygons with the same area and perimeter but absolutely different shape? Like this branched polygon A:

which I tried to draw with the same area and perimeter as curved strip B. All my known indexes will be the same for them. But for me it's very important to differentiate simple strips (including curved like new moon) from complex branched shapes.

I intentionally show the polygon B as a curved strip and not a straight strip because I am aware of Related Circumcircle index which detects straight elongated shapes but my polygons may have also the same circumcircles. Even if I construct Convex hull and calculate a ratio of areas Apolygon/Aconvex, it may be very similar here.

So, how can I clearly distinguish branched polygon A from polygon B in vector data automatically? (Converting them to raster would require extremely small cell size, enormous dataset and a lack of memory, so it is not possible). Are there other shape indexes which include other parameters? Ideally, the method would distinguish not only clearly branched polygons but even C and D:

My only idea is to construct the convex hull then erase the polygon from it's convex hull and count the number of (big) pieces it leaves (erasing polygon by polygon and not the entire layer). This could show the border complexity.

I welcome mathematical solutions/algorithms, which I would later implement in Python.

gisnside · Answer

You could have a look at the following method : skeletonize your polygons and rather work on line type features related to your original polygon with a unique source polygon ID. I guess there's some guesses to do (for example, when to consider a polyline as a real centerline : minimal length for a polyline to be eligible to centerline status). When the number of centerline is more then 1 for a single source polygon, then it's branched.

A branched polygon, when cleaned up to a center line, will have multiples lines whereas a straight polygon might have only one big line in the center (same as human interpretation in fact).

Example :

when you draw a Y letter, you use at least 2 continuous strokes (= 2 polylines),, so it's branched because the minimal number of strokes is > 1.
when you draw an L letter, you use at least 1 continuous stroke. It's not branched.

More examples of this logic :

When you draw a A : 2 strokes = it's branched 
When you daw a B : 3 strokes = it's branched
when you draw a C : 1 stroke = it's not branched
etc

I haven't tried anything, just trying logic, but I think it could work.

See : Skeletonize vectors in QGIS/Python or http://postgis.net/docs/ST_StraightSkeleton.html

Or

Source: Extracting centerline of a Complex-Polygon in PostGIS/Python

EDIT : For cases C & D, you need to already have filtered B shapes (non branched).

Make sure a unique ID links the centerline and the source polygon.
Transform your polygons into polylines
Densify the centerline polyline and the borderline polyline with regular points (not too much to avoid memory problems later but enough to "catch" the irregular bits.
Create a distance matrix between points of the centerline and the points of the borderline
Keep in the matrix lines only those where ID_centerline = ID_borderline 
Create statistics to have a  standard deviation value
Set a bound value to indicate for high SD values that it's a non regular contour and create the required indicator, for each unique ID
Get back the indicator to the original polygon by joining the field on the base of the unique ID.

Jan Šimbera · Answer

In addition to the indices you mention and the excellent skeletonization idea, there are a few more indices that could be interesting if you can calculate buffers and convex hulls easily:

Fullness index: ST_Area(ST_Buffer(geometry, 0.177245385 * sqrt(ST_Area(geometry)))) / ST_Area(geometry)
Depth index: ST_Area(ST_Buffer(geometry, -0.177245385 * sqrt(ST_Area(geometry)))) / ST_Area(geometry)
Concavity index: 1 - (ST_Area(geometry) / ST_Area(ST_ConvexHull(geometry)))
Detour index: 3.5449077 * sqrt(ST_Area(geometry)) / ST_Perimeter(ST_ConvexHull(geometry))

(the expressions work for PostGIS and are taken from https://github.com/simberaj/rum/blob/master/rum/util.py)
For reference and explanation, you might want to see this article on compactness properties.

Detecting branched polygon shape?

2 Answers

Add your own answers!

Ask a Question