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;}`