convert bezier curve to polygonal chain?

Question

I want to split a bezier curve into a polygonal chain with n straight lines. The number of lines being dependent on a maximum allowed angle between 2 connecting lines. I'm looking for an algorithm to find the most optimal solution (ie to reduce as much as possible the number of straight lines).

I know how to split a bezier curve using Casteljau or Bernstein polynomals. I tried dividing the bezier into half calculate the angle between the straight lines, and split again if the angle between the connecting lines is within a certain threshold range, but i may run into shortcuts.

Is there a known algorithm or pseudo code available to do this conversion?

Answer 1

Use de Casteljau algorithm recursively until the control points are approximately collinear. See for instance http://www.antigrain.com/research/adaptive_bezier/index.html.

Answer 2

This was a fascinating topic. The only thing I'm adding is tested C# code, to perhaps save somebody the trouble. And I tried to write for clarity as opposed to speed, so it mostly follows the AGG web site's PDF doc (see above) on the Casteljau algorithm. The Notation follows the diagram in that PDF.

public class Bezier
{
    public PointF P1;   // Begin Point
    public PointF P2;   // Control Point
    public PointF P3;   // Control Point
    public PointF P4;   // End Point

    // Made these global so I could diagram the top solution
    public Line L12;
    public Line L23;
    public Line L34;

    public PointF P12;
    public PointF P23;
    public PointF P34;

    public Line L1223;
    public Line L2334;

    public PointF P123;
    public PointF P234;

    public Line L123234;
    public PointF P1234;

    public Bezier(PointF p1, PointF p2, PointF p3, PointF p4)
    {
        P1 = p1; P2 = p2; P3 = p3; P4 = p4;
    }

    /// <summary>
    /// Consider the classic Casteljau diagram
    /// with the bezier points p1, p2, p3, p4 and lines l12, l23, l34
    /// and their midpoint of line l12 being p12 ...
    /// and the line between p12 p23 being L1223
    /// and the midpoint of line L1223 being P1223 ...
    /// </summary>
    /// <param name="lines"></param>
    public void SplitBezier( List<Line> lines)
    {
        L12 = new Line(this.P1, this.P2);
        L23 = new Line(this.P2, this.P3);
        L34 = new Line(this.P3, this.P4);

        P12 = L12.MidPoint();
        P23 = L23.MidPoint();
        P34 = L34.MidPoint();

        L1223 = new Line(P12, P23);
        L2334 = new Line(P23, P34);

        P123 = L1223.MidPoint();
        P234 = L2334.MidPoint();

        L123234 = new Line(P123, P234);

        P1234 = L123234.MidPoint();

        if (CurveIsFlat())
        {
            lines.Add(new Line(this.P1, this.P4));
            return;
        }
        else
        {
            Bezier bz1 = new Bezier(this.P1, P12, P123, P1234);
            bz1.SplitBezier(lines);

            Bezier bz2 = new Bezier(P1234, P234, P34, this.P4);
            bz2.SplitBezier(lines);
        }

        return;
    }

    /// <summary>
    /// Check if points P1, P1234 and P2 are colinear (enough).
    /// This is very simple-minded algo... there are better...
    /// </summary>
    /// <returns></returns>
    public bool CurveIsFlat()
    {
        float t1 = (P2.Y - P1.Y) * (P3.X - P2.X);
        float t2 = (P3.Y - P2.Y) * (P2.X - P1.X);

        float delta = Math.Abs(t1 - t2);

        return delta < 0.1; // Hard-coded constant
    }

The PointF is from System.Drawing, and the Line class follows:

public class Line
{
    PointF P1; PointF P2;

    public Line(PointF pt1, PointF pt2)
    {
        P1 = pt1; P2 = pt2;
    }

    public PointF MidPoint()
    {
        return new PointF((P1.X + P2.X) / 2f, (P1.Y + P2.Y) / 2f);
    }
}

A sample call creates the Bezier object with 4 points (begin, 2 control, and end), and returns a list of lines that approximate the Bezier:

        TopBezier = new Bezier(Point1, Point2, Point3, Point4 );

        List<Line> lines = new List<Line>();
        TopBezier.SplitBezier(lines);

Thanks to Dr Jerry, AGG, and all the other contributors.