How to convert interpolated curve to lines and arcs

[Ddm]

Hi, 

following previous question about how to use catmull-rom interpolation, I now need to convert interpolated paths to primitive lines and arcs or simply lines. 

This is typical problem for motion planning in robots and for plotters/ cnc to create smooth contours. 

Questions:

how to get path point of interpolated curve?  I see in previous question  "move a point along a path" ( https://groups.google.com/forum/#!topic/jsxgraph/PjP_n3MkJa0 )  how to get all points from a curve ( I guess is what moveAlong) and can be used with any interpolation. 

1) What is the point precisson? in the example it is taking 1/10 of the points. 

2) Do curve interpolation already minimices the number of points or are set at given distances over the path?

3) Is there any jsxgraph support to reduce the number of lines in curves with arcs? I'm aware that this is far from trivial, but tehre are many magical stuff already inside :D

Thanks

David 

[Alfred Wassermann]

Hi David,
interesting question. I'm not at all familiar with motion planning for robots, but the situation seem to be related to the curve plotting algorithm used in JSXGraph:

In JSXGraph, one supplies some mathematical description of a curve like (x, sin(x)) or catmullromspline(points) and at the end of the day there is a path plotted on the screen visualizing this mathematical term. In JSXGraph this path consists of line segments, no arcs. A subdivision algorithm decides where to use many line segment, e.g. if the curvature is large, or where few line segments suffice, e.g. if the curve is close to a straight line. The aim is to approximate the "real curve" such the the error is less than 1 pixel.

If suitable, it should be easy to adapt this algorithm for your problem. Since in your case the exact path is defined by a spline curve,  the approximation by line segments is expected to converge very rapidly. In the general curve plotting algorithm various critical situation must be detected: cusps, discontinuities, poles. For splines these problems do not exist, the algorithm will be much easier.

At the time being, this curve plotting algorithm is internal to the JXG.Curve object. But if there is a demand, we can extract it.
By how many line segments should the spline curve be approximated? Can you give a quality parameter, how good the approximation should be?

Best wishes,
Alfred

[Ddm]

Hi Alfred, 

great news. 

I digged a little bit in curve code to see the inner complexity of it and get scared :D

This is a general need for cutting plotters,  CNC machinery and now it is even being used in drones for  movement planning to make nice camera footages (http://diydrones.com/profiles/blogs/new-splinenav-0-3-smoother-yaw-and-manual-yaw-override).

As you pointed out, this curve comes from a previous point interpolation to create a smooth path from few control points and now it gets back to lines for the movement.

I do undertand that coming from a previous interpolation, the curve description is quite controlled and it is great that it simplifies the "curve fitting".

About the quality of the approximation, I have seen some solutions that allow to define the number of segments per spline and usually  move around 25 per spline, in the cnc world it is usually defined as number of points per cm, but I guess it could be the max delta angle between connected lines. 

The good thing is that the output from jsxgraph is already optimized, so it is one step ahead of typical processing. 

My 2 cents in possible solutions: 

 

Most CAD solutions usually provide spline to polyline/polyline+arcs and the goal is really well described here and in this chart 

from this tool , but there are many others  (ie  DXF Splines to Arcs ). Even InkScape has a plugin for flattering Beziers  that works with a flattering factor.

There are several solutions for this  but they seem to summarized here  :  

if fine control of error is desired, then biarc approximation here well explained with interactive simulation  and code here , otherwise the "four center"  solution can do the job.

I also found a quite interesting and recent paper from esri on this "Optimal Compression of a Polyline with Segments and Arcs"

Not sure if any of those approaches are too far from possible straight forward solution already foreseen but looks pretty close to the linear approximation used by most CAD programs. 

[Ddm]

Alfred, 

based on your comments, looks like the exteenal definition fo the max error in user metrics instead of pixels should be very straight forward. 

I mean if I want the max deviation to be 0.01 or 0.1  in the same metrics used at the board, it would be a great metric for my case that is close to the existing error metric. 

Thanks

[Ddm]

Back for more. 

Playing with the curve RDPsmoothing param, i got really impressive reductions. 

Is there a way to tune the tolerance to be less agressive? 

With that, I have all in place. 

In d3js Mike Bostock example lib there is an interactive visalization of the poliline simplifcacion based on " Visvalingam’s algorithm" as a more effective algorithm than  the Douglas–Peucker

https://bost.ocks.org/mike/simplify/

Thanks 

David 

[Alfred Wassermann]

Dear David, 

good suggestion. I will test this algorithm soon.

In the next few days I'm busy with other things but then I will come back to this problem.

Best wishes,

Alfred

[Alfred Wassermann]

Dear David, 

the sources contain now a first implementation of the Visvalingam-Whyatt algorithm. It can be tested with today's nightly build. An example which approximates a Cardinal spline is the following:

    var board = JXG.JSXGraph.initBoard('jxgbox', {
        boundingbox: [-10, 10, 10, -10],
        axis: true
    });

    // Generate random points
    var p = [];
    for (i=0; i<5; ++i) {
        p.push(board.create('point', [Math.random() * 12 - 6, Math.random() * 12 - 6]));
    }
   
    // Plot a cardinal spline curve through the points
    var splineArr = JXG.Math.Numerics.CardinalSpline(p, 0.5);
    var cu1 = board.create('curve', splineArr, {strokeColor: 'green'});

    // Plot an approximation of the curve cu1 with Visvalingam-Whyatt
    var c = board.create('curve', [[0],[0]], {strokeWidth: 2, strokeColor: 'black'});
    c.updateDataArray = function() {
        var i, len, points;

        // Reduce number of intermediate points with Visvalingam-Whyatt to 6
        points = JXG.Math.Numerics.Visvalingam(cu1.points, 6);

        // Plot the remaining points
        len = points.length;
        this.dataX = [];
        this.dataY = [];
        for (i = 0; i < len; i++) {
            this.dataX.push(points[i].usrCoords[1]);
            this.dataY.push(points[i].usrCoords[2]);
        }
    };
    board.update();

It is a rough implementation and has potential to be further optimized. 

Please, tell me your experiences.

Best wishes,

Alfred