De Casteljau algorithm and procedure

Betzie Robet Desstrio (

de Casteljau

Algorithm and program

1) Description

The most basic concept of de Casteljau algorithm is to find C points in the line segment AB, so that the C point divides the AB line segment into a ratio (| AC |: | AB | = u), how to find this C point? ?

The vector of the A to B is B - a, because u is between 0 and 1, the C point is at U (B - a), taking into account the location of the A point, the position of the C point is A U (B - A) = (1 - u) A UB, therefore, for a given U, (1-u) A UB is the C point between A and B, C point divide the AB line segment into u: ( 1-u) ratio.

The thinking of the de Casteljau algorithm is as mentioned below: Suppose we require C (u), where u is between [0, 1], starting from the first multilateral, 00-01-02-03 ...- 0N, The above formula obtained a point 1i 1i 1i on a line segment of 0i to 0 (i 1), 1I point divides the line segment of 0i to 0 (i 1) into u: (1-U) ratio; so we can get N points 10, 11, 12, ...., 1 (n-1), which form a new N-1 line segment.

In the above figure, u = 0.4, 10 is a point on the line segment of 00 to 01, 11 is a point on the 01 to 02 line segments, ..., 14 is a point on the 04 to 05 line segment, and all the new dot is displayed.

The new point is named 1i mode, perform the same operations on these new points, we will get the second multilateral and N-2 composed of (20, 21, ..., 2 (n-2)) N-1 point Tibbon; Perform this operation again, we will obtain a multilateral and N-3 strip of the third by (30, 31, ..., 3 (n-3)) N-2 points; this cycle is carried out N times After that, a single point N0 will be produced; de Casteljau proves that this point is the C (u) we required.

Let us continue to look at the above graphics, get points 20 on the line segments of 10 to 11 divide the line segments of 10 to 11 into u: (1-U) ratio, and can also get the points 21, 12 of the line segments of 11 to 12 13 The points 23, 13 to 14 on the line segment of 13, this third multilateral side has four points and three edges; so continues, we can get new multilateral edges consisting of 30, 31, and 32 points. From this fourth multilateral, we can get the fifth multilaterality consisting of 40 and 41 points; so again, we can get 50, which is the C (u) we required on the curve.

This is the geometric interpretation of the de Casteljau algorithm, very wonderful curve design.

Note: The above original text

Http://www.cs.mtu.edu/~shene/courses/cs3621/notes/spline/bezier/de-casteljau.html

2) Program

///

// PDC device

// FlarrayX composition point X coordinate sequence

// FlarrayY composition point y coordinate sequence

// created by: handwolf

// CREATE TIME: 2004-10-1

///

INT Decasteljau (CDC * PDC, Carray & flarrayx, carray & flarrayy)

{

IF (flarrayx.getsize ()! = flarrayy.getsize ()) Return 0;

Float * Pflx, * pfly;

Float fltempx, fltempy, flu; // Flu ------- u parameters

INT I, N, J;

n = flarrayx.getsize ();

IF (n <2) Return 0;

Pflx = new float [n];

Pfly = new float [n];

FLTEMPX = flarrayx.getat (0);

FLTEMPY = flarrayy.getat (0);

For (i = 0; i

PFLX [I] = flarrayx.getat (i);

Pfly [i] = flarrayy.getat (i);

}

FOR (Flu = 0; Flu <= 1; Flu = 0.05 / n) {

For (i = 1; i

For (j = 0; j

PFLX [J] = (1-Flu) * PFLX [J] Flu * PFLX [J 1];

Pfly [J] = (1-Flu) * pfly [j] flu * pfly [j 1];

}

}

PDC-> Moveto (fltempx, fltempy);

PDC-> LineTo (PFLX [0], Pfly [0]);

FLTEMPX = PFLX [0];

FLTEMPY = Pfly [0];

}

Delete [] PFLX;

Delete [] pfly;

Return 1;

}

end//