A huge shoutout to Ian Mackenzie who actually implemented all of this

Evenly spaced things

The main feature that arc length parameterization gives is the ability to evenly space things along an arbitrary curve.

For instance, we might have a radial chart like this one, and want to know the positions for the labels (assuming they are anchored in the center). The math is not hard, but I really like this better than a bunch of cos and sin

module Main exposing (main)

import OpenSolid.Arc2d
import OpenSolid.Point2d as Point2d
import Segment
import SubPath


arc =
    OpenSolid.Arc2d.with
        { centerPoint = Point2d.fromCoordinates ( 0, 0 )
        , startPoint = Point2d.fromCoordinates ( 1, 0 )
        , sweptAngle = 2 * pi
        }


parameterized =
    let
        error =
            1.0e-6
    in
    arc
        |> Segment.arc
        |> List.singleton
        |> SubPath.arcLengthParameterized error

labelPositions = 
    SubPath.evenlySpacedPoints 12 parameterized

Note: be very careful with the error value and the scale of your curves.

The error is the maximal difference between the true answer and the given answer. So when the arcLength function returns 10 and the arcLengthParameterized was called with error 0.1 the true value of the arc length is between 9.9 and 10.1.

Calculating the arc length parameterization of a long curve with a very small error can take a very long time.

Animation

With the evenly spaced points along a curve, we can create animations by adding an offset.

Manipulating stroke geometry

• dashes in the geometry Using the stroke-dasharray property is probably faster, but maybe you want to manipulate the geometry after it’s been dashed

• adding markers (like triangles pointing in the direction of the curve) at arbitrary positions along the curve normal svg only allows one shape to be put on all intermediate points.

How it works

A brief overview of how the arc length parameterization is calculated.

The arc length parameterization of a line is simple. Given the start and end points, say (0, 0) and (5, 5), it only takes some basic math to find the total length, or to find the center point. The arc length parameterization for (segments of) a circle is similarly well-defined.

But more complex curves - like ellipses and bezier curves - don’t have easy exact solutions. in math-speak: there is no simple closed-form solution. Finding the closed-form solution is complicated and computationally expensive. So as true computer scientists, we cheat and approximate the solution. We can do this by reducing our curve to a collection of straight line segments, and then perform the arc length based calculations on this set of simple lines.

The segment type has four primitives

• line
• elliptical arc segment
• quadratic bezier curve
• cubic bezier curve

Line is easy, the rest needs to be approximated by straight lines. The basic idea is to evaluate the curve at enough points. when evaluated at just 2 points (start and end) the error (difference between the found answer and the truth) is very high.

When evaluating at 3 points - start, middle, end - the error is smaller. Keep adding points, and the error will keep decreasing. Using the second derivative of the curve, it is possible to calculate how many points are needed to get below some error value.

These calculations are quite expensive, so they are cached in a segment tree:

type SegmentTree
    = Node
        { lengthAtStart : Float
        , lengthAtEnd : Float
        , paramAtStart : Float
        , leftBranch : SegmentTree
        , rightBranch : SegmentTree
        }
    | Leaf
        { length0 : Float
        , length1 : Float
        , param0 : Float
        , param1 : Float
        }

The actual implementation has 8 instead of 2 segments per leaf for performance reasons

The Leaf is a straight line segment, where for the start and the end point we store the length so far, and the parameter values. The Node keeps some information to make binary search easy, and two branches.

With the SegmentTree data structure, it is very easy to write functions like

• arcLength : SegmentTree -> Float
• at : Float -> SegmentTree -> Maybe (Float, Float).