Geometry Library in C# — Intersections

Saturday, April 4, 2026

In the previous articles, we built curves, NURBS, and composite curves. The next fundamental operation is intersection: given two curves, find where they cross.

What seems simple in theory hides real complexity in practice. Two curves can cross transversally, touch tangentially, partially overlap, or intersect at their endpoints. And polygon clipping algorithms (like Greiner-Hormann) need to distinguish all these cases to work correctly.

Two types of results

When two curves intersect, the result is either a point or an interval (an overlap):

Point intersection: the curves cross or touch at a point. This is the most common case.
Overlap: the curves coincide over an interval. For example, two collinear segments sharing a common portion.

The lazy computation principle

Most of the time, you only need the intersection point. The parameters on each curve, the classification (crossing, tangency, endpoint position) — all of this is only useful in specific algorithms.

Computing the parameter corresponding to an intersection point can be expensive, especially for NURBS where the parameterization must be inverted. The intersection type requires tangent and cross product calculations. Paying this cost systematically would be wasteful.

The solution is lazy computation with Lazy<T>: we store the bare minimum at construction time, and compute the rest on demand, only once.

The base interface

public interface IIntersectionResult2d
{
    ICurve2d Curve0 { get; }

    ICurve2d Curve1 { get; }
}

This is deliberately minimal: we only know which curves are involved. The two subtypes provide the details.

The point intersection

public interface IPointIntersectionResult2d : IIntersectionResult2d
{
    Point2d Point { get; }

    double Parameter0 { get; }

    double Parameter1 { get; }

    IntersectionType Type { get; }

    IntersectionPosition Position { get; }
}

Point is always available immediately — it's the information everyone asks for.
Parameter0 and Parameter1 are the intersection point's parameters on each curve. Computed on demand.
Type classifies the intersection:

public enum IntersectionType
{
    Transversal,
    Tangent
}

Position indicates whether the point falls on an endpoint:

[Flags]
public enum IntersectionPosition
{
    None        = 0b0000,
    Curve0Start = 0b0001,
    Curve0End   = 0b0010,
    Curve1Start = 0b0100,
    Curve1End   = 0b1000
}

It's a flag enum: an intersection can be both at the start of curve 0 and the end of curve 1 (Curve0Start | Curve1End).

Why position matters

The Greiner-Hormann polygon clipping algorithm needs to classify each intersection based on its position on the edges. By combining Position with the flags, we distinguish three cases:

Case	Condition	Meaning
X (crossing)	`Position == None`	Both curves cross in the middle
T	Only Curve0 or Curve1 flags are set	A vertex touches the interior of the other edge
V	Both a Curve0 flag and a Curve1 flag are set	Two vertices coincide

The algorithm can easily test these cases:

bool IsX => Position == IntersectionPosition.None;

bool IsT => Position != IntersectionPosition.None
          && (Position & (IntersectionPosition.Curve0Start | IntersectionPosition.Curve0End)) == 0
          || (Position & (IntersectionPosition.Curve1Start | IntersectionPosition.Curve1End)) == 0;

bool IsV => (Position & (IntersectionPosition.Curve0Start | IntersectionPosition.Curve0End)) != 0
          && (Position & (IntersectionPosition.Curve1Start | IntersectionPosition.Curve1End)) != 0;

The implementation with lazy computation

public sealed class PointIntersectionResult2d : IPointIntersectionResult2d
{
    readonly Lazy<double> _parameter0;
    readonly Lazy<double> _parameter1;
    readonly Lazy<IntersectionType> _type;
    readonly Lazy<IntersectionPosition> _position;

    public ICurve2d Curve0 { get; }

    public ICurve2d Curve1 { get; }

    public Point2d Point { get; }

    public double Parameter0 => _parameter0.Value;

    public double Parameter1 => _parameter1.Value;

    public IntersectionType Type => _type.Value;

    public IntersectionPosition Position => _position.Value;

    public PointIntersectionResult2d(ICurve2d curve0, ICurve2d curve1, Point2d point)
    {
        ArgumentNullException.ThrowIfNull(curve0);
        ArgumentNullException.ThrowIfNull(curve1);

        Curve0 = curve0;
        Curve1 = curve1;
        Point = point;

        _parameter0 = new Lazy<double>(() => curve0.GetParameterAtPoint(point));
        _parameter1 = new Lazy<double>(() => curve1.GetParameterAtPoint(point));

        _type = new Lazy<IntersectionType>(() => ComputeType());
        _position = new Lazy<IntersectionPosition>(() => ComputePosition());
    }

