"""
threepointscircle.py -- V.1.0, Feb 11 2007, by leonardo maffi

Computes the center (x,y) and the radius of the circle passing through three given points.
"""

from math import sqrt

def circle_through_three_points((ax,ay), (bx,by), (cx,cy)):
    """circle_through_three_points((ax,ay), (bx,by), (cx,cy)): return the center
    (x,y) and the radius of the circle passing through three given points.
    Raises TypeError if the given points are collinear or almost collinear.

    Algorithm:
    Let the three given points be a, b, c.  Use _0 and _1 to represent
    x and y coordinates. The coordinates of the center p=(p_0,p_1) of
    the circle determined by a, b, and c are:

        A = b_0 - a_0
        B = b_1 - a_1
        C = c_0 - a_0
        D = c_1 - a_1

        E = A*(a_0 + b_0) + B*(a_1 + b_1)
        F = C*(a_0 + c_0) + D*(a_1 + c_1)

        G = 2.0*(A*(c_1 - b_1)-B*(c_0 - b_0))

        p_0 = (D*E - B*F) / G
        p_1 = (A*F - C*E) / G;

    If G is zero then the three points are collinear and no finite-radius
    circle through them exists.  Otherwise, the radius of the circle is:
        r^2 = (a_0 - p_0)^2 + (a_1 - p_1)^2

    Reference: "Computational Geometry in C",
      Joseph O'Rourke, Cambridge University Press 1994,
      ISBN 0-521-44592-2 Pbk, ISBN 0-521-44034-3 Hdbk
      Page 201, simplified by Jim Ward.
    """
    A = bx - ax
    B = by - ay
    C = cx - ax
    D = cy - ay
    E = A*(ax + bx) + B*(ay + by)
    F = C*(ax + cx) + D*(ay + cy)
    G = 2.0 * (A*(cy - by) - B*(cx - bx))
    if abs(G) < 1e-50:
        raise TypeError("circle_through_three_points: the 3 given vertices are collinear")

    # center of the circle
    cx = (D*E - B*F) / G
    cy = (A*F - C*E) / G

    ax_cx = (ax - cx)
    ay_cy = (ay - cy)
    r = sqrt(ax_cx * ax_cx  +  ay_cy * ay_cy)
    return (cx, cy), r


if __name__ == "__main__":
    print "Small circle_through_three_points demo:"
    from random import uniform
    import Tkinter as tk

    win = tk.Tk()
    size = 700
    varia = size / 8.0
    canv = tk.Canvas(win, height=size, width=size, background="white")
    canv.pack()

    for _ in xrange(10):
        posx, posy = uniform(varia, size-varia), uniform(varia, size-varia)
        v1, v2, v3 = [(posx+uniform(-varia, varia), posy+uniform(-varia, varia)) for _ in range(3)]
        try:
            (cx, cy), r = circle_through_three_points(v1, v2, v3)
        except TypeError:
            # v1, v2, v3 vertices are collinear
            pass
        else:
            cp1x, cp1y = cx-r, cy-r
            cp2x, cp2y = cx+r, cy+r
            # Plot computed circle
            canv.create_oval(cp1x, cp1y, cp2x, cp2y, fill="grey93", outline="grey51")
            # Plot triangle
            canv.create_polygon(v1[0],v1[1], v2[0],v2[1], v3[0],v3[1], outline="", fill="grey80")
            # Plot triangle vertices
            for vx, vy in v1, v2, v3:
                canv.create_oval(vx-1.5, vy-1.5, vx+1.5, vy+1.5, fill="red", outline="")
    win.mainloop()