3
$\begingroup$

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 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 Winding Polygon with Bounding Box

$\endgroup$
  • $\begingroup$ Is the shape of the polygon qualitatively always the same as in the picture? $\endgroup$ – Maxim Umansky Aug 8 at 4:59
  • 1
    $\begingroup$ I helped on a biomaterial project, where we used some characteristics of the shapes to classify cells. Elongation is very similar to what you need (M. Stojmenovic, J. Žunic, J. Math. Imaging Vis., 2008, 30, 73). Solidity might also be helpful depending on if the shapes you are considering are self-intersecting, e.g. not handwriting. Solidity is the ratio of the area of the shape divided by the area of the convex hull of the shape. This research field in general is called shape analysis or shape descriptors. The literature is quite rich. $\endgroup$ – Abdullah Ali Sivas Aug 8 at 6:18
  • 1
    $\begingroup$ A important question is what informations do you have of the shape. Only the point cloud or realy the polygon including its connectivity? $\endgroup$ – ConvexHull Aug 8 at 8:27
  • 1
    $\begingroup$ My approach would be to implement an algorithm that would analyze the geometry, with an assumption that the shape belongs to a certain class. Can we say that the shape is a "curved quadrilateral", defined by a curve $\vec{r}(s)$along the long direction of it, and by the width $w$? If so then one can extract those main features from a given polygon. $\endgroup$ – Maxim Umansky Aug 8 at 14:53
  • 1
    $\begingroup$ As a first step define what "width" means, so we can be sure that an algorithm really does find (or approximate more accurately) the "max width". The notion may seem obvious to you, but a well-founded definition may depend on the class of shapes you have in mind. Comparison with the diameter of a polygon may illustrate the importance of a definition. $\endgroup$ – hardmath Aug 8 at 15:22
2
$\begingroup$

You could use a medial axis transform

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:

Rotating caliper

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks. Is there a particular algorithm that you recommend to calculate the discretized medial axis transform for a simple polygon like in my example? $\endgroup$ – Addie Aug 9 at 23:42
  • $\begingroup$ Also, is this type of medial axis called a "straight skeleton"? $\endgroup$ – Addie Aug 9 at 23:48
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Correction: Richard posted an answer 9 seconds before me :) $\endgroup$ – LedHead Aug 8 at 19:29
2
$\begingroup$

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:

visualize new geometric frame

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

fan partition

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.