For version 0.7.0.
To top.  Up: User's guide index

Paths

A first introduction to paths was given in the tutorial. In this guide we'll explore some of the more powerful operations that can be performed on paths.
Sections:    Spline time and arc time    Sliders    Point references    Upsampling    Joining paths

Spline time and arc time

Before discussing path sliders in the next section, we must introduce the concepts of spline time and arc time. Recall that a path is a sequence of connected cubic splines, and that each spline segment can be parameterized by a scalar in the range 0 to 1.
First, a spline time is a real number used to refer to points on paths. The integer part refers to a spline segment, with zero being the first segment, while the fractional part refers to a point on that segment. Second, an arc time is a length used to refer to points on paths. The length is simply the arc length from the beginning of the path to the point being referred to.
Note that spline time makes no sense from a geometric point of view. To see this, note that any spline segment can be divided into several shorter spline segments, and that while this does not change the geometry of the path, it changes the interpretation of spline times along the path. On the other hand, spline time is very natural from a computer representation point of view. Therefore, all arc times are converted to spline times internally in Shapes, a procedure which relies on numeric integration.
While the numeric integration required to work with arc time may seem costly from a computational point of view, it is believed that working with features of geometry rather then representation is such an important tool that it is worth while the extra computation time. While this argument may not have been feasible in the times when MetaPost was designed, the computational power of personal computers has increased by huge amounts since then, and we think that computing arc lengths is a good use of this power. Hence, users are recommended to avoid thinking in terms of spline time unless working explicitly with the underlying path representation.
Use the function ..Shapes..Numeric..Math..abs to find the total length of a path, and ..Shapes..Geometry..duration to find the final spline time of a path. Note that the duration of a closed path is 1 more than that of the corresponding open path.

Sliders

A path slider, generally referred to as just slider, is a location on a particular path. It is the natural result of any operation that selects a point on a path, and gives access to local characteristics of the path such as tangent its direction and curvature. In Shapes, a sub-range of a path is constructed by connecting one slider at the beginning of the range with another slider at the end of the range.
There are two types of sliders, depending on whether their paths are contained in 2d or 3d, see §PathSlider and §PathSlider3D, for details.
As the name suggests, a slider can be used to move along the path. By adding §Float or §Length values to a slider, one obtains a new slider at the given distance from the original slider; §Float values move in terms of spline time, while §Length values move in terms of arc length.
The simplest operations that yield sliders on a path are either to access the fields begin or end, or to apply the path like a function to a §Float value to construct a slider with the given spline time. Similarly, if the path is applied to a §Length value, one obtains a slider at the given arc time.
The function ..Shapes..Layout..mspoint (read it as mediation-slide point) is a convenient way to specify the arc time relative to the arc length of the path itself.
The most often used field of a slider is its location in space. The name of this field is p. This along with other fields and slider use is shown in the next example. Note that there are additional fields in 3d, and that it is not obvious how to best extend the definitions from 2d to 3d.
Sliders
Angry
Sliders. Given a slider, other sliders can be specified relative to the first one, either in terms of distance or in terms of spline time. Then, there are many fields to access to get both geometric and representation-related information about the particular point along the path. The right part of the picture shows that the velocity field v varies along a circle, so this is an example of a non-geometric field.
Note that arrows indicating direction have been given an arbitrary length.
Source: show/hide — visit
stdout: show/hide

Point references

