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

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 1

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.

Answer 2

I'm sure there are better solutions than this, but since no one else has answered to this point, I'll throw out a this-is-what-I'd-do answer.

1. Triangulate the polygon If your polygon doesn't have too many points, a simple $\mathcal{O}(N^2)$ ear-clipping method could be viable. For large polygons, this might be an inefficient solution. It's important to the next step that this triangulation only uses the existing vertices and doesn't introduce any new internal points.
2. Find triangle heights Every triangle which has exactly one external edge is guaranteed to span across the polygon, so calculate the orthogonal distance from the external edge to the opposite vertex of the triangle.
3. Reduce to a single number Since you have a value for every admissible triangle, you need to reduce that down to a single number. Min, max, mean, median? Maybe take a mean after you throw out outliers?

While the above should work for your "worm-like" polygons, there are plenty of pathological cases that will render the output value nonsensical.

Answer 3

I am going to assume that we have arrays of the edges representing the top and bottom curves for the winding polygon with edges going from left to right. Also make $n$ as the total number of edges in this polygon. Now consider the following visualization of the geometry where we construct some point using the two "sides" of the concave polygon:

It is clear if we shoot any ray from the point, given the direction is any convex combination of the directions to the two "sides" of the polygon, then the ray will intersect exactly two edges. Let us assume there exists some helper method that can take two line segments and return the maximum distance between them.

Deterministic Algorithm

If you want a deterministic algorithm, here is one idea using ideas based on the assumptions and ray stuff described above. Suppose we fix some edge $e = (v_1, v_2)$ from the top boundary. We can look at all edges from the bottom boundary that have at least one vertex between the rays drawn to the two vertices of $e$ and compute the maximum distance between them and $e$, using this result to update the overall maximum width for the polygon. If we fan over the polygon from left to right, we can do all of this work in $O(n)$ time since as we check a new edge on the top boundary, we can pick up where we left off in the bottom boundary instead of starting from scratch. Below is a visual of how things get partitioned

Randomized Algorithm

Given the earlier assumptions, the following Monte Carlo styled randomized algorithm could also be a solution:

algorithm RandomizedMaxWidth
input (top_boundary[...], bottom_boundary[...], k)
output max_width

init max_width = 0
for i from 1 to k
   - randomly choose an edge e from (say) the top boundary (can do this with or without replacement)
   - use binary search to find first edge in the bottom boundary, denoted e1, that intersects ray going through left vertex of e
   - iterate over all edges from left to right, starting with e1, that have at least one vertex between the rays generated by the left and right vertices of e
      - for each edge, compute the maximum width between this edge and e using helper method and update the max_width accordingly
endfor

return max_width

The runtime of the above algorithm using sampling with replacement is $O(k (\log(n) + c))$ where $c$ corresponds to the average number of edges in the bottom boundary that intersect rays that intersect an edge in the top boundary. The probability of failure corresponds to the probability that you never select the edge on the top boundary that corresponds to the maximum width. This error probability shrinks as $k$ gets large and if you randomly choose edges with replacement, $k = O(n)$ gives a constant probability result, implying the runtime is $O(n \log(n) + n c)$. But if the shapes are generally as "nice" as we see in the example, you may be able to get decent approximations (especially compared to the bounding box approach) making $k$ sublinear in $n$, which would make the algorithm as a whole potentially sublinear in $n$, depending on the value of $c$.

If you hate the constant $c$, you could modify this algorithm to randomly construct a ray with a direction randomly chosen between the directions corresponding to the two "sides". You would then, for each random ray, find the two intersecting edges and then compute the maximum width between these two edges. If you use $k$ random rays, this algorithm then gives an $O(k \log(n))$ runtime. With a large enough $k$, you should get a decent estimate, though the error probability could be larger compared to the above algorithm. Again, if shapes are "nice" generally, choosing $k$ to be sublinear in $n$ could be enough to get a decent result in practice, implying an overall sublinear randomized algorithm.

In fact, for the example drawn in the original question, a single sample would prove to be much more accurate than using the bounding box approach, which would give us an $O(\log(n))$ approximation algorithm.