0

I am trying to find an algorithm to draw a smooth curve passing through n points in Java.

I read a lot about the subject, but I only find examples with 3 or 4 points. I don't get how I am supposed to generalize the process with more points.

For instance, I found that answer that shows how to make a Bezier curve with 3 points. But if I repeat the process with the 3 next points, the 2 curves will not join smoothly.

I also found this interesting pdf that describes in details the process. The part I'm interested in is the 5th chapter about interpolation by cubic splines. It explains how to achieve what I want, but for 6 points. There isn't a generalization for n points.

If you see an easier approach, I would gladly take it. I just don't want Lagrange interpolation. As shown in the linked pdf, it doesn't give good results...

Community
  • 1
  • 1
Sharcoux
  • 5,546
  • 7
  • 45
  • 78
  • passing by (i.e. near) or passing through (i.e. strictly, directly through the points)? anyways, look in here: https://en.wikipedia.org/wiki/Cubic_Hermite_spline – Will Ness Apr 02 '16 at 11:39
  • Passing through (sorry, not my mother language). Thanks for the link. Still doesn't look as easy as I expected. I'll need more time to wrap my mind around all this. – Sharcoux Apr 03 '16 at 02:19
  • connect all points with lines. at each vertex, find the mid-angle and use it as the tangent direction. For the two edge tangents, use the chords directions themselves. Should be easy enough. Each segment will be defined by its two edge points and two tangent directions. – Will Ness Apr 03 '16 at 06:56
  • ... no, using the chord direction for the edge tangent isn't good, it'll introduce a curve bend. -- another option is a "biarc spline". – Will Ness Apr 03 '16 at 08:45

2 Answers2

0

You can find both short introduction into cubic splines and good practical implementation in this chapter of the book Numerical Methods in C.

You can also use Catmull-Rom splines (they provide smoothness only for the first derivative)

One more simple approach for interpolation with Bezier curves proposed by Maxim Shemanarev

MBo
  • 77,366
  • 5
  • 53
  • 86
  • Thanks a lot for these links. I'll read all that and come back to you. It will probably take me some times to understand everything. – Sharcoux Mar 31 '16 at 19:27
0

You did not mention what means smooth for you (what continuity c0,c1,c2...?) but in most cases for visual smoothness cubics are enough (4 point curves).

If you want your curve going through all the points then you want interpolation instead approximation so BEZIER/SPLINE is not a way (unless some additional computations are introduced).

So your question boils to 2 things. What polynomial curve to use and how to smoothly join more of them together. To achieve that you need to sequence the control points in a specific manner. Booth of these questions are answered here:

  • Proper implementation of cubic spline interpolation

    The interpolation polynomial used there is constructed in a way that it goes through all control points and 1st derivation is smoothly connected on both ends if more such curves are put together. The point call sequence is the same as for BEZIER/SPLINE cubics.

    If you want/need to use BEZIER instead interpolation (for example to use GDI for rendering it) and still want the curve going through all the points you can convert that interpolation cubics of mine into BEZIER (it is form of Catmull-Rom splines) you just convert the control points into new ones so BEZIER matches the same shape. It is easily done like this:

  • how to convert interpolation cubic polynomial to cubic BEZIER

Here you can find example images how the joined curves looks like

Community
  • 1
  • 1
Spektre
  • 49,595
  • 11
  • 110
  • 380
  • Thanks a lot for your answer. There's a lot to study so I won't answer deeper before making some tests. But I don't understand why you say that I want interpolation and so Bezier/Spline isn't a solution. The chapter 5 of the pdf I gave shows that it is possible, I think ? – Sharcoux Mar 31 '16 at 19:26
  • BEZIER and SPLINE are approximation curves that means that they usually only approach to control points and not necessarily cross them. There are special type of splines like Catmul-Rom that do the interpolation with BEZIER but you can look at that as a fix for approximation. The result is more or less the same as directly using/constructing interpolation polynomials but the math is a bit more complex. If you do not need that your curve goes through your points and only approaches them then you can use BEZIER but your title and text suggest you want to go through the points directly. – Spektre Mar 31 '16 at 19:59
  • Saying Bezier/Spline are not suitable for interpolation is really confusing (especially for beginners) and almost misleading (although I do understand what you meant). – fang Mar 31 '16 at 23:38
  • @fang yes but Bezier/Splines and polynomial parametric curves are usually confusing for beginners on their own anyway. – Spektre Apr 01 '16 at 06:25