    IntersectionType ComputeType()
    {
        UnitVector2d tangent0 = Curve0.GetTangentAtParameter(Parameter0);
        UnitVector2d tangent1 = Curve1.GetTangentAtParameter(Parameter1);

        Vector2d t0 = tangent0;
        Vector2d t1 = tangent1;
        double crossProduct = t0.X * t1.Y - t0.Y * t1.X;

        return Math.Abs(crossProduct) < 1e-10
            ? IntersectionType.Tangent
            : IntersectionType.Transversal;
    }

    IntersectionPosition ComputePosition()
    {
        var position = IntersectionPosition.None;
        double tolerance = 1e-10;

        if (Curve0 is IBoundedCurve2d bounded0)
        {
            if (Point.IsAlmostEqualTo(bounded0.StartPoint, tolerance))
                position |= IntersectionPosition.Curve0Start;
            else if (Point.IsAlmostEqualTo(bounded0.EndPoint, tolerance))
                position |= IntersectionPosition.Curve0End;
        }

        if (Curve1 is IBoundedCurve2d bounded1)
        {
            if (Point.IsAlmostEqualTo(bounded1.StartPoint, tolerance))
                position |= IntersectionPosition.Curve1Start;
            else if (Point.IsAlmostEqualTo(bounded1.EndPoint, tolerance))
                position |= IntersectionPosition.Curve1End;
        }

        return position;
    }
}

The constructor only takes the bare minimum: the two curves and the point. Everything else is wrapped in Lazy<T>:

Accessing Point → no computation, always instant.
Accessing Parameter0 → computes GetParameterAtPoint once, then caches.
Accessing Type → computes tangents and cross product (requires parameters, which are themselves computed on demand).
Accessing Position → compares the point to bounded curves' endpoints.

Note the dependency chain: Type accesses Parameter0 and Parameter1, triggering their computation if not already done. Lazy<T> handles this cascade automatically.

The overlap

When two curves coincide over an interval, the result isn't a point but a piece of curve:

public interface IOverlapIntersectionResult2d : IIntersectionResult2d
{
    double StartParameter0 { get; }

    double EndParameter0 { get; }

    double StartParameter1 { get; }

    double EndParameter1 { get; }
}

The four parameters delimit the overlap interval on each curve. The common sub-curve can be extracted with GetSubCurve.

A dedicated intersection class

Where should intersection logic live? If LineSegment2d has an IntersectWith(Circle2d) method, should Circle2d also have IntersectWith(LineSegment2d)? With N curve types, the number of combinations explodes as N×(N+1)/2. And every new curve type forces changes to all existing classes.

Intersection is an operation between two objects — it belongs to neither. So we place it in a dedicated class, CurveIntersector2d, that centralizes all dispatch logic:

public static class CurveIntersector2d
{
    public static IReadOnlyList<IIntersectionResult2d> Intersect(
        ICurve2d curve0, ICurve2d curve1)
    {
        ArgumentNullException.ThrowIfNull(curve0);
        ArgumentNullException.ThrowIfNull(curve1);

        return (curve0, curve1) switch
        {
            (LineSegment2d segment0, LineSegment2d segment1)
                => IntersectSegments(segment0, segment1),

            (LineSegment2d segment, Circle2d circle)
                => IntersectSegmentCircle(segment, circle),

            (Circle2d circle, LineSegment2d segment)
                => IntersectSegmentCircle(segment, circle, swapped: true),

            // Other combinations...

            _ => IntersectGeneric(curve0, curve1)
        };
    }
}

Each type pair gets its own optimized algorithm (analytical for simple cases, numerical for NURBS). Adding a new curve type means adding branches in CurveIntersector2d, without touching existing curve classes.

The caller then filters results based on their needs:

IReadOnlyList<IIntersectionResult2d> results =
    CurveIntersector2d.Intersect(curve0, curve1);

// Common case: just the points
foreach (IPointIntersectionResult2d point in results.OfType<IPointIntersectionResult2d>())
    Console.WriteLine(point.Point);

