| 1 |
h1. *Piecewise* |
| 2 |
|
| 3 |
In order to represent functions with a complex shape, it is necessary |
| 4 |
to define functions in a piecewise manner. In the graphics world this |
| 5 |
sort of function, when parametric, is often referred to as a 'spline'. |
| 6 |
Even beyond the representation of paths, it is also often necessary |
| 7 |
for mathematical operations to return piecewise functions, as otherwise |
| 8 |
the single-fragment versions would require an inordinate degree to |
| 9 |
still be accurate. An example of this is the *inverse* function. |
| 10 |
|
| 11 |
In the world of lib2geom, this is implemented as the *Piecewise* |
| 12 |
template class. It manages a sequence of fragment 'segments' and the |
| 13 |
cuts between them. These cuts are the various t-values which separate |
| 14 |
the different segments. |
| 15 |
|
| 16 |
h2. Cuts |
| 17 |
|
| 18 |
The first and last cuts of a piecewise define it's intended range, and |
| 19 |
the intermediary cuts separate the segments. With indices, segment i |
| 20 |
is always bordered on the left with cut i and on the right with cut i+1. |
| 21 |
In general, c = s+1, where c is the number of cuts and s is the number |
| 22 |
of segments. These invariants are checked by the |
| 23 |
@bool Piecewise<T>::invariants();@ method. |
| 24 |
|
| 25 |
The cuts essentially define the position and scale of each segment. |
| 26 |
For example, if the left and right cuts are 0.5 apart, the segment is |
| 27 |
half its regular size; the derivative will be twice as big. |
| 28 |
|
| 29 |
h4. Cut Query Functions |
| 30 |
|
| 31 |
<pre><code> |
| 32 |
unsigned Piecewise<T>::segN(double, int low = 0, int high = -1) const; |
| 33 |
double Piecewise<T>::segT(double, int = -1) const; |
| 34 |
double mapToDomain(double t, unsigned i) const; |
| 35 |
</code></pre> |
| 36 |
|
| 37 |
These functions use the cut information to ascertain which segment a |
| 38 |
t-value lies within ( *segN* ), and what the t-value is for that segment |
| 39 |
at that particular point ( *segT* ). *segN* takes two optional parameters |
| 40 |
which limit the range of the search, and are used internally as it is |
| 41 |
defined as a recursive binary search. These may be used if you are sure |
| 42 |
that the desired segment index lies within the range. *segT* takes an |
| 43 |
optional parameter for the case where you already know the segment number. |
| 44 |
|
| 45 |
mapToDomain is the inverse of segT, as it takes a t-value for a particular |
| 46 |
segment, and returns the global piecewise time for that point. |
| 47 |
|
| 48 |
h4. @ Interval Piecewise<T>::domain() const; @ |
| 49 |
|
| 50 |
The *domain* function returns the Interval of the intended domain of the |
| 51 |
function, from the first cut to the last cut. |
| 52 |
|
| 53 |
h4. Cut Modification Functions |
| 54 |
|
| 55 |
<pre><code> |
| 56 |
void Piecewise<T>::offsetDomain(double o) |
| 57 |
void Piecewise<T>::scaleDomain(double s) |
| 58 |
void Piecewise<T>::setDomain(Interval dom) |
| 59 |
</code></pre> |
| 60 |
|
| 61 |
These functions very simply transform the cuts with linear transformations. |
| 62 |
|
| 63 |
h3. Technical Details |
| 64 |
|
| 65 |
As the cuts are simply a public std::vector, they may also be accessed as |
| 66 |
@pw.cuts@. |
| 67 |
|
| 68 |
While the actual segments begin on the first cut and end on the last, |
| 69 |
the function is defined throughout all inputs by extending the first |
| 70 |
and last segments. The exact switching between segments is arbitrarily |
| 71 |
such that beginnings (t=0) have priority over endings (t=1). This only |
| 72 |
really matters if it is discontinuous at that location. |
| 73 |
|
| 74 |
In the context of 2d parametrically defined curves, the usefulness of cuts |
| 75 |
becomes less apparrent, as they make no real difference for the display |
| 76 |
of the curves. Rather, cuts become more of an agreement between various |
| 77 |
functions such that the proper data aligns. |
| 78 |
|
| 79 |
h2. Construction |
| 80 |
|
| 81 |
Most of the time there is no need for raw construction of *Piecewise* |
| 82 |
functions, as they are usually obtained from operations and other sources. |
| 83 |
|
| 84 |
The following constructors defined for *Piecewise*: |
| 85 |
* The blank constructor |
| 86 |
* A constructor which explicitly lifts a fragment to a *Piecewise* on [0,1] |
| 87 |
* A constructor which takes the *output_type*, and creates a constant function |
| 88 |
|
| 89 |
<pre><code> |
| 90 |
void Piecewise<T>::push_seg(T); |
| 91 |
void Piecewise<T>::push_cut(double); |
| 92 |
void Piecewise<T>::push(T, double); |
| 93 |
</code></pre> |
| 94 |
|
| 95 |
The usual method for raw construction is to construct a blank *Piecewise* |
| 96 |
function, and use these push methods to load the content. *push_seg* and |
| 97 |
*push_cut* simply add to the segment and cut lists, although *push_cut* |
| 98 |
also checks that the cut time is larger than the last cut. The current |
| 99 |
recommended method for calling these functions is to have one initial |
| 100 |
*push_cut*, followed by successive calls to *push*, as this will guarantee |
| 101 |
that the cuts and segments properly align. |
| 102 |
|
| 103 |
h2. Operations |
| 104 |
|
| 105 |
h3. Arithmetic |
| 106 |
|
| 107 |
*Piecewise* has many arithmetic operations, and implements |
| 108 |
*OffsetableConcept*, *ScalableConcept*, *AddableConcept*, and |
| 109 |
*MultiplicableConcept*. The operations which operate on two Piecewise |
| 110 |
functions (Addable and Multiplicable) work by interleaving the cuts using |
| 111 |
mutual *partition* calls, and iterating the resulting segments. |
| 112 |
|
| 113 |
h3. Fragment Wrapping |
| 114 |
|
| 115 |
While *Piecewise* is not a fragment (it does not have the [0,1] domain), |
| 116 |
it has many functions reminiscient of *FragmentConcept*, including the |
| 117 |
bounds functions, () and valueAt. |
| 118 |
|
| 119 |
(TODO: reverse function?) |
| 120 |
|
| 121 |
h3. Concatenation |
| 122 |
|
| 123 |
<pre><code> |
| 124 |
void Piecewise<T>::concat(const Piecewise<T> &other); |
| 125 |
void Piecewise<T>::continuousConcat(const Piecewise<T> &other); |
| 126 |
</code></pre> |
| 127 |
|
| 128 |
These functions efficiently append another *Piecewise* to the end of a |
| 129 |
*Piecewise*. They offset the _other_ *Piecewise* in time such that it is |
| 130 |
flush with the end of this *Piecewise*. *continuousConcat* is basically |
| 131 |
the same except that it also offsets in space so the functions also match |
| 132 |
in value. |
| 133 |
|
| 134 |
(TODO: compose/derivative/integral) |