Skip to content

Points & Lines

Planar points are pairs \((x, y)\). Lines can be given as two points, or as coefficients \(ax + by + c = 0\). The cross product (2D as scalar \(z\) of the 3D cross) encodes orientation and area.

Cross product (2D)

For vectors \(\vec{pq} = (q_x - p_x, q_y - p_y)\) and \(\vec{pr}\):

\[ \text{cross}(pq, pr) = (q_x - p_x)(r_y - p_y) - (q_y - p_y)(r_x - p_x) \]

Sign: > 0 ⇒ \(r\) is to the left of directed line \(pq\) (counterclockwise); < 0 ⇒ right; 0 ⇒ collinear.

#include <algorithm>
struct Point { double x, y; };

double cross(const Point& p, const Point& q, const Point& r) {
    return (q.x - p.x) * (r.y - p.y) - (q.y - p.y) * (r.x - p.x);
}

int sgn(double v) {
    if (v > 1e-9) return 1;
    if (v < -1e-9) return -1;
    return 0;
}

Segment intersection

Segments \(ab\) and \(cd\) intersect (properly or at endpoints) if orientations interleave and bounding boxes overlap—standard case analysis or use cross products to test straddling.

bool onSegment(const Point& a, const Point& b, const Point& p) {
    return sgn(cross(a, b, p)) == 0 &&
           min(a.x, b.x) <= p.x && p.x <= max(a.x, b.x) &&
           min(a.y, b.y) <= p.y && p.y <= max(a.y, b.y);
}

bool segmentsIntersect(const Point& a, const Point& b, const Point& c, const Point& d) {
    int o1 = sgn(cross(a, b, c)), o2 = sgn(cross(a, b, d));
    int o3 = sgn(cross(c, d, a)), o4 = sgn(cross(c, d, b));
    if (o1 != o2 && o3 != o4) return true;
    if (o1 == 0 && onSegment(a, b, c)) return true;
    if (o2 == 0 && onSegment(a, b, d)) return true;
    if (o3 == 0 && onSegment(c, d, a)) return true;
    if (o4 == 0 && onSegment(c, d, b)) return true;
    return false;
}

Line–line intersection

If lines are not parallel, solve two linear equations; for parametric form \(p + t \vec{u}\), \(q + s\vec{v}\), solve for \(t, s\) via cross products.