catmull_rom splines

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

catmull_rom splines

Boost - Users mailing list
Hi all,

I am trying to interpolate some data with a catmull_rom spline available in boost math (interpolation). However, the resulting spline has a strange behavior; especially, at its ends (see the attached image). 
Just out of curiosity, I also tried to normalise my data to [0-1] range. However, the line has had even worse behavior (see the attached image).
Below, the c++ code segment of the interpolation is depicted:

 std::vector<std::array<double, 2>> points_intr(16);

  points_intr[0] = { 1.263270, 0.774614 };
  points_intr[1] = { 1.876, 2.480 };
  points_intr[2] = { 1.651110, 4.550 };
  points_intr[3] = { 1.426340, 5.688 };
  points_intr[4] = { 1.429, 7.054 };
  points_intr[5] = { 2.073220, 8.377020 };
  points_intr[6] = { 3.910, 9.140 };
  points_intr[7] = { 6.430, 9.537 };
  points_intr[8] = { 8.950, 9.859 };
  points_intr[9] = { 11.470, 10.317 };
  points_intr[10] = { 12.730, 10.6456 };
  points_intr[11] = { 13.990, 11.0741 };
  points_intr[12] = { 15.335, 11.6928 };
  points_intr[13] = { 16.680, 12.5661 };
  points_intr[14] = { 18.3538, 14.830 };
  points_intr[15] = { 18.700, 16.056 };
 
  bm::catmull_rom<std::array<double, 2>>
    interpolator_cr(std::move(points_intr));

  std::vector<double> x_linspace_cr(100);
  std::vector<std::array<double, 2>> inter_points(100);
  linspace(1.263270, 18.700, 100, x_linspace_cr); // evaluation points along the line
  
  for (std::size_t i{0}; i < x_linspace_cr.size(); ++i)
  {
    inter_points[i] = interpolator_cr(x_linspace_cr[i]);
  }

Should I have to add additional (ghost) points at both ends? If yes, is there any optimum way to calculate where exactly to poisition these points? I understand if I get the derivatives at both end I can calculate a straight line that the additional points should lie within. However, how should I calculate the distance from the end points?

I hope I am not doing anything fundamentally wrong. Any help would be much appreciated.

Many thanks! 

_______________________________________________
Boost-users mailing list
[hidden email]
https://lists.boost.org/mailman/listinfo.cgi/boost-users

catmull_rom_spline.png (111K) Download Attachment
catmull_rom_splines_normalised.png (90K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: catmull_rom splines

Boost - Users mailing list
Hi Giorgino,

The strange behavior at the end of the Catmull-Rom splines is a deficiency of the method. However, we are fortunate that this is not a big deficiency. This is because the Catmull-Rom splines are interpolated by functions of compact support, so a point can influence at most four segments (only two, if the point is on the boundary). Looking at your images, I personally don't think they look bad. But presumably since you are writing this, you want better!

I would recommend adding two ghost points. Draw a line between point 0 and point 1, and put the ghost point "in the mirror", i.e., place it where point 1 would appear if a mirror sat in the plane passing through P0 and orthogonal to the line joining point zero and point one. You might contend that this is an arbitrary choice, and it is! But the compact support of the basis functions means that the decision is not super important, and this choice will at least give reasonable-looking tangent vectors.

   Nick

‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Wednesday, May 29, 2019 12:08 PM, Giorgino R via Boost-users <[hidden email]> wrote:

Hi all,

I am trying to interpolate some data with a catmull_rom spline available in boost math (interpolation). However, the resulting spline has a strange behavior; especially, at its ends (see the attached image). 
Just out of curiosity, I also tried to normalise my data to [0-1] range. However, the line has had even worse behavior (see the attached image).
Below, the c++ code segment of the interpolation is depicted:

 std::vector<std::array<double, 2>> points_intr(16);

  points_intr[0] = { 1.263270, 0.774614 };
  points_intr[1] = { 1.876, 2.480 };
  points_intr[2] = { 1.651110, 4.550 };
  points_intr[3] = { 1.426340, 5.688 };
  points_intr[4] = { 1.429, 7.054 };
  points_intr[5] = { 2.073220, 8.377020 };
  points_intr[6] = { 3.910, 9.140 };
  points_intr[7] = { 6.430, 9.537 };
  points_intr[8] = { 8.950, 9.859 };
  points_intr[9] = { 11.470, 10.317 };
  points_intr[10] = { 12.730, 10.6456 };
  points_intr[11] = { 13.990, 11.0741 };
  points_intr[12] = { 15.335, 11.6928 };
  points_intr[13] = { 16.680, 12.5661 };
  points_intr[14] = { 18.3538, 14.830 };
  points_intr[15] = { 18.700, 16.056 };
 
  bm::catmull_rom<std::array<double, 2>>
    interpolator_cr(std::move(points_intr));

  std::vector<double> x_linspace_cr(100);
  std::vector<std::array<double, 2>> inter_points(100);
  linspace(1.263270, 18.700, 100, x_linspace_cr); // evaluation points along the line
  
  for (std::size_t i{0}; i < x_linspace_cr.size(); ++i)
  {
    inter_points[i] = interpolator_cr(x_linspace_cr[i]);
  }

Should I have to add additional (ghost) points at both ends? If yes, is there any optimum way to calculate where exactly to poisition these points? I understand if I get the derivatives at both end I can calculate a straight line that the additional points should lie within. However, how should I calculate the distance from the end points?

I hope I am not doing anything fundamentally wrong. Any help would be much appreciated.

Many thanks! 


_______________________________________________
Boost-users mailing list
[hidden email]
https://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|

Re: catmull_rom splines

Boost - Users mailing list
Yes, the Catmull-Rom curve is confusing for scientific application developers because it *creates* a parametrization. For example, if you solved by stepper an ODE y' = f(t,y) and got a solution skeleton {t_i, y_i}, the Catmull-Rom curve *wouldn't accept the time points t_i*. It's only interested in the y_i. Since the Catmull-Rom curve is used in computer graphics, you can kinda see why those guys don't care what the parametrization is.

I'm currently working on extending the barycentric rational interpolator into higher dimensions; mathematically it's trivial but getting the interface right is (as always) the real problem.

   Nick



‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Thursday, May 30, 2019 8:52 AM, Giorgino R <[hidden email]> wrote:

Dear Nick/all,

That was my bad.

I though that the parametrisation should be in the range [0-1] or [x_min-x_max]. I debugged my program and I saw that Catmull-Rom class internally change the parametrisation from 0 to m_max_s (for normal range 0 -1). Actually, it is explicitly mentioned in the documentation, as well. For some reason, I didn't interpret it properly. I attach my normal spline that now look as expected.

Apologies for the trouble. It's because I have never had any previous experience with these type of splines.

Many thanks
Giorgio
 

On Thu, May 30, 2019 at 11:07 AM Giorgino R <[hidden email]> wrote:
Dear Nick,

Many thanks for your prompt reply along with your valuable suggestions.

I have now added two ghost points at each end as you described; however, the curve looks (see the attached) more disappointing (always for my objectives :) ).  
To clarify, what I am trying to achieve is to get a (interpolation) line that passes through all the knots/points. Then, for a set of discrete x values (within the space of the line) I want to evaluate the corresponding points and pass them to a boost::linestring. I tried also with both Cubic B-spline interpolation and Barycentric Rational Interpolation. However, my sample points are not equally spaced and non-monotonic (x values). Therefore, I found that Catmull-Rom may be of better use here.

