Vector Representation of Lines

Key concepts:

• Treat points as vectors to leverage vector addision for point translation.
• Represent lines using a point plus a direction vector, wich naturally handles vertical lines.

Consider two lines intersecting at point I. Line 1 is defined by point p₁ and direction vector v₁, while Line 2 uses point p₂ and direction vector v₂.

Representing I as a vector gives us I = p₁ + t·v₁, where the goal is to determine the scalar parameter t. The cross product method exploits the fact that vector I→p₂ is paralel to v₂, meaning their cross product equals zero.

First, recall cross product properties:

• Left distributive law: a × (b + c) = a × b + a × c
• Right distributive law: (a + b) × c = a × c + b × c
• Scalar multiplication: (λa) × b = λ(a × b) = a × (λb)

Deriving the parameter t:

$$(p_2 - I) \times v_2 = 0$$ $$(p_2 - (p_1 + t\cdot v_1)) \times v_2 = 0$$ $$(p_2 - p_1) \times v_2 - t(v_1 \times v_2) = 0$$ $$(p_2 - p_1) \times v_2 = t(v_1 \times v_2)$$ $$t = \frac{|(p_2 - p_1) \times v_2|}{|v_1 \times v_2|}$$

With t determined, the intersection coordinates follow directly from I = p₁ + t·v₁.

This approach of unifying points and vectors into a single representation underlies homogeneous coordinates in computer graphics.

Implementation

A simple 2D vector structure handles the calculations:

struct Vector2D
{
    double u, v;
    Vector2D() = default;
    Vector2D(double u, double v) : u(u), v(v) {}
    double squaredMag() const { return u * u + v * v; }
    double magnitude() const { return sqrt(squaredMag()); }
    Vector2D operator+(const Vector2D& other) const { return Vector2D(u + other.u, v + other.v); }
    Vector2D operator-(const Vector2D& other) const { return Vector2D(u - other.u, v - other.v); }
    Vector2D operator*(double scalar) const { return Vector2D(u * scalar, v * scalar); }
    Vector2D operator/(double scalar) const { return Vector2D(u / scalar, v / scalar); }
    Vector2D operator-() const { return Vector2D(-u, -v); }
};

double crossProductMagnitude(const Vector2D& a, const Vector2D& b) { return a.u * b.v - b.u * a.v; }

The intersection function is straightforward and handles all cases, including vertical lines:

Vector2D lineIntersection(const Vector2D& anchor1, const Vector2D& dir1, const Vector2D& anchor2, const Vector2D& dir2)
{
    double param = crossProductMagnitude(anchor2 - anchor1, dir2) / crossProductMagnitude(dir1, dir2);
    return anchor1 + dir1 * param;
}