← all categories

Segment Intersection 980f3679

Test whether segments (a,b) and (c,d) intersect (including touching at an endpoint or overlapping collinearly).

Time: O(1). tested

content/geometry/segment-intersection.h

int sgn(ld x) { return (x > 1e-9) - (x < -1e-9); }

bool onSegment(Point a, Point b, Point p) {  // p collinear with a,b already assumed by caller context
    return min(a.x,b.x) - 1e-9 <= p.x && p.x <= max(a.x,b.x) + 1e-9
        && min(a.y,b.y) - 1e-9 <= p.y && p.y <= max(a.y,b.y) + 1e-9;
}

bool segmentsIntersect(Point a, Point b, Point c, Point d) {
    int d1 = sgn(a.cross(b, c)), d2 = sgn(a.cross(b, d));
    int d3 = sgn(c.cross(d, a)), d4 = sgn(c.cross(d, b));
    if (d1 != d2 && d3 != d4) return true;
    if (d1 == 0 && onSegment(a, b, c)) return true;
    if (d2 == 0 && onSegment(a, b, d)) return true;
    if (d3 == 0 && onSegment(c, d, a)) return true;
    if (d4 == 0 && onSegment(c, d, b)) return true;
    return false;
}