How to find the center of the minimal bounding circle for three (and more) shapes?

188 Views Asked by At

Suppose there are two rectangles with a common side (Figure A, blue line) or two quadrangles that do not have common points (Figure B, blue line).

It is required to construct the mininal bourding circle for two figures (case A, B).

Attempt, build two shapes to a rectangle, then find the intersection point of the diagonals. This point will be the circle center.

Question. Now to find the center of the minimal bounding circle for three (and more) shapes?

enter image description here

Edit after the fantasie's comment. Case A

Case B

1

There are 1 best solutions below

1
On BEST ANSWER

Find convex hull, in O(n)log(n) of initial n points at vertices of initial polygons via https://en.m.wikipedia.org/wiki/Graham_scan

Find minimum bounding circle of convex hull using Nimrod Megiddo's or Welzl's algorithm in O(n) of n points on convex hull.

Find center of the bounding circle. (trivial)