Skip to content

Instantly share code, notes, and snippets.

@Phryxia
Created August 13, 2023 11:32
Show Gist options
  • Save Phryxia/04d74734cc45e73d3c10b35c1a3677e6 to your computer and use it in GitHub Desktop.
Save Phryxia/04d74734cc45e73d3c10b35c1a3677e6 to your computer and use it in GitHub Desktop.
TypeScript implementation of circumcircle finder
import { Vector2 } from 'three';
export function findCircumCircle(vertices: Vector2[]) {
if (vertices.length === 1) {
return [vertices[0], 0];
}
if (vertices.length === 2) {
return [
vertices[0].clone().add(vertices[1]).multiplyScalar(0.5),
vertices[0].distanceTo(vertices[1]) * 0.5,
];
}
if (vertices.length !== 3) {
console.warn(
`Unexpected number of vertices ${vertices.length}, expect 3`,
);
}
// handle degeneracy
if (isStrictlyEqual(vertices[0], vertices[1])) {
return findCircumCircle([vertices[0], vertices[2]]);
}
if (isStrictlyEqual(vertices[0], vertices[2])) {
return findCircumCircle([vertices[0], vertices[1]]);
}
if (isStrictlyEqual(vertices[1], vertices[2])) {
return findCircumCircle([vertices[0], vertices[1]]);
}
const x0 = vertices[0].x;
const x1 = vertices[1].x;
const x2 = vertices[2].x;
const y0 = vertices[0].y;
const y1 = vertices[1].y;
const y2 = vertices[2].y;
const s0 = x0 ** 2 + y0 ** 2;
const s1 = x1 ** 2 + y1 ** 2;
const s2 = x2 ** 2 + y2 ** 2;
// https://en.wikipedia.org/wiki/Circumcircle#Circumcenter_coordinates
const d = 2 * (x0 * (y1 - y2) + x1 * (y2 - y0) + x2 * (y0 - y1));
const xc = (s0 * (y1 - y2) + s1 * (y2 - y0) + s2 * (y0 - y1)) / d;
const yc = (s0 * (x2 - x1) + s1 * (x0 - x2) + s2 * (x1 - x0)) / d;
const r = ((xc - x0) ** 2 + (yc - y0) ** 2) ** 0.5;
return [new Vector2(xc, yc), r];
}
export function isStrictlyEqual(v1: Vector2, v2: Vector2) {
return v1.x === v2.x && v1.y === v2.y;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment