I have the four vertices of a rectangle. I need to find it's smallest enclosing circle. For example:
I need to find the radius of the circle.
[Math] How to find the smallest enclosing circle for a rectangle
circlesgeometry
Related Solutions
If your goal is to "draw" the smallest circle and you don't really care about the numerical values of its center and radii too much, You can construct it in a geometrical manner.
Let's say the three circles are centered at $A$, $B$ and $C$ respectively.
There are two possibilities.
- The smallest circle is touching two of the circles. In this case, the center of the smallest circle will be collinear with the center of the two circles it touches.
- The smallest circle is touching all three circles.
It is clear how to construct the smallest circle in $1^{st}$ case. For the $2^{nd}$ case,
- Construct a line passing through $A$ and $B$.
- Let $G$ be the intersection of line $AB$ with circle $A$ on the opposite side of point $B$.
- Let $H$ be the intersection of line $AB$ with circle $B$ on the opposite side of point $A$.
- Let $I$ be the mid-point of $G$ and $H$.
- Construct a hyperbola passing through $I$ having $A$ and $B$ as foci (the red curve in the picture below).
- Repeat the same procedure to the two other combination of pairs of circles to obtain three hyperbolas (the red, green and blue curves in picture below).
These 3 hyperbolas will intersect at two points $P$ and $R$. The point $P$ is the one which lies on the branch that contains the mid point $I$. It will be the center of another candidate of smallest circle (the orange circle) you want.
At the end, we will obtain four candidates of the smallest circle and it is easy to check which one is the smallest one.
In any event, in the $2^{nd}$ case, one can compute the coordinates of the center $P$ by first figuring out the equations for the three hyperbolas and then determine their intersection. The algebra will be a mess and I'll let you have the fun (if you really want that).
Real solution:
B. Gärter from ETH zurich has come up with this C++ package embodying the algorithm to solve the problem. Even in higher dimensions. https://people.inf.ethz.ch/gaertner/subdir/software/miniball.html
more info here: https://www.inf.ethz.ch/personal/emo/DoctThesisFiles/fischer05.pdf
I leave my previous answers below so people can see how primitive they are.
Approximation involving center of mass of the points:
Let $c(x_i,y_i,r_i)$ define a circle with position $(x_i,y_i)$ and radius $r_i$
Let $(x_c,y_c) = { (\sum_{i=1}^{n}x_i/n \:,\sum_{i=1}^{n}y_i/n)} \:\:\:\:\:$ be the center of of mass of the $n$ circle positions.
Next our concern is finding the smallest radius $r_c$ that encloses the circles from the center of mass.
This is done by finding the maximum value of the distance from the center $(x_c,y_c)$ to the circle center positions $(x_i,y_i)$ plus their radius $r_i$:
$r_c = max (\sqrt{(x_c - x_j,y_c-y_j) \cdot (x_c - x_j,y_c -y_j)}+r_j)$
We now have a circle $C(x_c,y_c,r_c)$ enclosing the other circles. This is not the optimal circle but the algorithm to find it is linearly bounded, $o(n)$.
Approximation involving the smallest enclosing rectangle for the circles
This is a basic approach that finds the enclosing rectangle defined by its boundaries. We obtain $Rect(x_{min}, x_{max}, y_{min}, y_{max})$ that defines the boundaries of an axis oriented rectangle. Where:
$x_{min} = min( \:x_j - r_j)$
$x_{max} = max( \:x_j + r_j)$
$y_{min} = min( \:y_j - r_j)$
$y_{max} = max( \:y_j + r_j)$
Now the center of our enclosing circle is $(x_c,y_c ) = ((x_{min}+ x_{max})/2\:, (y_{min} + y_{max})/2)$
We obtain the radius as before:
$r_c = max (\sqrt{(x_c - x_j,y_c-y_j) \cdot (x_c - x_j,y_c -y_j)}+r_j)$
We now have a circle $C(x_c,y_c,r_c)$ enclosing the other circles. This is not the optimal circle but the algorithm to find it is linearly bounded, $o(n)$. Its a start I hope someone posts an exact solution. Its an interesting problem.
Best Answer
There is only one such circle for a rectangle. If your rectangle has sidelengths $a$ and $b$, then the length of the diagonal (by the Pythagorean theorem) is $\sqrt{a^2+b^2}$. Since the diagonal is a diameter, the radius is just $\dfrac{\sqrt{a^2+b^2}}{2}$.