Computational Science Asked by Addie on August 4, 2021
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.
Using the bounding box approximation, e.g., line AB
, for this polygon clearly wouldn’t provide an accurate result.
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.
Answered by Richard on August 4, 2021
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.
While the above should work for your "worm-like" polygons, there are plenty of pathological cases that will render the output value nonsensical.
Answered by LedHead on August 4, 2021
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.
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
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.
Answered by spektr on August 4, 2021
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP