Calculating an Even Width For a Line Strip

The operation goes by several names: expanding, dilating, inflating, etc. Basically, given a series of ordered points, how do we calculate a path that’s the line strip, but with an even width?

A caveat, this is not going to be an optimized solution, but given the basic intuition I hope to bring, and the resulting code, it can be simplified and optimized. There’s going to be very little math notation, and we’re going to try to tackle this on an intuition basis with diagrams. I’m going to assume you already know about line segments and some vector math.

Generate Perpendicular 2D Lines

The first thing we need to cover is taking a vector and rotating it 90 degrees. While we could set up a rotation coordinate frame and then apply it to the vector, or perform a 3D cross-product with these 2D vectors, there’s a shortcut for rotating these things 90 degrees in 2D.

With the picture above, given a vector of (5,1), it’s easy to notice that:

• rotating the vector 90 degrees counter-clockwise is just (-y,x) of the vector,
• and rotating the vector 90 degrees clockwise is (y,-x).

That’s nothing special with this vector; it works for any 2D vector. Note that this depends on your coordinate frame. Sometimes, especially in computer graphics, the +Y axis may point down, or the -Y may point up, in which case, reverse the swapping formulas.
… in which case, swap the swapping.

This will give a perpendicular vector of the same length, but it’s easy to see that if we normalize it and then scale it by a specific value, we can control how long the perpendicular vector is.

In the illustration above, we can see where the endcaps could be if we added the perpendicular vector from itself to the next. Obviously, there’s no additional point for the endpoint on the right, so we take the vector from its previous neighbor to the end. Cyan is counter-clockwise, purple is clockwise.

We can see that if we took this rotated vector, normalized and scaled it by a certain value, that value would end up being the width. So a naive idea would be to do that for every point and connect them to create an outline.

It’s safe to say the naive implementation doesn’t give ideal results.

Averaged Corner Angles (Half Angles)

Something we should note is that for every point, there are two perpendicular vectors on each side, the one we’ve been showing and another one if we traveled the reverse direction across the points on the line strip.

We don’t care about the vector widths that created these perpendicular vectors, so we’ll assume they’re normalized. Now, if we add them up, we get the angle in between. Note the top and the bottom are opposite of each other, so we only need to calculate one and negate it if we need the other side’s vector.

Note this vector cuts the angle at the point in half. Also, notice how if we offset the vector outwards by a specific amount on both sides, they intersect at this point.

In the illustration above, additional rays are offset on the top and bottom, all 4 by an equal perpendicular distance from their original vector. This is pretty much the ideal final result we want. And something we notice is that they intersect the half-angle vector. So now the question is, “how much do I need to extend outwards on the half-angle vector for a uniform width?”

The naive answer would be “a uniform amount for each point.”

Wow, look at that last illustration with the inflated line strip. We’re SO close! But if you look carefully, you’ll see it’s not an even thickness anywhere, especially at that second to the last point. But again, we’re SOoOooooOoooo close!

Angle Based Inflation

The problem is we need different ratios of length for each angle of a point. The tighter the angle, the longer we need to extend outward. If the point represents a flat connection, we just need a unit length. But if we imagine trying to find the collision point of offset rays, the more parallel the rays become, the more we need to move outwards (see illustration below).

Also note that for perfectly parallel rays, this requires extending out towards infinity. And for near-parallel rays, you’re still going to extend out quite a ways.
You actually wouldn’t be able to calculate this for parallel rays (0 degrees), the way we calculate half angles would return a zero vector.

Here’s a list of various angles and how they intersect. After looking at the image, before continuing, guess how we solve the distance along the half-angle that we need.

To find the answer, we lean on the dot product, a simple vector multiplication operation that’s a staple of linear algebra. If you’re not familiar with the dot product, here are the important things to know – these bullet points below (except for the last) are going to assume the vectors being dot-producted together are unit length (i.e., they have a length (a.k.a, magnitude) of 1 – a.k.a, they’re normalized):

• A dot product takes in two vectors and returns a single scalar (a.k.a., a normal number, i.e., not a vector).
• A dot product will return the cosine of the angle between the two vectors.
• If the vectors being dot produced are parallel, it will return 1.0. If they’re parallel but in opposite direction, -1.0.
• If the vectors being dot produced are perpendicular, it will return 0.0.
• The more perpendicular the vectors are, the smaller the return value. The closer to being parallel the vectors are, the larger the absolute value will be, with the maximum absolute value being 1.0.
• If the vectors aren’t normalized, the return value is scaled by the magnitude of both vectors. This is also true for it when they are normalized, but if that’s the case, it’s the equivalent of multiplying the scalar by 1.0, twice, which does nothing.

While I’ve spoiled that we’re using the dot product, we still need to find a use for it that has these properties:

• An approaching zero angle has a limit of an infinite distance along the half-angle vector.
• If we have no curvature and have an angle of 180, where both vectors are parallel, we need a value of 1.0.

To get the value with those properties, we take the dot product of the perpendicular angle (the angle from either direction will do) and the half-angle vector. This will give us a value that’s 1.0 for straight-line connections but tends to 0 as the vectors get more parallel in the opposite directions. Then we get the inverse of that calculation.

Order of Operations

Something to mention is that if you’re going to write back the inflated values where you’re processing the original data, you need to calculate all the inflation offsets first before you apply them – or else you’ll find yourself writing values you’ll eventually be reading for future points (crawling feedback).

Example

Example code and obligatory interactive sample. The source for the Unity sample can be downloaded from its GitHub repo.

Some excerpts, here’s the perpendicular vector generation. Nothing too surprising.

public static Vector2 PerpCCW(Vector2 v) => new Vector2(-v.y, v.x);
public static Vector2 PerpCW(Vector2 v) => new Vector2(v.y, -v.x);

And the code to calculate the inflation amount for each vert at unit length. For any desired thickness, just multiply a point’s inflation amount by that thickness – it’s linear.

/// <summary>
/// Get the amount we need to extend per unit width.
/// </summary>
/// <param name="vecs">The line strip to process.</param>
/// <returns>
/// A 1-1 mapping of vectors for how much to move to inflate the vector
/// 1 unit.</returns>
public static List<Vector2> GetInflationVectors(List<Vector2> vecs)
{ 
    List<Vector2> ret = new List<Vector2>();

    ret.Add( PerpCCW((vecs[1] - vecs[0]).normalized));

    for(int i = 1; i < vecs.Count - 1; ++i)
    { 
        Vector2 toPt = PerpCCW((vecs[i] - vecs[i-1]).normalized);
        Vector2 frPt = PerpCW((vecs[i] - vecs[i+1]).normalized);
        Vector2 half = (toPt + frPt).normalized;
        float dot = Vector2.Dot(toPt, half);
        ret.Add((1.0f / dot) * half);
    }

    ret.Add(PerpCCW((vecs[vecs.Count - 1] - vecs[vecs.Count - 2]).normalized));
    return ret;
}

Degenerate Cases

The biggest degenerate case is the large distances we extend the shape for small angles. Many vector standards and drawing packages allow clamping the distance that this extension is allowed, sometimes rounding it out at a certain point, or flatting it with a straight line that cuts through.
For an example with clamping in SVGs, see this page on stroke miter limits.

One option is to modify the shape slightly to have less sharp angles by distributing it. If you’re inflating a flattened (Bezier) curve, there’s an advantage that it naturally distributes sharp angles over multiple points and angles.

Another issue involves large inflation widths and thin line strip segments with sharp angles. There’s also a risk that verts will be pushed into the inflation volume with a wider width. Or even worse, concave regions will turn inside out.

– Stay strong, code on. William Leu