# algorithm for splitting splines into arc and line

I would like to split splines of DXF files to lines and arcs in 2D for a graphic editor. From DXF file, I have extracted the following data:

• degree of spline curve
• number of knots and knot vectors
• number of control points and their coordinates
• number of fit points and their coordinates

Using the extracted data,

• start and end point of lines
• start and end point, center point, radius of arcs are needed to find.

I get confused which control points are controlling which knots by seeing the extracted data. I have found this paper about biarc curve fitting. Is it only for only two connected arc or useful for splines with so many knot points? But, it still needs tangents to calculate the points of arc. Which algorithms should I use to find the points of arcs and lines?

Biarc fitting is to find two tangential connected arcs or one line and one arc that meet the given two end points and two end tangents. You can use it as a core algorithm to approximate a spline with lines and arcs (that are connected with G1 continuity). The algorithm would be something like this:

1. Compute the start point, end point, start tangent and end tangent of the spline.
2. Use biarc algorithm to find the two curves (two arcs or one line and one arc) that meet the two end points and two end tangents.
3. Compute the deviation between the two curves and the original spline. If the deviation is sufficiently small, you are done. If not, subdivide the spline at t=0.5 and repeat step 1~3 for the two split spline.

At the end, you should have a series of lines/arc connected with tangent continuity that approximate the spline within a certain tolerance.

• To find start and end tangent, is it point of x and y from $T(t) = \frac {C'(t)} {\vert C'(t) \vert} = \frac {C'(t)_x, C'(t)_y} {\sqrt {\left[C'(t)_x\right]^2 + \left[C'(t)_y\right]^2}}$, or slope of tangent line calculated from $m = \frac {y-y_0} {x-x_0}$? I get confused when there is time to calulate value of tangent. – Toat Nov 7 '16 at 2:24
• It is $T(t)$ that you should use in biarc fitting. – fang Nov 7 '16 at 7:02
• I have found De Casteljau's algorithm to divide curves and find new control points for new curves. For step 3, would u suggest me how to find the deviation between old curve and new curves? Is it for checking whether the new curves are in circular arc shape? – Toat Nov 10 '16 at 8:37
• The deviation check is to make sure the new curves are close enough to the original spline. To perform the check, simply sample some points along the spline, then compute the distance between each point to the lines and arcs. If the maximum distance is greater than a certain tolerance, then you have to split the spline. – fang Nov 11 '16 at 3:58

See this question.