StreamingLineSimplifier

A streaming line simplification algorithm for .NET that processes points one at a time with O(1) time per point. Unlike batch algorithms like Douglas-Peucker, this works in real-time as points arrive.

Use Cases

Drawing applications with pen/touch input
GPS tracking and route simplification
Real-time data visualization
Any scenario where points arrive incrementally

How It Works

The algorithm uses an angular tolerance cone to decide which points to keep and which to skip.

Core Idea

Given a tolerance (maximum allowed perpendicular distance from the simplified line), the algorithm maintains:

An anchor point - the last emitted vertex
An angular cone - the range of valid directions for the next segment
A minimum distance constraint - prevents the line from doubling back

For each incoming point beyond the tolerance radius, the algorithm computes how much the line could deviate if it continued through that point. This deviation defines a cone of valid angles. As more points accumulate, the cone narrows (intersection of all individual cones). When a new point falls outside the cone, or when the line doubles back too far, the previous point is emitted as a vertex and the process restarts.

Angle Representation

Instead of working with angles in radians and trigonometric functions, the algorithm represents rotations as unit complex numbers stored in Vector2(cos, sin). This is the Rotation2 utility class.

Why this is cleaner than angle arithmetic:

Composing rotations is just complex multiplication (two multiplies, two adds) instead of atan2 + addition + cos/sin
Comparing angles uses the perpendicular dot product (a.X * b.Y - a.Y * b.X > 0 = "is b counterclockwise of a") instead of modular angle subtraction with wraparound handling
Inverse rotation is just conjugation (cos, -sin) instead of negating an angle
No wraparound discontinuities - the ±180 degree boundary that plagues angle-based code simply doesn't exist

The cone boundaries are maintained as unit vectors, and narrowing the cone is done by taking the max of the lower bounds and min of the upper bounds, all using perpendicular dot product comparisons.

Distance Constraint

Besides the angular cone, the algorithm tracks the farthest point seen from the anchor. If a new point is closer than (farthest - tolerance) to the anchor, it means the line has doubled back enough that the tolerance guarantee could be violated. This triggers an emit.

Comparison with Other Algorithms

Algorithm	Processing	Time Complexity	Streaming	Error Bound
StreamingLineSimplifier	One point at a time	O(1) per point	Yes	Guaranteed
Douglas-Peucker	Full line required	O(n log n)	No	Guaranteed
Visvalingam-Whyatt	Full line required	O(n log n)	No	Not guaranteed
Nth-point	One point at a time	O(1) per point	Yes	Not guaranteed
Radial distance	One point at a time	O(1) per point	Yes	Not guaranteed

The key advantage over Douglas-Peucker is that you don't need the complete polyline before simplifying. The key advantage over simpler streaming methods (nth-point, radial distance) is the guaranteed error bound - the simplified line is always within the tolerance distance of any skipped point.

Installation

Add a reference to the StreamingLineSimplifier project or copy the source files directly.

Usage

using System.Numerics;
using StreamingLineSimplifier;

// Create simplifier with 5-pixel tolerance
var simplifier = new StreamingLineSimplifier(tolerance: 5f);

// Process points as they arrive
foreach (var point in inputPoints)
{
    if (simplifier.TryAdd(point, out Vector2 emittedPoint))
    {
        // A simplified vertex was emitted
        outputPoints.Add(emittedPoint);
    }
}

// Don't forget to add the final point
outputPoints.Add(inputPoints.Last());

Batch Processing

public static List<Vector2> Simplify(IEnumerable<Vector2> points, float tolerance)
{
    var result = new List<Vector2>();
    var simplifier = new StreamingLineSimplifier(tolerance);
    Vector2 lastPoint = default;

    foreach (var point in points)
    {
        lastPoint = point;
        if (simplifier.TryAdd(point, out var emitted))
        {
            result.Add(emitted);
        }
    }

    // Add final point if different from last emitted
    if (result.Count == 0 || result[^1] != lastPoint)
    {
        result.Add(lastPoint);
    }

    return result;
}

Resetting for New Lines

// Reset to process a new line
simplifier.Reset();

API Reference