CODEWITHSUNDEEP
algorithmcomputational-geometry
Lexandr
Lexandr

Reputation: 689

Curve (spline, bezier path, etc) described by a set of base points

As an input I have set of 'base' points (e.g. 9 points), and as an output I must return another set of points, which describe a curve.

A1-A9 is an input; these are the 'base' points. My task is to return a set of points, from which the user can build the depicted curve, the black line from A1-A9

Puzzle piece

My mathematical skills are low, and Googling is not very helpful. As I understand, this can be a cubic spline. I have found some C-based source code, but this code loops endlessly when I try to build spline parts, where nextPoint.x < currentPoint.x.

Please, explain me, what kind of splines, bezier paths, or other constructs I should use for my task. It will be very good if you point me to code, an algorithm, or a good manual for dummies.

Upvotes: 2

Views: 1992

Answers (3)

user3227217
user3227217

Reputation: 1

If you have MATLAB license,

x = -4:4;
y = [0 .15 1.12 2.36 2.36 1.46 .49 .06 0];
cs = spline(x,[0 y 0]);
xx = linspace(-4,4,101);
y=ppval(cs,xx);

Upvotes: 0

Lexandr
Lexandr

Reputation: 689

Thank you all. I found the solution. For build 2D curve by basic points I do follow:
I found this article about a cubic spline with C++ and C# examples. This example allows to find interpolation values of 'one dimension' cubic spline by base points. Because I need a two dimension cubic spline - I create two one dimension splines - for 'x' and 'y' axes. Next, Next, I was run a cycle from first point to end point with some step and in each iteration of cycle I found interpolation value. From interpolation value I was make a point. So, when cycle has be ended I get a curve.

pseudo code (using spline class from article pointed above):

- (array*)splineByBasePoints:(array*)basePoints
{
    int n = basePoints.count;
    cubic_spline xSpline, ySpline;
    xSpline.build_spline(basePoints.pointNumbers, basePoints.XValuesOfPoints, n);
    ySpline.build_spline(basePoints.pointNumbers, basePoints.YValuesOfPoints, n);
    array curve;
    int t = 1; //t - intermediate point. '1' because number of point, not index

    for (; t <= n; t += step)
    {
        [curve addToArray:PontWithXY([xSpline f:t], [ySpline f:t])];
    }
    return array;
}

Upvotes: 0

Elle
Elle

Reputation: 3775

Use Interpolation methods to generate the intermediate points on your curve.

For example, given the CubicInterpolate function:

double CubicInterpolate(
   double y0,double y1,
   double y2,double y3,
   double mu)
{
   double a0,a1,a2,a3,mu2;

   mu2 = mu*mu;
   a0 = y3 - y2 - y0 + y1;
   a1 = y0 - y1 - a0;
   a2 = y2 - y0;
   a3 = y1;

   return(a0*mu*mu2+a1*mu2+a2*mu+a3);
}

to find the point halfway between point[1] and point[2] on a cubic spline, you would use:

newPoint.X = CubicInterpolate(point[0].X, point[1].X, point[2].X, point[3].X, 0.5);
newPoint.Y = CubicInterpolate(point[0].Y, point[1].Y, point[2].Y, point[3].Y, 0.5);

point[0] and point[3] do affect the section of the curve between point[1] and point[2]. At either end of the curve, simply use the end point again.

To ensure a roughly equal distance between points, you can calculate the distance between input points to determine how many intermediate points (and mu values) to generate. So, for points that are further apart, you would use many more mu values between 0 and 1. Conversely, for points that are very close together, you may not need to add intermediate points at all.

Upvotes: 1

Related Questions