// Greiner-Hormann algorithm: needs position
foreach (IPointIntersectionResult2d point in results.OfType<IPointIntersectionResult2d>())
{
    if (point.Position == IntersectionPosition.None)
        HandleCrossing(point);       // X
    else if (point.IsV())
        HandleVertexVertex(point);   // V
    else
        HandleVertexEdge(point);     // T
}

// Overlap detection
foreach (IOverlapIntersectionResult2d overlap in results.OfType<IOverlapIntersectionResult2d>())
    HandleOverlap(overlap);

The beauty of lazy computation is visible here: in the first case (just points), you pay no extra cost. In the second case (Greiner-Hormann), parameters and position are computed on demand.

A convenience method can also be added on curves, delegating to the intersector:

public sealed class LineSegment2d : IBoundedCurve2d
{
    public IReadOnlyList<IIntersectionResult2d> IntersectWith(ICurve2d other)
        => CurveIntersector2d.Intersect(this, other);
}

The caller can choose between CurveIntersector2d.Intersect(a, b) and a.IntersectWith(b), but the logic lives in one place only.

The fast API for hot loops

The rich API with Lazy<T> is ideal for occasional use. But in some scenarios — complex polygon clipping, real-time collision detection — you compute thousands of intersections in a loop. Each call allocates a list, PointIntersectionResult2d objects, Lazy<T> instances... The garbage collector eventually chokes.

For these cases, CurveIntersector2d exposes a second allocation-free API based on structs and Span<T>:

public readonly struct RawIntersection2d
{
    public Point2d Point { get; }

    public double Parameter0 { get; }

    public double Parameter1 { get; }

    public RawIntersection2d(Point2d point, double parameter0, double parameter1)
    {
        Point = point;
        Parameter0 = parameter0;
        Parameter1 = parameter1;
    }
}

The struct is minimalist: the point and both parameters, computed immediately. No Lazy<T>, no curve references, no classification — just raw data.

public static class CurveIntersector2d
{
    // Rich API (general use)
    public static IReadOnlyList<IIntersectionResult2d> Intersect(
        ICurve2d curve0, ICurve2d curve1) { /* ... */ }

    // Fast API (hot loops)
    public static int Intersect(
        LineSegment2d segment0, LineSegment2d segment1,
        Span<RawIntersection2d> buffer)
    {
        Vector2d d0 = segment0.EndPoint - segment0.StartPoint;
        Vector2d d1 = segment1.EndPoint - segment1.StartPoint;
        double crossProduct = d0.X * d1.Y - d0.Y * d1.X;

        if (Math.Abs(crossProduct) < 1e-10)
            return 0; // Parallel — no intersection point

        Vector2d startToStart = segment1.StartPoint - segment0.StartPoint;
        double t = (startToStart.X * d1.Y - startToStart.Y * d1.X) / crossProduct;
        double u = (startToStart.X * d0.Y - startToStart.Y * d0.X) / crossProduct;

        if (t >= 0 && t <= 1 && u >= 0 && u <= 1)
        {
            Point2d point = segment0.StartPoint + d0 * t;
            buffer[0] = new RawIntersection2d(point, t, u);
            return 1;
        }

        return 0;
    }
}

The method returns the number of intersections written to the buffer. The caller allocates the Span once (on the stack or in a reusable array):

Span<RawIntersection2d> buffer = stackalloc RawIntersection2d[2];

for (int i = 0; i < segments.Length; i++)
    for (int j = i + 1; j < segments.Length; j++)
    {
        int count = CurveIntersector2d.Intersect(segments[i], segments[j], buffer);

        for (int k = 0; k < count; k++)
            ProcessIntersection(buffer[k].Point);
    }

Zero allocations in the inner loop. Parameters are computed immediately because in a hot loop, you typically need them right away. The cost is negligible for segments (a simple division), and we avoid the Lazy<T> machinery entirely.

For a line and a circle (which can produce 0, 1, or 2 intersections), a buffer of size 2 is sufficient. For NURBS, a larger buffer may be needed — the theoretical maximum size depends on the curve degrees.

What's next

We've laid out the intersection result architecture and the two API levels. In the next article, we'll implement the first concrete algorithm: the intersection of two segments, with the complete equation setup and overlap handling.