Given a ray and polygon, compute largest circle inside polygon, where center lies on ray and endpoint is on circle

Question

Given a simple polygon (not necessarily convex) and a ray whose origin lies inside the polygon, I'd like to compute the largest circle contained in the polygon, subject to the following constraints:

1. The center of the circle lies somewhere on the ray.
2. The origin of the ray lies on the circle.

Is there an algorithm to compute this exactly? What about an approximation?

Answer 1

(This answer works for convex regular polygons; I misinterpreted the term "simple" polygon.)

The center of the circle will be the same distance from the ray's origin and one of the polygon's sides. The set of points which are equidistant from a line and a point is a parabola.

If you divide the n-sided polygon into n sections, the circle will touch the side of the polygon which borders the sector that the center point of the circle is in.

So, to find the center point, do this for every sector that the ray passes through:

• Draw the parabola defined by the side of the polygon and the origin of the ray.
• If the parabola intersects with the ray inside the sector, the intersection is the center of the circle.

So it's really a matter of creating the equation for the ray and the parabolas, and finding the intersection.

(This is just a quick sketch, using circles instead of real parabolas; the parts should obviously meet up at the edge of the segments.)

Answer 2

Let C be the set of circles meeting the conditions of the problem (that is, the centre of the circle on the ray and the origin of the ray is on the circle).

Consider an edge e of the polygon. Then either:

1. None of the circles in C touch e. In this case, r(e) = ∞.
2. There's a smallest circle c ∈ C that touches e (either e is tangent to c, or else one of the endpoints of e lies on c — you can find c by solving for these possibilities). In this case, r(e) is the radius of c.

The answer you want is then min(r(e)).

Update Obviously you don't compute C (there are infinitely many circles in this set). What you do is to find the smallest circle c touching each edge e (if any such circle exists). For each edge e you compute three candidates for c: one that's tangent to e, and two that touch the endpoints of e, and take smallest of the viable candidates. So if there n edges, you consider at most 3n circles.