How to make a line curve through points

Question

I'm looking for a way to make a line curve through a number of points. It would be preferable to use 3 points although I've considered that in order to give context to the angle of the line entering a point more may be needed to give context to the curve so to speak.

In general a start point P1, a control point P2 and an end point P3, the line should curve to P2 from P1 and then curve from P2 to P3.

In fact here is a perfect example of the effect I would like to achieve:

If I could do this I really would be eternally grateful!

In Java so far, I have tried playing around with things such as QuadCurve2D.Double , Cub icCurve2D.Double and also Path2D.Double (using curveTo with Path2D.Double) but to no avail - the curves which are painted aren't even close to passing through the control point specified.

Here is an image of the methods I have tried so far :

And here is the code I used to generate the points and curves in the image :

    Graphics2D g = (Graphics2D) window.getGraphics();
    g.setColor(Color.blue);
    int d = 4;

    // P0
    int x0 = window.getWidth()/8;
    int y0 = 250;
    g.drawString("P0", x0, y0 + 4*d);
    g.fillRect(x0, y0, d, d);

    // P1
    int x1 = (window.getWidth()/7)*2;
    int y1 = 235;
    g.drawString("P1", x1, y1 + 4*d);
    g.fillRect(x1, y1, d, d);

    // P2
    int x2 = (window.getWidth()/2);
    int y2 = 200;
    g.drawString("P2", x2, y2 - 2*d);
    g.fillRect(x2, y2, d, d);

    // P3
    int x3 = (window.getWidth()/7)*5;
    int y3 = 235;
    g.drawString("P3", x3, y3 + 4*d);
    g.fillRect(x3, y3, d, d);

            // P4
    int x4 = (window.getWidth()/8)*7;
    int y4 = 250;
    g.drawString("P4", x4, y4 + 4*d);
    g.fillRect(x4, y4, d, d);

    g.setColor(Color.cyan);
    QuadCurve2D quadCurve = new QuadCurve2D.Double(x0, y0, x2, y2, x4, y4);
    g.draw(quadCurve);


    g.setColor(Color.YELLOW);
    CubicCurve2D.Double cubicCurve = new CubicCurve2D.Double((double)x0, (double)y0, 
                                                             (double)x1, (double)y1, 
                                                             (double)x2, (double)y2, 
                                                             (double)x4, (double)y4);
    g.draw(cubicCurve);


    g.setColor(Color.red);      
    Path2D.Double path1 = new Path2D.Double();
    path1.moveTo(x1, y1);
    path1.curveTo(x0, y0, x2, y2, x4, y4);
    g.draw(path1);

My reasons for wanting a curved line to pass through points is that I want to 'smoothen' the transition between vertices on a line graph I have written. Before anyone mentions it JFree Chart is not an option. I understand there are different types of curves and splines that are used but I've not had much luck in understanding exactly how they work or how to implement something that suits my needs.

I would be really grateful for any help offered - Thanks in advance.

Horse

Let me clarify are you asking to be able to draw a curve through an array of points? – Maladapted

Yes, so consider that each point on the Irwin-Hall spline is an element in the array. – Horse

Answer 1

I think you're missing the idea of what a control point is. Control points are generally not on the path itself. Instead they control how the curve of the path is shaped between points. See a spline tutorial for full details.

Now to the problem at hand, you have points on the curve but no actual control points. There are some techniques, like Cardinal Spline, for deriving control points to then pass to one of the curve drawing APIs you mention. You probably want the Path2D.Double option so you can smoothly string together individual curves.

So for drawing from P1 to P2 to P3, instead of

Path2D.Double path1 = new Path2D.Double();
path1.moveTo(x1, y1);
path1.curveTo(x0, y0, x2, y2, x4, y4);
g.draw(path1);

You want

Path2D.Double path1 = new Path2D.Double();
path1.moveTo(x1, y1);
path1.curveTo(cx1a, cy1a, cx1b, cy1b, x2, y2);
path1.curveTo(cx2a, cy2a, cx2b, cy2b, x3, y3);
g.draw(path1);

where the cx and cy coordinates are your derived control points, two control points per cubic spline segment. Possibly,

cx1a = x1 + (x2 - x1) / 3;
cy1a = y1 + (y2 - y1) / 3;
cx1b = x2 - (x3 - x1) / 3;
cy1b = y2 - (y3 - y1) / 3;
cx2a = x2 + (x3 - x1) / 3;
cy2a = y2 + (y3 - y1) / 3;
cx2b = x3 - (x3 - x2) / 3;
cy2b = y3 - (y3 - y2) / 3;

The pattern here is that for the interior points (only P2 in this case) the control points before and after it (c1b and c2a) are offset by the slope of the line between the points before and after it (P1 and P3). For the edge points, the control points are based on the slope between that point and the next closest point.

If you have domain-specific information you might choose different control points. For instance, you might want to force the slopes at the end points to be 0.

Serviette

Pretty sure cx1b and cy1b aren't supposed to be duplicated? Should they not be cx1a cy1a cx1b cy1b ? – Horse

If it's not too much trouble could you shed some light on why you choose such x and y values to construct the control points? Why do all but the last pair of control points use x1,y1? Also in the second pair cx1b and cy1b they seem to depend on the position of the point after the point the curve is approaching, but in the last pair you obviously can't take that extra step since you are approaching that last point. So I assume you perhaps use the future point x3,y3 to justify the angle of the curve approaching the second point seeing as it will then smoothly need to go on to the future point ? – Horse

Right. More info on control point formulas added to my answer. – Serviette

Answer 2

well maybe this could help :P

Catmull-Rom curves by example the same principles different lang... http://schepers.cc/svg/path/dotty.svg

Association

Catmull-rom splines differ from Irwin-hall splines in the way the curve is drawn. Check this resource and draw some points, blog.ivank.net/interpolation-with-cubic-splines.html – Maladapted

Thanks for the link Joban however if you consider this example that I created at the link you provided you can see the curve (at least in my case) would wrongfully give the impression that much larger values existed between the last to points. The Catmull-Rom example that swim linked to is acceptable however the implementation isn't clear - any ideas swim ? – Horse

Ok, so you want a catmull-rom spline then, hmm that probably should be a little easier. – Maladapted

Answer 3

Basically what you are asking is for is Cubic Spline Interpolation, I was able to find this program online Interp2.java. It actually includes a polynomial spline and cubic spline.

Unfortunately its an applet and not an actual class, but you can still look through the code are learn how they did it. Which is always a good thing.

Maladapted