http://orcid.org/0000-0002-3224-8858
by Paul Murrell
http://orcid.org/0000-0002-3224-8858
Wednesday 07 June 2017
This document
is licensed under a Creative
Commons Attribution 4.0 International License.
This document describes algorithms for generating line-end and line-join styles for lines that have a variable width. The algorithms are implemented in the 'vwline' package for R.
When drawing a line that has a noticable width, the style used to draw the ends of the line becomes significant. Graphics formats such as PDF (Adobe Systems Incorporated, 2006), SVG (Ferraiolo and ed., 2001), and PostScript (Adobe Systems Incorporated, 1999) offer three options for the line end style: "round", "butt", and "square". The following diagram shows a thick line drawn with each of these line endings in the R graphics system.
If the width of the line is allowed to vary along its length, the meaning of these standard line endings becomes more complex; for example, a "round" line ending is no longer a semi-circle and a "square" line ending becomes a trapezoid, as shown below.
Similarly, the corner style becomes significant when drawing a series of line segments with a noticeable width, with options usually including "round", "mitre", and "bevel".
Again, if the line width is allowed to vary, the meaning of these styles becomes more complex. For example, a "round" corner is unlikely to be satisfied by an simple circular arc.
This document considers a variety of scenarios for line ends and line joins and describes general algorithms that can cope coherently and consistently with a wide range of possibilities. The approach described here is implemented in the 'vwline' package (Murrell, 2017b, Murrell, 2017a)
The simplest scenario to consider is when the width of the line is allowed to vary identically on either side of the central line. In this case, for a "round" end, although the end is no longer a semi-circle, it makes sense to use an appropriate circular arc.
However, in the 'vwline' package for R, some functions allow us to specify a different width to the left and to the right of the central line. Some other functions allow us to specify the width at an angle other than perpendicular to the central line. Both of these scenarios mean that the left edge and the right edge can approach the end of the line at different angles, which means that a circular arc is no longer an appropriate line ending.
In order to accomodate these more complex scenarios, we must allow the line end shape to be more flexible than a circular arc. The solution adopted in 'vwline' is to draw a single cubic Bezier curve for the line ending. This curve is tuned so that it closely approximates a semicircle when the line edges are parallel (i.e., the line width is constant), but generalises to non-circular shapes.
The fundamental idea is to generate a cubic Bezier curve for the line ending and this requires 4 control points. The first and last control points are easy - they are the two ends of the left and right edges of the variable-width line.
The middle two control points for the Bezier curve are found by extending both the left and right edges, which ensures that the line ending connects smoothly with the edges (these extensions are represented by green line segments on the diagrams below). The amount to extend the edges is based on the "angle" of the line ending and the "radius" of the line ending.
The angle and radius of the line ending are determined by generating line segments perpendicular to the edges of the variable-width line and calculating the angle at which those line segments intersect and the distances from the edges to the point of intersection (this calculation is represented by the light green shaded regions on the diagrams below).
When the angle is between 0 and 90 degrees, and the edges approach the line ending symmetrically, we get a good approximation of a circular arc using the following formula (from Riškus, 2015):
radius*(4/(3*(1/cos(angle/2) + 1))
When the edges approach the line ending asymmetrically, the distances from the edges to the intersection are no longer equal and we take the smaller of the two.
If the edges of the variable-width line are parallel then the line ending has an angle of 180 degrees and the formula breaks down. In this case, we extend the edges by 2/3 of the line width (following Slinker, 2008).
This approach produces reasonable approximations to circular arcs for symmetric line endings and reasonable results for asymmetric line endings, as shown below. As the angle of the line ending becomes large, the result starts to diverge significantly from a circular arc, but this downside is an acceptable price for being able to handle asymmetric line endings (and it pays off even more when we get to "round" line joins later on).
The possibility of edges converging at the end of a line also introduces a new "mitre" line end style. This line ending is easy to generate by simply extending the edges of the line until they intersect (this is represented by the orange lines in the diagrams above).
A "square" end is easier to deal with, even in complex scenarios. We simply place a new line parallel to the line end at a distance equal to half of the width of the line at the line end (represented by the pink line on the diagrams above) and then intersect the line edges with this parallel line. One complication that we must deal with is the possibility that the edges intersect with each other before they intersect with the parallel line. Once detected, this can be handled easily by simply converting to the "mitre" solution. Conversely, a "mitre" end must be converted to a "square" end when the edges are parallel or diverging.
A "round" line join is handled similarly to a "round" line end, with a single cubic Bezier that approximates a circular arc when the edge angles either side of the corner are symmetric, but adapts to asymmetric situations as well.
The line join can become more complex than a line end because it is possible for a corner to "invert" if the line width is (dramatically) decreasing as it approaches from both sides (see the left image below). It is also possible for the corner to require an inflected curve if the width is increasing (dramatically) from one side and decreasing from the other (or vice versa; see the right image below).
The algorithm described for "round" line ends comfortably handles the case of an inverted join and the case of an inflected join is handled as a special case where we take the "radius" of the join to be half the distance between the ends of the edges.
Mitre line joins are much easier because they just require extending the edges until they intersect (see the left image below). A mitre-limit is used to avoid extremely large mitres by converting to a bevel ending. The only complication is the case where the line join involves an inflection. In this case, one edge will intersect the "end" of the other line segment before it intersects the other edge, which produces a "dog-leg" mitre join (see the right image below).
Bevel line joins are very simple, because they just require a straight line from one edge to the next and this can be achieved in all possible line-join scenarios.
Up to this point, we have only had to consider the "outside" of a line join (for a right-turn corner, this is the right side of the join; for a left-turn corner, this is the left side of the join). In most situations, on the "inside" of a corner, the edges that meet at the corner intersect each other, so we can simply use that intersection point as the inside of the join.
However, in the 'vwline' package, the
vwline function also allows the width to be constant
along a segment and step up instantly at a join. This does not create
any new problems for the outside of a join, but it does introduce
some problems for the inside of a join.
One problem is that the inside of a join can have the inflection issue, so we need to intersect an edge with the end of the previous or next segment of the line (see the left image below). The second problem is that it is possible for the inside of one segment of the line to extend beyond the outside of another segment (see the right image below).
A single algorithm that can accomodate the normal, simple case
and these less common ones, is to draw the inside join by a line segment
from the end of edge i
to the centre of the corner, then a line segment
from the centre of the corner
to the start of edge i+1 (see the left image below).
This will produce a loop in the boundary
of the variable-width line in many cases, but that is removed
by simplifying the boundary with polysimplify from
the 'polyclip' package (Johnson and Baddeley, 2017; see the right
image below).
A known problem with this approach is that it will produce "spikes" on the inside of a join when the width is increasing rapidly towards the join, as shown below. A more pleasing result would be to clip those spikes off, but to do so would produce inconsistent results for the unusual cases outlined above. One possibility would be to provide a parameter that allows the user to specify the behaviour of the algorithm for inside joins.
Drawing a series of straight line segments with variable widths creates complexities in the shapes of the line endings and line joins. This document describes some general algorithms that can cope with a wide range of scenarios for a variety of line end and line join styles.
These algorithms have been implemented in the 'vwline' package for R,
particularly in the vwline function from that package.
The examples and discussion in this document relate to 'vwline' version 0.1.
This document was generated within a Docker container (see Resources section below).
Murrell, P. (2017). Variable-Width Line Ends and Line Joins. Technical Report 2017-02, University of Auckland. [ bib ]
This document
is licensed under a Creative
Commons Attribution 4.0 International License.