Tuesday, November 17, 2009

Segment-Circle Intersection


This is a sample code which verifies whether a given Circle and Segment intersects or not.




/*
** Verifies the intersection of a segment and a circle
** The line segment is defined from points p1 to p2
** The circle is of radius r and centered at point c
** There are potentially two points of intersection given by
** p = p1 + mu1 (p2 - p1)
** p = p1 + mu2 (p2 - p1)
** mu1 and mu2 are updated via reference
** Return FALSE if the segment doesn't intersect the circle
*/
bool cross(POINT p1, POINT p2, CIRCLE p, double &mu1, double &mu2) {
double a, b, c, d;
POINT t;
t.x = p2.x - p1.x;
t.y = p2.y - p1.y;
a = sq(t.x) + sq(t.y);
b = 2.0 * (t.x * (p1.x - p.c.x) + t.y * (p1.y - p.c.y));
c = sq(p.c.x) + sq(p.c.y);
c += sq(p1.x) + sq(p1.y);
c -= 2.0 * (p.c.x * p1.x + p.c.y * p1.y);
c -= sq(p.r);
d = b * b - 4 * a * c;
if(fabs(a) < eps || d < -eps) {
mu1 = mu2 = 0.0;
return false;
}
mu1 = (-b + sqrt(d)) / (2.0 * a);
mu2 = (-b - sqrt(d)) / (2.0 * a);
return true;
}

No comments:

Post a Comment