Skip to content

Instantly share code, notes, and snippets.

@herzig
Last active February 6, 2021 23:24
Show Gist options
  • Save herzig/cc5833f6b4b4c0ac1e314bb16cb94dc3 to your computer and use it in GitHub Desktop.
Save herzig/cc5833f6b4b4c0ac1e314bb16cb94dc3 to your computer and use it in GitHub Desktop.
3D circle-circle intersection in Javascript. Intersection of two circles that share the same plane (in 3D). Convenient use with three.js vectors
function IntersectTHREE() {};
// intersection of two 3d circles
// c1,n1,c2,n2 are the center points and normal directions as 3d vectors (ex: {x: 1, y: 2, z: 3} )
IntersectTHREE.circleCircle = function(c1, n1, r1, c2, n2, r2)
{
let r = Intersect.circleCircle(
c1.x, c1.y, c1.z, n1.x, n1.y, n1.z, r1,
c2.x, c2.y, c2.z, n2.x, n2.y, n2.z, r2);
return r;
}
function Intersect() {};
// intersection of two 3d circles that lie in the same plane.
// x1,y1,z1: center point of circle 1
// nx,ny,nz: normal of circle 1 (axis)
// r1: radius 1
//
// returns an object { coincident: true [if the circles are identical], points: [isect0, isect1] }
//
// basic algorithm from: http://stackoverflow.com/questions/35748840/circle-circle-intersection-in-3d#35751516
//
Intersect.circleCircle = function(x1, y1, z1, nx1, ny1, nz1, r1, x2, y2, z2, nx2, ny2, nz2, r2)
{
let eps = 1e-5;
// sum of components of n1 x n2;
para = ny2*nz1-nz2*ny1 + nz2*nx1-nx2*nz1 + nx2*ny1-ny2*nx1;
if (Math.abs(para) > eps)
{
// TODO: non-parallel circle intersection
// if there are any intersections they are on a line width direction: n1 x n2 (intersection line of both planes)
return null;
}
let diffx, diffy, diffz;
diffx = x2-x1; diffy = y2-y1; diffz = z2-y1;
if (Math.abs(diffx * nx2 + diffy * ny2 + diffz * nz2) > eps)
{
// planes are parallel offset
return null;
}
let dist = Math.sqrt(diffx*diffx + diffy*diffy + diffz*diffz);
if (dist < eps && Math.abs(r1 - r2) < eps)
{
// circles are identical
return { coincident: true, points: null };
}
if (dist > (r1 + r2))
return null;
if (Math.abs(dist - (r1 + r2)) < eps)
{
// circles intersect in one point (tangent)
let p = [];
p[0] = (x1 * r2 + x2 * r1) / (r1+r2);
p[1] = (y1 * r2 + y2 * r1) / (r1+r2);
p[2] = (z1 * r2 + z2 * r1) / (r1+r2);
return {coincident: false, points: [p]};
}
if (dist < Math.abs(r2 - r1))
return null;
if (Math.abs(dist - (r2 - r1)) < eps)
{
// circles intersect in one point (tangent)
let p = [];
p[0] = (x1 - x2) * r2 / (r2 - r1);
p[0] = (y1 - y2) * r2 / (r2 - r1);
p[0] = (z1 - z2) * r2 / (r2 - r1);
return {coincident: false, points: [p]};
}
// circles intersect in two points
// find intersections using quadratic formula
//normalize diff
diffx /= dist; diffy /= dist; diffz /= dist;
let perpx, perpy, perpz;
perpx = diffy*nz1-diffz*ny1;
perpy = diffz*nx1-diffx*nz1;
perpz = diffx*ny1-diffy*nx1;
let q = dist*dist + r2*r2 - r1*r1;
let dx = 0.5 * q / dist;
let dy = 0.5 * Math.sqrt(4 * dist*dist * r2*r2 - q*q) / dist;
let p0 = [
x1 + diffx * dx + perpx * dy,
y1 + diffy * dx + perpy * dy,
z1 + diffz * dx + perpz * dy];
let p1 = [
x1 + diffx * dx - perpx * dy,
y1 + diffy * dx - perpy * dy,
z1 + diffz * dx - perpz * dy];
return {coincident: false, points: [p0, p1]};
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment