What are some algorithms to calculate the width of an arbitrary polygon when a bounding box approximation is inaccurate

2020-08-08

An answer to this question on the Scientific Computing Stack Exchange.

Question

What are some alternative algorithms to creating a bounding box for finding the max width of a concave, simple winding polygon, like the one in the below image? I prefer solutions that are more performant when implemented programmatically, even if they sacrifice some accuracy.

I am trying to calculate the max width of a winding polygon, where the max width could be, e.g, line CD. The polygon is drawn free-form using a collection of points and there's no guarantee that the width is constant across the polygon.

WINDING POLYGON

Using the bounding box approximation, e.g., line AB, for this polygon clearly wouldn't provide an accurate result.

WINDING POLYGON WITH BOUNDING BOX

Answer

You could use a medial axis transform

if the transform is discretized, each point in the transform indicates the radius from that point to the nearest two edges. Doubling this gives the width. To deal with noise, you could take something like the 95th+ percentile of such points and then average.

You could also look into rotating caliper methods:

though I suspect this will be less appropriate for your use case.