2

I have the feeling that I'm way out of my element here, and that maybe this question will be obvious to most of you. Nonetheless, here goes:

I have an example set of 22 two-dimensional points, ordered in increasing x-axis value:

319.48067   -219.040581
323.411004  -221.767389
326.375842  -222.245532
327.8193    -224.307961
330.315608  -225.26134
331.952721  -228.313128
334.289559  -228.254367
335.988759  -231.239028
339.392045  -229.993712
340.882416  -232.052757
343.045085  -234.498472
345.091425  -235.021075
347.066267  -236.365868
348.887618  -238.0629
350.364466  -241.289831
352.211338  -242.140001
353.641035  -245.225141
355.346446  -246.093982
356.474918  -249.797807
357.66939   -252.040193
357.700936  -255.611868
358.127355  -260.326559

I want to smooth out this shape by creating a Bézier curve with the 2 end points and the 20 internal points as the control points. I then want to sample the curve at equally spaced parametric 't' values to achieve the curve fit. I've written a C++ routine to calculate the Bézier curve values, and the output seems very wrong to me.

For the following 20 parametric 't' values:

0.047619047619
0.095238095238
0.142857142857
0.190476190476
0.238095238095
0.285714285714
0.333333333333
0.380952380952
0.428571428571
0.476190476190
0.523809523810
0.571428571429
0.619047619048
0.666666666667
0.714285714286
0.761904761905
0.809523809524
0.857142857143
0.904761904762
0.952380952381

I get the following 20 locations on the curve:

172.548459,-118.213783
118.690938,-81.208733
100.189584,-68.513146
94.453547,-64.601268
93.078197,-63.668437
93.107059,-63.666879
93.558920,-63.928764
94.124242,-64.262521
94.707939,-64.625647
95.280613,-65.014698
95.833185,-65.433873
96.363957,-65.888688
96.877984,-66.386296
97.400090,-66.944260
98.025710,-67.629717
99.090008,-68.689441
101.684547,-70.933598
109.123610,-76.804231
130.846232,-93.207709
192.234365,-138.650327

This doesn't look right to me, and it certainly doesn't achieve a curve fit.

My question is: is my Bézier curve calculation incorrect, or is my understanding of what a Bézier curve should look like incorrect?

Please see the following two images of the original shape only plus the outputted Bézier curve locations:

Shape Only Graph

Shape With Curve Samples Graph

Parcly Taxel
  • 103,344
user2062604
  • 125
  • Bezier curve is always bounded by the convex hull (or XY bounding box) of its control points. So, the fact that your curve goes beyond the range of x and y of the control points means that you most likely have some bugs computing points on the Bezier curve. – fang Jun 16 '16 at 23:27
  • Thanks fang! You are correct, I looked more closely and determined that I was calculating the binomial coefficient incorrectly. It's working properly now. I don't know how to mark your comment as the correct answer... any help would be much appreciated! – user2062604 Jun 17 '16 at 15:32
  • I will repost my comment as an answer with a little bit more information. – fang Jun 17 '16 at 19:59

1 Answers1

1

Bezier curve is always bounded by the convex hull (or XY bounding box) of its control points. So, the fact that your curve goes beyond the range of x and y of the control points means that you most likely have some bugs computing points on the Bezier curve.

A common mistake when computing high degree Bezier curve is the overflow issue when computing the binomial coefficient. For 32bit machine/OS, the binomial coefficient will have overflow condition when the curve's degree reaches 25 or 26.

Furthermore, for performance sake, it is also a common practice to calculate these binomial coefficients in advance and store them in arrays so that you do not need to repeatedly compute the same coefficients when evaluating points on the curve.

fang
  • 3,570