30static double B0(
double u);
31static double B1(
double u);
32static double B2(
double u);
33static double B3(
double u);
47 return (((*a)[0] * (*a)[0]) + ((*a)[1] * (*a)[1]));
60 (*v)[0] *= newlen /
len;
61 (*v)[1] *= newlen /
len;
69 return (((*a)[0] * (*
b)[0]) + ((*a)[1] * (*
b)[1]));
75 double dx = (*a)[0] - (*b)[0];
76 double dy = (*a)[1] - (*b)[1];
77 return sqrt((dx * dx) + (dy * dy));
83 (*c)[0] = (*a)[0] + (*b)[0];
84 (*c)[1] = (*a)[1] + (*b)[1];
131 nPts = last - first + 1;
140 for (i = 0; i < nPts; i++) {
147 C[0][0] +=
V2Dot(&
A[0], &
A[0]);
148 C[0][1] +=
V2Dot(&
A[0], &
A[1]);
151 C[1][1] +=
V2Dot(&
A[1], &
A[1]);
164 det_C0_C1 = C[0][0] * C[1][1] - C[1][0] * C[0][1];
165 det_C0_X = C[0][0] *
X[1] - C[0][1] *
X[0];
166 det_X_C1 =
X[0] * C[1][1] -
X[1] * C[0][1];
169 if (det_C0_C1 == 0.0) {
170 det_C0_C1 = (C[0][0] * C[1][1]) * 10.0e-12;
172 alpha_l = det_X_C1 / det_C0_C1;
173 alpha_r = det_C0_X / det_C0_C1;
178 if (alpha_l < 1.0e-6 || alpha_r < 1.0e-6) {
181 bezCurve[0] = d[first];
182 bezCurve[3] = d[last];
183 V2Add(&(bezCurve[0]),
V2Scale(&(tHat1), dist), &(bezCurve[1]));
184 V2Add(&(bezCurve[3]),
V2Scale(&(tHat2), dist), &(bezCurve[2]));
192 bezCurve[0] = d[first];
193 bezCurve[3] = d[last];
194 V2Add(&bezCurve[0],
V2Scale(&tHat1, alpha_l), &bezCurve[1]);
195 V2Add(&bezCurve[3],
V2Scale(&tHat2, alpha_r), &bezCurve[2]);
210 int nPts = last - first + 1;
214 uPrime = (
double *)malloc(nPts *
sizeof(
double));
215 for (i = first; i <= last; i++) {
230 double numerator, denominator;
240 for (i = 0; i <= 2; i++) {
241 Q1[i][0] = (Q[i + 1][0] - Q[i][0]) * 3.0;
242 Q1[i][1] = (Q[i + 1][1] - Q[i][1]) * 3.0;
246 for (i = 0; i <= 1; i++) {
247 Q2[i][0] = (Q1[i + 1][0] - Q1[i][0]) * 2.0;
248 Q2[i][1] = (Q1[i + 1][1] - Q1[i][1]) * 2.0;
256 numerator = (Q_u[0] -
P[0]) * (Q1_u[0]) + (Q_u[1] -
P[1]) * (Q1_u[1]);
257 denominator = (Q1_u[0]) * (Q1_u[0]) + (Q1_u[1]) * (Q1_u[1]) + (Q_u[0] -
P[0]) * (Q2_u[0]) +
258 (Q_u[1] -
P[1]) * (Q2_u[1]);
261 if (denominator == 0) {
264 uPrime = u - (numerator / denominator);
283 for (i = 0; i <= degree; i++) {
288 for (i = 1; i <= degree; i++) {
289 for (j = 0; j <= degree - i; j++) {
290 Vtemp[j][0] = (1.0 - t) * Vtemp[j][0] + t * Vtemp[j + 1][0];
291 Vtemp[j][1] = (1.0 - t) * Vtemp[j][1] + t * Vtemp[j + 1][1];
304static double B0(
double u)
306 double tmp = 1.0 - u;
307 return (tmp * tmp * tmp);
310static double B1(
double u)
312 double tmp = 1.0 - u;
313 return (3 * u * (tmp * tmp));
316static double B2(
double u)
318 double tmp = 1.0 - u;
319 return (3 * u * u * tmp);
322static double B3(
double u)
337 tHat1 =
V2SubII(d[end + 1], d[end]);
348 tHat2 =
V2SubII(d[end - 1], d[end]);
360 V1 =
V2SubII(d[center - 1], d[center]);
361 V2 =
V2SubII(d[center], d[center + 1]);
362 tHatCenter[0] = (V1[0] + V2[0]) / 2.0;
363 tHatCenter[1] = (V1[1] + V2[1]) / 2.0;
367 if (
V2Length(&tHatCenter) < M_EPSILON) {
385 u = (
double *)malloc(uint(last - first + 1) *
sizeof(
double));
388 for (i = first + 1; i <= last; i++) {
392 for (i = first + 1; i <= last; i++) {
393 u[i - first] = u[i - first] / u[last - first];
417 *splitPoint = (last - first + 1) / 2;
419 for (i = first + 1; i < last; i++) {
423 if (dist >= maxDist) {
442 result[0] = v[0] * s;
443 result[1] = v[1] * s;
464 for (
int i = 0; i <= n; ++i) {
465 _vertices.push_back(curve[i]);
471 int size = data.size();
473 for (
int i = 0; i < size; ++i) {
474 d[i][0] = data[i][0];
475 d[i][1] = data[i][1];
484 oCurve.emplace_back(v->x(), v->y());
494 FitCubic(d, 0, nPts - 1, tHat1, tHat2, error);
506 double iterationError;
507 int maxIterations = 4;
511 iterationError = error * error;
512 nPts = last - first + 1;
519 bezCurve[0] = d[first];
520 bezCurve[3] = d[last];
521 V2Add(&bezCurve[0],
V2Scale(&tHat1, dist), &bezCurve[1]);
522 V2Add(&bezCurve[3],
V2Scale(&tHat2, dist), &bezCurve[2]);
524 free((
void *)bezCurve);
534 if (maxError < error) {
537 free((
void *)bezCurve);
542 if (maxError < iterationError) {
543 for (i = 0; i < maxIterations; i++) {
547 free((
void *)bezCurve);
553 if (maxError < error) {
556 free((
void *)bezCurve);
564 free((
void *)bezCurve);
566 FitCubic(d, first, splitPoint, tHat1, tHatCenter, error);
568 FitCubic(d, splitPoint, last, tHatCenter, tHat2, error);
An Algorithm for Automatically Fitting Digitized Curves by Philip J. Schneider,.
void DrawBezierCurve(int n, Vector2 *curve)
void FitCubic(Vector2 *d, int first, int last, Vector2 tHat1, Vector2 tHat2, double error)
void FitCurve(std::vector< Vec2d > &data, std::vector< Vec2d > &oCurve, double error)
ccl_device_inline dual1 len(const ccl_private dual< T > &a)
static Vector2 BezierII(int degree, Vector2 *V, double t)
static Vector2 * V2Normalize(Vector2 *v)
static Vector2 * V2Negate(Vector2 *v)
static Vector2 V2AddII(Vector2 a, Vector2 b)
static double B1(double u)
static double ComputeMaxError(Vector2 *d, int first, int last, BezierCurvePoints2D bezCurve, double *u, int *splitPoint)
static Vector2 ComputeRightTangent(Vector2 *d, int end)
static double NewtonRaphsonRootFind(BezierCurvePoints2D Q, Vector2 P, double u)
static Vector2 * V2Add(Vector2 *a, Vector2 *b, Vector2 *c)
static Vector2 V2ScaleIII(Vector2 v, double s)
static double V2Dot(Vector2 *a, Vector2 *b)
static double B0(double u)
static BezierCurvePoints2D GenerateBezier(Vector2 *d, int first, int last, double *uPrime, Vector2 tHat1, Vector2 tHat2)
static Vector2 ComputeLeftTangent(Vector2 *d, int end)
static Vector2 * V2Scale(Vector2 *v, double newlen)
static double V2SquaredLength(Vector2 *a)
static double * ChordLengthParameterize(Vector2 *d, int first, int last)
static double B3(double u)
static double B2(double u)
static double * Reparameterize(Vector2 *d, int first, int last, double *u, BezierCurvePoints2D bezCurve)
static double V2DistanceBetween2Points(Vector2 *a, Vector2 *b)
static double V2Length(Vector2 *a)
Vector2 * BezierCurvePoints2D
static Vector2 V2SubII(Vector2 a, Vector2 b)
static Vector2 ComputeCenterTangent(Vector2 *d, int center)
CCL_NAMESPACE_BEGIN struct Window V