convert bezier curve to polygonal chain?

algorithm bezier polyline
dr jerry picture dr jerry · Feb 12, 2012 · Viewed 8.5k times · Source

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

lhf picture lhf · Feb 12, 2012

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

Related questions

How can I fit a Bézier curve to a set of data?

I have a set of data points (which I can thin out) that I need to fit with a Bézier curve. I need speed over accuracy, but the fit should be decent enough to be recognizable. I'm also looking …

Read More
Cheap way of calculating cubic bezier length

An analytical solution for cubic bezier length seems not to exist, but it does not mean that coding a cheap solution does not exist. By cheap I mean something like in the range of 50-100 ns (or less). Does someone …

Read More
Algorithm for deriving control points of a bezier curve from points along that curve?

I've been looking for, but obviously not finding, an algorithm that will allow me to plug in a list of x,y coordinates that are known to be along a curve so as to get the 4 control points for a …

Read More