2
$\begingroup$

I have seen (and implemented) algorithms that find the 'Pole of Inaccessibility' for a polygon - that allows you to draw the largest circle within it. However, if I wanted to find the largest semi-circle that fits inside a polygon, is there a similar method?

EDIT: I use this algorithm MapBox polylabel to calculate the largest circle that will fit inside a polygon. Whilst I understand what it does, I can't really see a way to apply it to semi-circles.

I feel as if the answer might start with trying to find the longest line inside the polygon that has the smallest average distance to the boundary, which might align it close to the longest straight(ish) part of said boundary.

I re-implemented this Largest Rect in a Poly which I feel could have some bearing on my thoughts above in the way that it searches for longest lines inside the poly.

But its easy to come up with shapes where the largest semi-circle is not really approximated by either the largest circle or the largest rectangle.

$\endgroup$
6
  • 1
    $\begingroup$ Welcome to MSE. Please include your own thoughts and the effort made thus far, so that people can work with you accordingly. (Please add those in the body of the question instead of commenting.) This is a difficult problem, so it is particularly important to do so. $\endgroup$ – Lee David Chung Lin Feb 17 '20 at 4:22
  • $\begingroup$ The positioning of a largest semi-circle within a polygon (perhaps a convex one??) will naturally be more difficult because an additional parameter is involved. Have you done any research to answer your Question? Sharing the fruits of that search would expedite the responses of willing Readers. $\endgroup$ – hardmath Feb 17 '20 at 15:48
  • $\begingroup$ I'm not really following the concept here? I'm not a mathematician. If I knew how to do this, I wouldn't be asking, would I? The whole point of me posting was to avoid countless fruitless hours of Googling and trying to understand maths, if someone already knows how to approach the problem. Nevertheless, I'll update the question with my research, such as it is. $\endgroup$ – Kyudos Feb 18 '20 at 2:52
  • $\begingroup$ In trade for saving you the countless hours of googling, we ask that you save us hours of trying to answer questions that turn out not to be what folks really need to solve (example: "I need to do arithmetic with 5000-digit numbers", failing to mention that the end result will be the reduction, mod 13, of whatever gets computed...) or the answer to which is beyond their understanding ("I'm 11 years old, and I want to understand Wiles' proof of Fermat. Can you explain it to me without algebra?") So forgive us if we ask a few questions before spending lots of our time on your problem. $\endgroup$ – John Hughes Feb 18 '20 at 3:56
  • $\begingroup$ This is an extremely hard problem and not being a mathematician does not justify dumping the work on others. If you have absolutely no approach to this problem, then chances are you would not understand the answer either (if there is one). $\endgroup$ – Sam Feb 18 '20 at 4:24
0
$\begingroup$

My Approach Thus Far

Using the largest rect routine above, I find the largest 2:1 rectangle that will fit. And (if necessary) move it parallel to the short edge until it is on the boundary.

One

I then draw a semicircle on each of the long edges, and see if I can make it bigger.

Two Three

I then move the rectangle parallel to the short edge again, until it is on the other side. Then repeat the semicircle jigging around.

enter image description here

It's not perfect, but it's a decent start.

EDIT: It seems it would also be worth testing the 'internal' semi-circle formed by each line segment of the polyline. There also feels like there is a geometric solution to finding the largest edge-aligned internal semi-circle for each segment, but I can't quite get my head around it yet.

$\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.