In this section, we shall describe the powerful ways of referring to points (one at a time) on paths. Although most of these methods are defined and implemented in terms of optimization and that this may seem expensive from a computational point of view, one should keep in mind that precise computation of curve lengths (arc times) can be rather expensive too. Hence, try to use the powerful abstractions presented here whenever you think they are the best match for your thinking, and resort only to less expensive alternatives when too lengthy computations are a fact.
As usual, we concentrate on the methods in 2d, and make at most minor comments regarding the 3d counterparts.
Let us begin with a concept which appears also in MetaPost, namely to find the first point on a path where the path has a certain direction. In one does not specify the direction, but maximize the function in an orthogonal direction. This avoids undefined results when the given direction is never attained, and generalizes immediately to 3d. The function that does the job is ..Shapes..Geometry..maximizer. Sometimes, one is only interested in a coarse maximization, looking only at the points where the path goes through a path point, in which case ..Shapes..Geometry..pathpoint_maximizer does the job. A third option is to maximize over all the control points of the path (the convex hull of which is known to contain the path). Note, though, that while ..Shapes..Geometry..maximizer and ..Shapes..Geometry..pathpoint_maximizer yield a §PathSlider, ..Shapes..Geometry..controlling_maximizer cannot do this but returns a §Coords since the maximizing point is not on the path in general.
Maximizers
Angry
Maximizing in the direction indicated by the arrow. Control points of the path are marked by connecting them with blue lines to the path point they belong to. The first maximizing point on the path is marked with a red spot, the first maximizing point through a path point is marked with a small circle, and the maximizing point among all the control points is marked with a cross.
Source: show/hide — visit
The next concept for point references is to minimize the distance to a given point. This is done using ..Shapes..Geometry..approximator, and analogous to the maximization suite, there is also a ..Shapes..Geometry..pathpoint_approximator. The next example gives an illustration in 2d, but the concept makes sense and is implemented also in 3d.
Point approximators
Angry
Minimizing the distance to the point marked with a cross. The first maximizing point on the path is marked with a red spot, and the first maximizing point through a path point is marked with a small circle.
Source: show/hide — visit
Another concept for point references is that of intersection points. This has only been implemented in 2d as the function ..Shapes..Geometry..intersection (where the intersection with another path can be found), since Shapes does not support the abstraction of a general surface in 3d. Note that there may be no intersection at all, in which case ..Shapes..Geometry..intersection will invoke an error handler, see the following example.
Path intersection
Angry
Finding the first point on the solid black path (direction indicated by the arrow) where it intersects with the dashed blue path (direction not important). The intersection is marked with a red spot, and an error handler is used to treat the case when there is no intersection.
Source: show/hide — visit
Finally, there is a generalization of intersection of paths which generalizes to 3d, and that is to find the point where the path is closest to the other path. Again, ..Shapes..Geometry..approximator is the interface — depending on argument types, it will dispatch to the appropriate path-to-point or path-to-path algorithm. Note that, in the absence of intersections, it is ill-conditioned to speak of order between equally closed points (since the distance cannot be computed exactly anyway). The first example shows basic use, the following example shows how ..Shapes..Geometry..approximator is used as an alternative to ..Shapes..Geometry..intersection.
Path approximator
Angry
Minimizing the distance to the dashed blue path. The closest point on the path is marked with a red spot. The corresponding point on the target path is found using path-to-point approximation, which is significantly cheaper, although it could be argued that this point should also be returned somehow from the path-to-path approximation.
Source: show/hide — visit
Path intersection by approximation
Angry
Using ..Shapes..Geometry..approximator as a robust alternative to ..Shapes..Geometry..intersection. Note that ..Shapes..Geometry..approximator will (just like ..Shapes..Geometry..intersection) give the first intersection when there are several, and that the result is well defined also when there is no intersection (no need to set up an error handler, compare with the path intersection example above).
Source: show/hide — visit
OK, that's pretty much all for now; more point references may be added in the future. However, it should be mentioned here that there is no built in support for evaluating the point references on anything smaller than the whole path. The last example in this section shows how this can be done manually.
Subpath intersection
Angry
Finding the first point on the solid black path (direction indicated by the arrow), between the two circles, where it intersects with the dashed blue path (direction not important). The intersection is marked with a red spot. Note that one must make use of arc length rather than spline time to relate the slider on the sub path to a slider on the whole path (which makes this a bit more expensive and inaccurate compared to what a built-in solution could offer).
Source: show/hide — visit

Upsampling

