0

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.

user1805103
  • 1
  • Maybe one could adapt an algorithm for the largest empty circle problem to take the distance of the circle to the bounding box into account forcing possible solutions to stay inside the bounding box. I am a bit worried about your examples though, as the lines are so squiggly. Are they supposed to be straight or do you mean literally any set of points? – Jonas Linssen Jun 18 '20 at 09:29
  • I am using squiggly lines to represent any arbitrary number of points connected and to indicate that the points/lines may not (indeed, likely will not) be regular. Thus, my lines could be considered an arbitrary number of unconnected points unconnected or points connected as lines. Does not matter for the example. Also, it does not have to be intersecting lines. Could be an oval shape, e.g., with an oriented minimum bounding box. In the oval example, the largest circle would be inside the oval. Thanks. – user1805103 Jun 18 '20 at 16:02
  • I am asking, because this makes a huge difference even in stating the problem. If there are only finitely many points involved or you restrict yourself to certain geometric shapes like lines, I am fairly sure that there are (modifications of) existing algorithms, which solve the problem. However if you allow arbitrary lines, we can get weird edge cases like „a square fully filled by points“. We have to be very careful how to pose the question then. – Jonas Linssen Jun 18 '20 at 16:17
  • You are raising a good point. In my problem, there are a finite number of points. Those points are connected make lines. But when connected, the lines may form curves. What I am really trying to do is characterize the shape in the bounding box in an indirect way by figuring out how much/how little of the bounding box is occupied. – user1805103 Jun 18 '20 at 16:27

0 Answers0