Largest Circle Enclosed In Oriented Minimum Bounding Box But Not Including Points/Lines

65 Views Asked by At

I am wondering if someone can suggest a way to find the largest circle that can fit within the oriented minimum bounding box for a set of points/lines, that does not include any of the points/lines.

Consider these two images:

Cross Tee

Each image is enclosed by its oriented minimum bounding box (just parallel to the X-Y axis to make things easier).

The "Cross" figure will have a circle that fits in one of the triangles while the "Tee" figure will have a circle that will fit on one side of the "T."

Thus, the issue is to find a generalized approach that can find such a circle and its radius/diameter.

This seems to be a different problem than finding the minimum bounding circle, the maximum inscribed circle, or the largest empty circle problem.

The largest empty circle problem appears close, but (if focused on the points/lines only) would exceed the size of the bounding box.

I am looking for a generalized way of finding the circle and its radius/diameter that will work for any oriented minimum bounding box and number of points/lines in a 2D space.

Thanks for any help.