The other issue that is unclear to myself is that the evaluation of a Catmull-Rom spline looks dependent on the parametrisation (see the two images in my first email), as well.

Since in my application I am going to use Boost geometry, I would really like to find a solution on how to interpolate such data point sets with functionality available in Boost.

Once again, many thanks for your support.

Giorgio
    

On Wed, May 29, 2019 at 6:32 PM Nick Thompson via Boost-users <[hidden email]> wrote:
Hi Giorgino,

The strange behavior at the end of the Catmull-Rom splines is a deficiency of the method. However, we are fortunate that this is not a big deficiency. This is because the Catmull-Rom splines are interpolated by functions of compact support, so a point can influence at most four segments (only two, if the point is on the boundary). Looking at your images, I personally don't think they look bad. But presumably since you are writing this, you want better!

I would recommend adding two ghost points. Draw a line between point 0 and point 1, and put the ghost point "in the mirror", i.e., place it where point 1 would appear if a mirror sat in the plane passing through P0 and orthogonal to the line joining point zero and point one. You might contend that this is an arbitrary choice, and it is! But the compact support of the basis functions means that the decision is not super important, and this choice will at least give reasonable-looking tangent vectors.

   Nick

‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Wednesday, May 29, 2019 12:08 PM, Giorgino R via Boost-users <[hidden email]> wrote:

Hi all,

I am trying to interpolate some data with a catmull_rom spline available in boost math (interpolation). However, the resulting spline has a strange behavior; especially, at its ends (see the attached image). 
Just out of curiosity, I also tried to normalise my data to [0-1] range. However, the line has had even worse behavior (see the attached image).
Below, the c++ code segment of the interpolation is depicted:

 std::vector<std::array<double, 2>> points_intr(16);

  points_intr[0] = { 1.263270, 0.774614 };
  points_intr[1] = { 1.876, 2.480 };
  points_intr[2] = { 1.651110, 4.550 };
  points_intr[3] = { 1.426340, 5.688 };
  points_intr[4] = { 1.429, 7.054 };
  points_intr[5] = { 2.073220, 8.377020 };
  points_intr[6] = { 3.910, 9.140 };
  points_intr[7] = { 6.430, 9.537 };
  points_intr[8] = { 8.950, 9.859 };
  points_intr[9] = { 11.470, 10.317 };
  points_intr[10] = { 12.730, 10.6456 };
  points_intr[11] = { 13.990, 11.0741 };
  points_intr[12] = { 15.335, 11.6928 };
  points_intr[13] = { 16.680, 12.5661 };
  points_intr[14] = { 18.3538, 14.830 };
  points_intr[15] = { 18.700, 16.056 };
 
  bm::catmull_rom<std::array<double, 2>>
    interpolator_cr(std::move(points_intr));

  std::vector<double> x_linspace_cr(100);
  std::vector<std::array<double, 2>> inter_points(100);
  linspace(1.263270, 18.700, 100, x_linspace_cr); // evaluation points along the line
  
  for (std::size_t i{0}; i < x_linspace_cr.size(); ++i)
  {
    inter_points[i] = interpolator_cr(x_linspace_cr[i]);
  }

Should I have to add additional (ghost) points at both ends? If yes, is there any optimum way to calculate where exactly to poisition these points? I understand if I get the derivatives at both end I can calculate a straight line that the additional points should lie within. However, how should I calculate the distance from the end points?

I hope I am not doing anything fundamentally wrong. Any help would be much appreciated.

Many thanks! 

_______________________________________________
Boost-users mailing list


_______________________________________________
Boost-users mailing list
[hidden email]
https://lists.boost.org/mailman/listinfo.cgi/boost-users