Circle approximation can freeze host application for extended time

[hannobraun]

The circle approximation code contains a loop that can become long-running, if the tolerance parameter is unreasonably low. This happened once before, due to a bug in calculating tolerance.

I think that we can do away with that loop completely by being a bit more clever about calculating n, which would solve the problem. I haven't actually sat down and done the math though, so I'm not 100% sure.

If it turns out this is not possible, then an alternative solution would be to create some system that can monitor and abort long-running algorithms. We might need something like that anyway, long-term, but that one loop is not a good enough reason to work on that now.

Labeling as good first issue, as this is basically a math problem, and the affected code is fully contained within a reasonable method.

[kastolars]

Could you provide some academic references on what this loop is attempting to achieve? I'd like to read up on this so I could possibly contribute.

[hannobraun]

Hey @kastolars, thank you for your interest!

That method creates a regular polygon to approximate a circle. The tolerance value determines how far that regular polygon is allowed to deviate from the circle. Give it a really low tolerance value, and it might produce a 100-sided polygon. Give it a really high value, and you might end up with a triangle.

That loop in particular determines how many-sided the polygon needs to be. It starts with a triangle, determines how far that triangle deviates from the ideal circle. If it's too much, it does a n += 1 and tests a square in the next loop. And so forth, until it ends up with an n-sided polygon that is close enough to the circle, according to tolerance.

As per the comment in the code, the ideal circle is the circumscribed circle of the approximated polygon (meaning the polygon's vertices are on the circle, the rest of the polygon is in it). The points on the polygon that are farthest from the circle are the center points of the edges. Since that is where the polygon's incircle (([1], [2], [3]) touches the polygon, we can compute the maximum deviation between polygon and circle by subtracting the incircle radius from the circumscribed circle radius.

So the problem boils down to this:

• Given an n-sided regular polygon
• with an incircle of radius r1
• and a circumscribed circle of radius r2
• find the smallest n for which r2 - r1 is equal or less than a given tolerance.

r2 is just the radius of the ideal circle, and r1 can be computed with a bit of trigonometry (which the code presumably is already doing in the let incircle = ... line; although now that I look at it again, I think that code is probably wrong).

That loop solves this problem using the brute-force method, and I hope we can come up with an equation that we can just plug the circle radius and the tolerance value into.

Does that help?