# Detecting branched polygon shape?

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.

• You don't need much Python. Try ! shape!. convexHull (). symmetricDifference(!shape!) In field calculator. Try first on a small subset copy. See arcpy geometry help for correct syntax. – FelixIP Sep 6 '17 at 19:09
• This could be a great question but at the moment you are asking multiple questions by not tying down whether you are asking about QGIS or ArcGIS Desktop and then also throwing in Python too. Once you specify precisely what you have tried it is easier for potential answerers to help with where you are stuck. I suggest focusing it on QGIS to avoid stranding your first answer. – PolyGeo Sep 6 '17 at 20:58
• I have data in Esri geodatabase because a shapefile already was exceeding 2 gb. I could do something about this if there is a working solution in QGIS or somewhere. But I am not asking inside a specific software. I am asking about a metric, a method how to mathematically detect a shape with complex border (branched). 1 question. Scientific article with a formula would be also ok, I will think how to implement it myself. – nadya Sep 7 '17 at 10:25
• My first thought was the same as yours, looking at the differences between the number and size of polygons left after subtracting the original from its convex (or concave) hull (see also alpha shapes). – user2856 Sep 11 '17 at 10:32
• If only skeleton was fast enough to compute I'd use to to compute 4A/PL, area, perimeter, length between farmost nodes of skeleton for compactness. Same applies to largest inscribed circle. – FelixIP Sep 11 '17 at 19:24

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.

Or 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.
• Thank you for the idea, I will try to create centerlines – nadya Sep 6 '17 at 16:43
• Just, the problem to distinguish my polygons C and D will remain – nadya Sep 6 '17 at 16:47
• You might need different methods for different cases and split the work. Once you have non branched polygons (B), you can refine B to try and find C and D. The problem is that i don't see what logic you use to distinguish C from D. you will probably have to phrase it clearly with criterias. – gisnside Sep 6 '17 at 17:18
• The difference between C and D seems to be that in C, the sides of the polygon are approximately a uniform distance from the centerline, while in D the sides are a non-uniform distance from the centerline. – csk Sep 6 '17 at 18:22
• @csk I see that. I guess translating that into code would be calculate statistics on the distance between centerline and border line. By densifying the border polyline with more points then converting this border into points + making a distance from the equivalent job on the centerline would give statistics on this behaviour. If the standard deviation is high, then probably the shape will be irregular. Hard to see how to do that on tousands of polygons though...nice challenge there – gisnside Sep 7 '17 at 5:04