Diagrams/Dev/Paths

Offset Paths.

The radius $r$ offset of a path is a path that is some fixed distance away on one side from the original path. We can consider this in two steps. First compute the offset of each segment. Second join these offsets. Depending on what particular path you want the second step could be to join or trim the segments. Trimming is much harder as it is possible that a whole segment's offset could be "trimmed" (think of an inside corner involving multiple segments) so we would need to consider more then just adjacent segments. Without trimming the path will always lie inside a trimmed path and the original curve (note that when stroking the non-trimmed path it is possible to have artifacts outside the trimmed path due to miter join of an acute angle).

An alternative definition could be based on the perimeter of the union of all circles of radius $r$ for each parameter value in the path. This has the benefit of never being self-intersecting, but can define complex paths (non-continuous). A certain kind of aggressive trimming can be equivalent to this definition.

Some preliminary code is here: https://gist.github.com/fryguybob/3969759.

Offsetting Segments.

Linear Segments.

Offsetting a Linear segment is simply a translation by a perpendicular vector of length $r$.

Arc Segments.

While at the time of writing this we do not have arc segments, it is useful to consider how they offset. Since arcs have a fixed radius of curvature they are already a constant distance $r_{1}$ from some center point. The offset is just the arc with the same start angle, end angle, and center, but with radius $r+r_{1}$.

Now consider an inside corner. We can think of this as an arc with radius $r_{1}<0$. if $r>|r_{1}|$ then our offset is in the opposite direction as the original and the center of the two arcs is between the two arcs. This might seem like the wrong thing but if you pick some parameter $t$ then the original arc and the offset arc will be exactly $r$ distance apart at that $t$.

This might be hard to follow without a picture, but if you consider that inside corner with a Linear segment $A$ leading in and $B$ leading out then the offset of the linear segments (given a big enough $r$) will cross each other. Now to get from the end of $A$ to the start of $B$ with an arc we start going in the direction "backward" along $A$, curve in the same direction (around the clock) as the arc, then end going "backward" along $B$. Note that this gives us a potentially undesirable cusp with maximal "sharpness", but it is the path that fits our definition. Trimming would remove this.

Cubic Segments.

Unlike the happy world of arcs we do not have a constant radius of curvature with Bézier curves. Lets first consider the most basic thing we could do. For the discussion we will use a fixed segment (absolute points) curve and name the points $a$, $b$, $c$, and $d$. We can get part of the way to the offset by getting the ends right. Note that at the start and end the curve is tangent to the lines $ab$ and $cd$ respectively. If we make our offset curve by offsetting $ab$ and $cd$ then we will have an offset that is correct at the ends. We will call this offset the $L$-offset.

This sets us up to do what we always do with Bézier curves, subdivide. First we produce the $L$-offset, then we check some $t$ values and see if we are close. We can check each $t$ by finding the point at that parameter then looking at the distance to the $L$-offset at that same $t$ value. If we are within some $\epsilon$ we use the $L$-offset. Otherwise we split in half and recurse. A version of this approach is here: https://gist.github.com/fryguybob/4945944 (this has been updated to include scaling based on curvature).

A few things to note. If we look at the length of the $L$-offset it is going to consistently undershoot when the radius of curvature is positive (counter-clockwise) and overshoot when negative (considering only original curves with curvatures with a constant sign). Other (single segment) offsets are only two degrees of freedom away from the $L$-offset. Specifically the lengths of the offset $ab$ and $cd$ (from here on called the handle lengths) are the only wiggle room we have.
Considering this we can see that while our subdivided $L$-offset will always give a curve within $\epsilon$ (ignoring a potential problem with the sampling) of the true offset, the first derivative will be rather noisy when compared to the offset. This is unfortunate as offsets could be quite useful for things like animations where it would be quite easy to perceive velocity oscillations.

One possible way to approximate how to set the handle lengths could be to use the fact that subdivision will eventually lead to monotonic segments (the radius of curvature has a constant sign, or the curve only bends one way), or a segment with an inflection point that is within $\epsilon$. It would probably be good to split on inflection points (in a single step at the beginning) anyway to get to these monotonic segments faster and more precisely. Once we are in this form we can treat the segment like we did the arc by producing the $L$-offset, then scaling the handle lengths by the ratio of the radius of curvature and that value plus $r$. We will call this the $A$-offset (this is now what is implemented in https://gist.github.com/fryguybob/4945944).

Remaining Issues.

We can construct cases much like the example given with two linear segments and an arc in-between with a single Cubic segment. For the right $r$ value we would then get two cusps in the true offset. This alone shows that the offset cannot be described exactly with a single segment.

The order of the true offset should determine how many samples we need to test to know if the whole curve is within $\epsilon$. This analysis remains to be done.

There is an opposite corner case where the segment starts with a cusp. If we first split the curve on the cusp we now need to join the offsets back together. Interestingly enough, if we don't split the cusp we get an approximation of this with just subdivision but it isn't clear how robust this is. It will probably be better to assume that we might have a join in the middle of a segment. This is unfortunate as it would be nice in some cases to be able to produce both the offset and the original with the same subdivisions as this gives a nice correlation of $t$-values between the two curves. In this situation we could give the original with an added zero length segment to match the join.

It appears that we should be able to do all of this over the rational numbers. All we need are some functions for the first and second derivative (curvature is available in the branch: https://github.com/diagrams/diagrams-lib/pull/74).

Joining Segments.

When we have a corner between line segments there is no longer a single point that is distance $r$ from that curve and is a closest point but an arc of such points. If this was a marching band taking a corner this is like the outer marchers having to march quickly while the inner marcher comes to a stop. All that is needed to construct the join segment is the point of the corner from the original path and the end point of the first offset segment and the start point of the second.

Joins also give an opportunity for different geometry based on those three points. For example any common line join styles such as, miter, round (this is the $r$-offset curve), and bevel. There are other styles useful in pattern making such as mirrored and notched joins. Note that we can recover the tangent vectors as perpendiculars to the lines from the original to one of the ends so we do not need that additional information.

Trimming Segments.

I don't have much to say here. There could be other uses for trimming as it is finding the "nearest" intersection and throwing away part of the curve.

Higher Dimensions.

It is interesting to note that in three dimensions we can reuse our alternative definition but with a union of spheres instead of a circle.

Curve Fitting.

It would be very useful to have a collection of curve fitting techniques.

Path simplifying.

Sometimes is is easy to generate a large number of segments, but in the end we would like a simpler curve that may be difficult to obtain constructively in the first place. One approach to this is to use curve fitting to regenerate the curve.

Links.

• Bezier curve intersection