As long as the polygon is reasonably small (under, say, a few hundred miles at typical latitudes) and not near a pole, we can simplify to the euclidean case. Then it is possible to use the Separating Axis Theorem to solve the problem.
Convert to distances
First things first, since our radius is in a distance measure (meters maybe?), We need to convert our lat/long coordinates into distance-type values as well.
This can get quite distorted far from our chosen meridian, so we will first subtract our center's longitude from the longitude of each of our polygon's vertices. Then to make the numbers less terrible we'll move the whole thing so our center is at $(0,0)$ in our euclidean space:
$$(x,y)=(\cos(\phi)(\theta-\theta_C), \phi-\phi_C)\cdot R$$
Where $(x,y)$ are the euclidean coordinates, $\theta$ is the longitude, $\phi$ is the latitude, $?_C$ denotes that this value comes from the center, and $R$ is the radius of the Earth in the same units as the uncertainty radius. Note: all angles are assumed to be radians; you may need to convert to get there.
Convexity
Next, because SAT requires convex polygons, we'll need to make sure we only give it convex polygons. The typical way of going about this is to use triangulation. There's lots of algorithms for that.
While you're doing this, you want to maintain the same winding for all your polygons - if one polygon has its vertices listed in clockwise order, so too must all other polygons, and vice versa. To maintain winding while breaking a polygon along an internal edge, the two new vertex lists should keep their order and simply remove the vertices that are exclusive to the other polygon: splitting $ABCDEFG$ along $CF$ should give $ABCFG$ and $CDEF$. Note that this makes one polygon have $CF$ as an edge and the other have $FC$; this is intentional.
Lines and Separation
Finally, given our convex polygons, we will generate lines that enclose each polygon; a point that's inside the polygon will be on the same side of every enclosing line. To make the results as convenient as possible, our goal should be Hesse Normal Form for the lines; this form gives, conveniently, the distance of the line from the origin with little hassle.
Given two points $A$ and $B$, a line through them can be expressed as: $$\vec n =\frac{\perp(A-B)}{|A-B|}$$ $$\vec n \cdot x = \vec n \cdot A$$ where $\perp (x,y) = (y,-x)$, a perpendicular vector.
This constant on the right is the distance between the line and the origin; this is convenient because we moved our center to the origin! The only thing left to consider is the radius.
If every line constant for a given polygon is less than the uncertainty radius, (or, depending on winding, more than the negative of the uncertainty radius), then the circle may intersect with that polygon. If even one exceeds that, then they do not intersect.
May
There is however one situation where all the lines say our circle is partly inside but we're not: these lines define a somewhat bigger polygon, but the envelope of locations where the circle and polygon collide is a rounded polygon. We need to figure out when that happens.
It only happens when the center is outside the polygon - when the highest (winding: lowest) line constant is positive (winding: negative). In addition, the center must be closer to a vertex than to a segment. That will happen if, with regards to the line with the highest constant, either $\angle ABC$ or $\angle BAC$ are obtuse, that is, if $(A-B)\cdot(C-B) < 0$ or $(B-A)\cdot(C-A) < 0$. Whichever one is true, we must check the distance between the center and the point; if it's greater than the radius then the circle and polygon don't collide.
In Summary
- Convert the polygon into Euclidean coordinates.
- Break the polygon into convex components.
- Turn each convex polygon into a set of lines.
- Test each convex polygon for collision.
If any convex polygon collides with the circle, then the circle and overall polygon collide.
Let G and H, I be the midpoints of BC and DE, as O is the center OG, OH, OI are perpendicular to BC, DE, AF and let R be the radius of the circumscribed circle of the equilateral triangle,
You can find OG and OH by pyth. theorem,
$OG=\sqrt{R^2-18^2}$
$OH=\sqrt{R^2-18^2}$
$OI=\sqrt{R^2-18^2}$
by these
$OG=OH=OI=h$
Also by pyth. theorem you can get the lengths of BY, CZ, DZ, XE, XF, AY
$BY=18-\sqrt{12^2-h^2}$
$CZ=18-\sqrt{12^2-h^2}$
$DZ=18-\sqrt{12^2-h^2}$
$XE=18-\sqrt{12^2-h^2}$
$XF=18-\sqrt{12^2-h^2}$
$AY=18-\sqrt{12^2-h^2}$
With above you can find out $\triangle ABY, \triangle DCZ, \triangle XFE$ are equilateral and the side lengths of each other are equal.
By angle chasing you can find that the all angles of the hexagon is equal 120 and it is a regular hexagon.
As OB bisects $\angle ABC$, $\angle ABO=60$ and the one side of the hexagon will be equal to 12 (radius of the inscribed circle)
And the perimeter will be equal to = 12*6=72
Your answer is correct here is the proof for it
Best Answer
I don't know of an algorithm that solves this problem, but there is an algorithm that solves a similar problem. It's called the medial axis transform (source) (source), or computing the straight skeleton of a polygon. The result can be interpreted as an infinite number of circles that perfectly recover the original polygon. If you are looking to minimize the area outside, and don't care about the number of circles, then this algorithm is optimal.
In order to get a realistic answer, as you mentioned, you need to define a tradeoff between the number of circles and the extra area covered. It is probably possible to do some post-processing on the skeleton to get a reasonable result. I have also seen implementations that consider circles of a fixed size, which makes the problem much simpler. As a warning though, this problem looks a lot like the NP-hard bin packing problem, so it may be hard to find a good solution that runs quickly.