approximate non-linear transformation of affine combination

Consider applying an arbitrary transformation f to an affine combination i=1nwixi of some points xi, with non-negative weights wi that sum to unity. Obviously, in general,


However, sometimes it is desirable to compute the image f(iwixi) as if f were a linear (or affine) transformation; the result is then hoped to be a good approximation to the true value. (See below for an application.)

Actually, it is possible to show that, provided that f is twice continuously differentiable, the approximation is good to first order, despite the absence of any derivatives of f in the formula. The domain and range of f may be any normed vector spacesPlanetmathPlanetmath.

First, we write:

f(iwixi) =f(iwi(xi-x1)+x1)

If h=maxixi-x1, then iwi(xi-x1)i|wi|h=h, and so the error term in the Taylor expansion can be simplified to O(h2).

Substituting another Taylor expansion


into the first, we obtain:

f(iwixi) =f(x1)+iwi(f(xi)-f(x1)+O(h2))+O(h2)

Furthermore, it is not hard to see, by accounting the error from the Taylor expansions more carefully, that we have the bound:


where M is the maximum, as ξ ranges inside the convex hullMathworldPlanetmath formed by the points xi, of the quantity f′′(ξ)=supu0f′′(ξ)(u,u)u2. Finally, the point x1 over which we performed Taylor expansions can be replaced by any other point xk, and so correspondingly h can be replaced by minkmaxixi-xk.

Application in computer graphics

The principle just derived is often applied in vector-based computer graphics when curved objects are drawn by cubic Bézier curves:


which are affine combinations of the control points xi. To compute and display a smooth transformation f of such curves, it may be too much work to compute f(γ(t)) repeatedly for many parameter values t. Provided γ is not too wavy, computing and displaying i=03wi(t)f(xi) is vastly more efficient, and may result in little or no visually perceptible difference.

As a concrete example, consider bending a straight line segment into a circle. Mathematically, we are mapping the intervalMathworldPlanetmath [0,2π] via t(rcost,rsint). If the interval is split into sub-segments, each considered as a cubic Bézier curve with its interior control points both set at the midpointMathworldPlanetmathPlanetmathPlanetmath of the line segmentMathworldPlanetmath, then a circle can be approximated by transforming these control points. The following diagram shows the approximation for 24 segments (three Bézier curves per 45 arc).

Figure 1: Circle drawn using approximate mapping of line segment
Title approximate non-linear transformation of affine combination
Canonical name ApproximateNonlinearTransformationOfAffineCombination
Date of creation 2013-03-22 16:50:35
Last modified on 2013-03-22 16:50:35
Owner stevecheng (10074)
Last modified by stevecheng (10074)
Numerical id 7
Author stevecheng (10074)
Entry type Example
Classification msc 41A58
Classification msc 51N20