Skip to content

Instantly share code, notes, and snippets.

@hrb90

hrb90/arc_segment_intersection.js

Last active January 6, 2018 16:25
Show Gist options
  • Save hrb90/14c15362d598329aa65ebbc9810a1850 to your computer and use it in GitHub Desktop.
Save hrb90/14c15362d598329aa65ebbc9810a1850 to your computer and use it in GitHub Desktop.
Download ZIP
arc/segment intersection in javascript
Raw
arc_segment_intersection.js
// returns an array of real solutions to the quadratic ax^2 + bx + c = 0
const quadratic = (a, b, c) => {
if (a === 0) return [ -c/b ];
const discriminant = b*b - 4*a*c;
if (discriminant < 0) {
return [];
} else {
const y = - b / (2 * a);
const x = Math.sqrt(discriminant) / (2 * a);
return [y + x, y - x];
}
}
// checks if the arc centered at (x0, y0), with radius r and stretching from theta0 to theta1 radians,
// intersects the line segment from (x1, y1) to (x2, y2)
const checkIntersection = (x0, y0, r, theta0, theta1, x1, y1, x2, y2) => {
// Solve for t, u in [0, 1]:
// x1 + t(x2 - x1) = x0 + r cos(theta0 + u (theta1-theta0))
// y1 + t(y2 - y1) = y0 + r sin(theta0 + u (theta1-theta0))
// Moving x0 and y0 to the LHS, if we square both equations, the RHS will sum to r^2.
const bx = x1 - x0;
const by = y1 - y0;
const mx = x2 - x1;
const my = y2 - y1;
// Now (bx + mx * t)^2 + (by + my * t)^2 = r^2
// Expanding, bx^2 + by^2 - r^2 + t * (2 bx mx + 2 by my) + t^2 * (mx^2 + my^2) = 0
const a = mx * mx + my * my;
const b = 2 * bx * mx + 2 * by * my;
const c = bx * bx + by * by - r * r;
const ts = quadratic(a, b, c).filter(t => t >= 0 && t <= 1)
.filter(t => {
const angle = Math.acos((bx + t * mx) / r);
if (isNaN(angle)) return false;
const u = (angle - theta0) / (theta1 - theta0);
return (u >= 0 && u <= 1);
});
return ts.length > 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment