Skip to content

Instantly share code, notes, and snippets.

@mutoo
Last active November 17, 2022 15:54
Show Gist options
  • Star 6 You must be signed in to star a gist
  • Fork 2 You must be signed in to fork a gist
  • Save mutoo/5617691 to your computer and use it in GitHub Desktop.
Save mutoo/5617691 to your computer and use it in GitHub Desktop.
a very fast algorithm for getting the circumcircle from a triangle - http://www.exaflop.org/docs/cgafaq/cga1.html#Subject 1.04
function circumcircle(a, b, c) {
this.a = a
this.b = b
this.c = c
var A = b.x - a.x,
B = b.y - a.y,
C = c.x - a.x,
D = c.y - a.y,
E = A * (a.x + b.x) + B * (a.y + b.y),
F = C * (a.x + c.x) + D * (a.y + c.y),
G = 2 * (A * (c.y - b.y) - B * (c.x - b.x)),
minx, miny, dx, dy
/* If the points of the triangle are collinear, then just find the
* extremes and use the midpoint as the center of the circumcircle. */
if(Math.abs(G) < 0.000001) {
minx = Math.min(a.x, b.x, c.x)
miny = Math.min(a.y, b.y, c.y)
dx = (Math.max(a.x, b.x, c.x) - minx) * 0.5
dy = (Math.max(a.y, b.y, c.y) - miny) * 0.5
this.x = minx + dx
this.y = miny + dy
this.r = dx * dx + dy * dy
}
else {
this.x = (D*E - B*F) / G
this.y = (A*F - C*E) / G
dx = this.x - a.x
dy = this.y - a.y
this.r = dx * dx + dy * dy
}
}
@RNavega
Copy link

RNavega commented Feb 2, 2021

Depending on your circumstances you can do it with vectors. The intersection of at least two rays, each passing through the midpoint of a side of the triangle and perpendicular to that side, is the circumcenter. Proof seen here: https://flashman.neocities.org/Courses/Circumcenter.html

In this image below the (segments of) rays are M, N and P, each perpendicular to the side that they pass through the midpoint of:
CIRCUM2C
The circumcenter is O, equidistant to the 3 vertices. In some cases it can be outside of the triangle.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment