将贝塞尔曲线转换为多边形链？

Question

我想将一条贝塞尔曲线分成一条带有n条直线的多边形链.线的数量取决于2条连接线之间的最大允许角度.我正在寻找一种算法来找到最佳解决方案(即尽可能减少直线的数量).

我知道如何使用Casteljau或Bernstein polynomals分割贝塞尔曲线.我尝试将bezier分成两半来计算直线之间的角度,如果连接线之间的角度在一定的阈值范围内,则再次分开,但我可能会遇到快捷方式.

是否有可用于执行此转换的已知算法或伪代码？

Answer 1

递归使用de Casteljau算法,直到控制点近似共线.例如,参见http://www.antigrain.com/research/adaptive_bezier/index.html.

Answer 2

这是一个令人着迷的话题。我唯一添加的是经过测试的 C# 代码，也许是为了省去一些麻烦。我试图写得清晰而不是速度，所以它主要遵循 AGG 网站关于 Casteljau 算法的 PDF 文档（见上文）。注释遵循该 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
    }

PointF 来自 System.Drawing，Line 类如下：

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);
    }
}

示例调用创建具有 4 个点（开始、2 个控制点和结束）的贝塞尔曲线对象，并返回近似贝塞尔曲线的线列表：

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

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

感谢 Jerry 博士、AGG 和所有其他贡献者。