There are operations on paths that despite a seemingly simple abstraction turn out very complicated to implement to a reasonable degree of accuracy. The design choice of Shapes was not to provide lousy implementations of these abstractions, but to provide simpler operations that can be implemented accurately and that will allow users to make their own approximations of the difficult abstractions. Basically, this comes down to means for folding over the discrete spline points defining a path, and means for generating a sufficiently dense sampling of the path. Currently, there are only means for upsampling, that is, to generate a representation that uses more points to define the same geometric path. The opposite, downsampling may be added in the future, but right now it is not even clear how the operation should be defined abstractly (note that downsampling will require the original path to be approximated somehow).
In this section, we shall discuss the available methods for upsampling. One of the methods refers to the Bezier spline representation of the new path, while the other methods have geometric meanings.
Beginning with the method which is not geometric, we have ..Shapes..Geometry..upsample_balance, which will divide each spline in two, such that the velocity is continuous through the new sample point. This will imply that the the two interpolation points around the new sample point are at equal distance (and opposite), hence the balance part of the name. It turns out that the sample point will be at spline time 0.5, so the operation is very cheap. Use this method if you need speed more than good properties of the upsampled path.
The method ..Shapes..Geometry..upsample_inflections adds samples where there were inflections on the spline segments of the original path. The new path will only have spline segments without inflections, which can be a useful thing when reasoning about the path in terms of its spline segment representation.
The method ..Shapes..Geometry..upsample_bends may be the most useful method of them all. It begins sampling at inflections (see ..Shapes..Geometry..upsample_inflections), and then it makes sure that each spline segment bends at most some given angle. Since it is often the parts of a path where it bends most that are difficult to work with, this method often gives you samples where you need them most.
The last method, ..Shapes..Geometry..upsample_every, simply ensures that each spline segment is shorter than some given length. The idea is simple, but it is not clear to me when this is more useful than ..Shapes..Geometry..upsample_bends.
The example below show the various methods applied to a variety of paths.
Upsampling
Angry
Various ways of upsampling a path.
Source: show/hide — visit
We end this section with an example showing an application of upsampling. The seemingly simple abstraction is to compute a path, following a given path at a certain distance. Basically, one would like to be able to compute one of the boundaries of a stroke along the path, but it is easy to also imagine more interesting generalizations. The idea is easy as long as the path has a radius of curvature being larger than the distance between the original and the new path, but when it is not the situation gets much more involved, and it is for this reason the (very important) operation is not included in the kernel.
Sidepaths
Angry
Application of upsampling: Computing side paths. Note that much of the interesting source code for this example is located in the extension ..Shapes..Geometry / pathmapping.
Source: show/hide — visit

Joining paths

It is possible to join two paths to create a longer path (which can then be joined with a third path, and so on). This is done using the connection operator --, which will connect the end of the first path with the beginning of the second path. If these are not the ends one intends to join, one may have to reverse one of the paths, so that its beginning becomes its end, and vice versa. To reverse a path, use the function ..Shapes..Geometry..reverse. (At the time of writing, this is implemented by constructing a new path with everything reversed, but this may be changed with the help of a more efficient path representation in the future.)
When paths are joined using the connection operator --, one must be able to specify the interpolation points of the spline filling the gap from the first to the second path. Shapes does not provide an operation to attach an interpolation point on the outside of a path end, although this can be achieved using a technique to be described soon.
For paths being constructed by joining path points, this is straight forward; even if the interpolation points on the outside of the first and last path point on an (open) path have no meaning when the path is stroked, the interpolation points still exist and will be used when the path is joined with more path points or other paths.
However, when creating a path from a sub-range of another path, the basic operation of connecting two sliders will create a path without interpolation points on the outsides. To specify interpolation points on the outside of the new path, one may attach interpolation points to the sliders before connecting them. (By using this technique with the end point sliders of a path, one can thus attach or replace interpolation points on the outside end of a complete path.)
Yet another way to join paths is to merge the end of the first path with the beginning of the second path, see ..Shapes..Geometry..meetpaths for more details and an example.
Get Shapes at SourceForge.net. Fast, secure and Free Open Source software downloads