Plotting graphs using Bezier curves

Question

I have an array of points (x0,y0)... (xn,yn) monotonic in x and wish to draw the "best" curve through these using Bezier curves. This curve should not be too "jaggy" (e.g. similar to joining the dots) and not too sinuous (and definitely not "go backwards"). I have created a prototype but wonder whether there is an objectively "best solution".

I need to find control points for all segments xi,y1 x(i+1)y(i+1). My current approach (except for the endpoints) for a segment x(i), x(i+1) is:

• find the vector x(i-1)...x(i+1) , normalize, and scale it by factor * len(i,i+1) to give the vector for the leading control point
• find the vector x(i+2)...x(i) , normalize, and scale it by factor * len(i,i+1) to give the vector for the trailing control point.

I have tried factor=0.1 (too jaggy), 0.33 (too curvy) and 0.20 - about right. But is there a better approach which (say) makes 2nd and 3nd derivatives as smooth as possible. (I assume such an algorithm is implemented in graphics packages)?

I can post pseudo/code if requested. Here are the three images (0.1/0.2/0.33). The control points are shown by straight lines: black (trailing) and red (leading)

Here's the current code. It's aimed at plotting Y against X (monotonic X) without close-ing. I have built my own library for creating SVG (preferred output); this code creates triples of x,y in coordArray for each curve segment (control1, xcontrol2, end). Start is assumed by last operation (Move or Curve). It's Java but should be easy to interpret (CurvePrimitive maps to cubic, "d" is the String representation of the complete path in SVG).

        List<SVGPathPrimitive> primitiveList = new ArrayList<SVGPathPrimitive>();
    primitiveList.add(new MovePrimitive(real2Array.get(0)));
    for(int i = 0; i < real2Array.size()-1; i++) {
        // create path 12
        Real2 p0 = (i == 0) ? null : real2Array.get(i-1);
        Real2 p1 = real2Array.get(i);
        Real2 p2 = real2Array.get(i+1);
        Real2 p3 = (i == real2Array.size()-2) ? null : real2Array.get(i+2);
        Real2Array coordArray = plotSegment(factor, p0, p1, p2, p3);
        SVGPathPrimitive primitive = new CurvePrimitive(coordArray);
        primitiveList.add(primitive);
    }
    String d = SVGPath.constructDString(primitiveList);
    SVGPath path1 = new SVGPath(d);
    svg.appendChild(path1);


/**
 * 
 * @param factor to scale control points by
 * @param p0 previous point (null at start)
 * @param p1 start of segment
 * @param p2 end of segment
 * @param p3 following point (null at end)
 * @return
 */
private Real2Array plotSegment(double factor, Real2 p0, Real2 p1, Real2 p2, Real2 p3) {
    // create p1-p2 curve
    double len12 = p1.getDistance(p2) * factor;
    Vector2 vStart = (p0 == null) ? new Vector2(p2.subtract(p1)) : new Vector2(p2.subtract(p0));
    vStart = new Vector2(vStart.getUnitVector().multiplyBy(len12));
    Vector2 vEnd = (p3 == null) ?  new Vector2(p2.subtract(p1)) : new Vector2(p3.subtract(p1));
    vEnd = new Vector2(vEnd.getUnitVector().multiplyBy(len12));
    Real2Array coordArray = new Real2Array();
    Real2 controlStart = p1.plus(vStart);
    coordArray.add(controlStart);
    Real2 controlEnd = p2.subtract(vEnd);
    coordArray.add(controlEnd);
    coordArray.add(p2);
    // plot controls
    SVGLine line12 = new SVGLine(p1, controlStart); 
    line12.setStroke("red");
    svg.appendChild(line12);
    SVGLine line21 = new SVGLine(p2, controlEnd); 
    svg.appendChild(line21);
    return coordArray;
}

Answer 1

A Bezier curve requires the data points, along with the slope and curvature at each point. In a graphics program, the slope is set by the slope of the control-line, and the curvature is visualized by the length.

When you don't have such control-lines input by the user, you need to estimate the gradient and curvature at each point. The wikipedia page http://en.wikipedia.org/wiki/Cubic_Hermite_spline, and in particular the 'interpolating a data set' section has a formula that takes these values directly.

Typically, estimating these values from points is done using a finite difference - so you use the values of the points on either side to help estimate. The only choice here is how to deal with the end points where there is only one adjacent point: you can set the curvature to zero, or if the curve is periodic you can 'wrap around' and use the value of the last point.

The wikipedia page I referenced also has other schemes, but most others introduce some other 'free parameter' that you will need to find a way of setting, so in the absence of more information to help you decide how to set other parameters, I'd go for the simple scheme and see if you like the results.

Let me know if the wikipedia article is not clear enough, and I'll knock up some code.

One other point to be aware of: what 'sort' of Bezier interpolation are you after? Most graphics programs do cubic bezier in 2 dimensions (ie you can draw a circle-like curve), but your sample images look like it could be 1d functions approximation (as in for every x there is only one y value). The graphics program type curve is not really mentioned on the page I referenced. The maths involved for converting estimate of slope and curvature into a control vector of the form illustrated on http://en.wikipedia.org/wiki/B%C3%A9zier_curve (Cubic Bezier) would take some working out, but the idea is similar.

Below is a picture and algorithm for a possible scheme, assuming your only input is the three points P1, P2, P3

Construct a line (C1,P1,C2) such that the angles (P3,P1,C1) and (P2,P1,C2) are equal. In a similar fashion construct the other dark-grey lines. The intersections of these dark-grey lines (marked C1, C2 and C3) become the control-points as in the same sense as the images on the Bezier Curve wikipedia site. So each red curve, such as (P3,P1), is a quadratic bezier curve defined by the points (P3, C1, P1). The construction of the red curve is the same as given on the wikipedia site.

However, I notice that the control-vector on the Bezier Curve wikipedia page doesn't seem to match the sort of control vector you are using, so you might have to figure out how to equate the two approaches.