Find the largest circle that fits in a planar curve: can this be faster and more precise? (23.7 KB)

For a convex polygon K there is a classic solution the Chebyshev center.
The solution is a linear optimization problem with linear inequality constraints.
Let the m-gon K be represented by the m inequalities a_i \cdot x<=b_i, where a_i is the 2d unit vector that is the outward normal of an edge of K. The variables of the optimization problem are the coordinates of the circle (x1, x2) and the radius r. The objective is to maximize r subject to a_i \cdot x +r <= b_i


Some time ago I also implemented this one by translating C++ to C# for OpenNest, works nice even if it is not fully touching all the sides:

For me this was needed to find a good placement of a label, since it was rarely a medial center of points.

1 Like