Codesignal: circumcircle

Original Problem

For any given triangle, a circle can be circumscribed around it:




Given the three (x, y) coordinates of a triangle, find the (x, y)coordinates of the center of the circumscribed circle and its radius.

It is guaranteed that all tests have an integer solution.

Example

For

triangle = [[3,2],
 [1,4],
 [5,4]]

the output should be

circumcircle(triangle) = [3, 4, 2].

The circumscribed circle is centered at (3, 4) and has a radius of 2.

Input/Ouput

Solution

We get 3 points, \(A, B, C\) from which we construct a triangle. In order to find the circumcenter of the triangle, we need to find the point where the perpendicular bisector lines cross. The bisector points on the sides of the triangle can be found like this:

\[ \begin{array}{rl} M_1 &= \frac{1}{2}(B+C)\\ M_2 &= \frac{1}{2}(A+B)\\ M_3 &= \frac{1}{2}(A+C) \end{array} \]

Having a typical rotation-matrix \(R(90^\circ)\), we can rotate the sides of the triangle around the \(M\)-points and get the rotated points plus the line equations. For line one:

\[ \begin{array}{rl}B_{M_1} &= M_1 + R \cdot (B - M_1)\\C_{M_1} &= M_1 + R \cdot (C - M_1)\end{array}\] \[L1(s) = B_{M_1} + s(C_{M_1} - B_{M_1})\]

For line two:

\[ \begin{array}{rl} A_{M_2} &= M_2 + R \cdot (A - M_2)\\ B_{M_2} &= M_2 + R \cdot (B - M_2)\\ \end{array} \] \[ L2(s) = A_{M_2} + s(B_{M_2} - A_{M_2}) \]

For line three:

\[ \begin{array}{rl} A_{M_3} &= M_3 + R \cdot (A - M_3) \\ C_{M_3} &= M_3 + R \cdot (C - M_3)\\ \end{array} \] \[ L3(s) = A_{M_3} + s(C_{M_3} - A_{M_3}) \]

We now calculate the intersection point of two of these lines, since all three lines meet in the same point anyway. I devoted a small article to the derivation of line intersections, which we will use here. The circumcenter \(O\) can be calculated with

\[O=v_1 + s \cdot w_1\]

As a small reminder, the parameter \(s\) can be calculated like this:

\[\left(\begin{array}{c}s\\t\end{array}\right) = \left(\begin{array}{cc}w_1 & -w_2\end{array}\right)^{-1}\cdot\left(\begin{array}{c}v_2-v_1\end{array}\right)\]

The four remaining values are already present, but when simplified we get:

\[\begin{array}{rl}v_1 & = B_{M_1}\\& = M_1 + R \cdot (B - M_1)\\& = \frac{1}{2}(B+C) + R\cdot \frac{1}{2}(B-C)\\w_1 & = C_{M_1} - B_{M_1}\\& = M_1 + R \cdot (C - M_1) - (M_1 + R \cdot (B - M_1))\\& = R \cdot (C - B)\\v_2 & = A_{M_2}\\& = M_2 + R \cdot (A - M_2)\\& =\frac{1}{2} (A + B) + R \cdot \frac{1}{2} (A - B)\\w_2 & = B_{M_2} - A_{M_2}\\& = M_2 + R \cdot (B - M_2) - (M_2 + R \cdot (A - M_2))\\& = R \cdot (B - A)\end{array}\]

We now need to work on the intersection part. First the inverse expression:

\[\left(\begin{array}{cc}w_1 & -w_2\end{array}\right)^{-1} = \frac{1}{A_xB_y - A_yB_x - A_xC_y + A_yC_x + B_xC_y - B_yC_x} \left(\begin{array}{cc}A_x - B_x & A_y - B_y\\C_x - B_x & C_y - B_y\\\end{array}\right)\]

Now the second factor:

\[ \left(\begin{array}{c}v_2-v_1\end{array}\right) = \left(\begin{array}{c}A_x/2 - A_y/2 + B_y - C_x/2 - C_y/2\\A_x/2 + A_y/2 - B_x + C_x/2 - C_y/2\end{array}\right)\]

And finally, we can calculate the \(s\) parameter. Everything else from the expression can be ignored.

\[ \left(\begin{array}{c}s\\t\end{array}\right)=\frac{\left(\begin{array}{c}((A_y - B_y)((A_x + A_y + C_x - C_y)/2 - B_x)) - ((A_x - B_x)((A_y - A_x + C_x + C_y)/2 - B_y)) \\((B_x - C_x)((A_y - A_x + C_x + C_y)/2 - B_y)) - ((B_y - C_y)((A_x + A_y + C_x - C_y)/2 - B_x))\end{array}\right)}{A_xB_y - A_yB_x - A_xC_y + A_yC_x + B_xC_y - B_yC_x}\]

After finding possible pairs and simplifications, the final obfuscated solution looks like this:

circumcircle = t => {

    b = t[0]
    c = t[1]
    g = t[2]
    a = b[0]
    b = b[1]
    d = c[0]
    c = c[1]
    f = g[0]
    e = g[1]

    k = a * a + b * b
    l = d * d + c * c
    m = f * f + e * e
    o = c - e
    p = e - b
    q = b - c

    h = a * o + d * p + f * q
    g = k * o + l * p + m * q
    d = k * (f - d) + l * (a - f) + m * (d - a)

    h+= h
    g = g / h - a
    d = d / h - b

    return [g+a, d+b, Math.hypot(g, d)]
}

This code can be simplified even further:

circumcircle = t => {

    a = t[0][0]
    b = t[0][1]
    c = t[1][0] - a
    d = b - t[1][1]
    e = t[2][0] - a
    f = t[2][1] - b

    g = 2 * (c * f + e * d)
    o = c * c + d * d
    p = e * e + f * f
    h = (o * f + p * d) / g
    i = (p * c - o * e) / g

    return [h + a, i + b, Math.hypot(h, i) | 0]
 }

« Back to problem overview

All images are copyright to Codesignal