[Solved] SOLVED: Fundamentals of Linear Algebra and Optimization Project 1

P1 (120 points). The purpose of this project is to design a Matlab program to plot acubic B´ezier spline curve given by a sequence of de Boor control points.Recall that a cubic B´ezier spline F(t) (in R2 or R3) is specified by a list of de Boorcontrol points (d0, d1, . . . , dN ), with N ≥ 7, and consists of N − 2 B´ezier cubic segmentsC1, . . . , CN−2, such that if the control points of Ci are (bi0, bi1, bi2, bi3), then they are determinedby the following equations:For C1, we haveb10 = d0b11 = d1b12 =12d1 +12d2b13 =12b12 +12b21 =14d1 +712d2 +16d3.The curve segment C2 is given byb20 =12b12 +12b21 =14d1 +712d2 +16d3b21 =23d2 +13d3b22 =13d2 +23d3b23 =12b22 +12b31 =16d2 +46d3 +16d4.1For i = 3, . . . , N − 4, the curve segment Ciis specified by the “one third two third rule:”bi0 =12bi−12 +12bi1 =16di−1 +46di +16di+1bi1 =23di +13di+1bi2 =13di +23di+1bi3 =12bi2 +12bi+11 =16di +46di+1 +16di+2.This generic case is illustrated in Figure 1. di−1didi+1di+2bi−12bi1bi2bi+11 bi0bi3CiFigure 1: Computing B´ezier control points from de Boor control pointsThe curve segment CN−3 is given bybN−30 =12bN−42 +12bN−31 =16dN−4 +46dN−3 +16dN−2bN−31 =23dN−3 +13dN−2bN−32 =13dN−3 +23dN−2bN−33 =12bN−32 +12bN−21 =16dN−3 +712dN−2 +14dN−1.2Finally, CN−2 is specified bybN−20 =12bN−32 +12bN−21 =16dN−3 +712dN−2 +14dN−1bN−21 =12dN−2 +12dN−1bN−22 = dN−1bN−23 = dNObserve thatbi+10 = bi3, 1 ≤ i ≤ N − 3.Using the above equation, the cases N = 5, 6 are easily adapted from the general case:compute the control points for C1, C2, . . . , CN−4, CN−2, and CN−3. When N = 4, use theformulae for C1 and CN−2 = C2 withb13 = b20 =14b1 +12b2 +14b3.(1) Implement a Matlab program to plot a cubic spline specified by a sequence of de Boorcontrol points (for N ≥ 5). Make use of a function that allows you to specify the controlpoints by clicking on the mouse (screen input).(2) Referring back to the interpolation problem defined in the notes (and the slides), canyou explain why the linear system giving d1, . . . , dN−1 in terms of the data points x0, . . . , xNand d0 and dN (N ≥ 4) is:7211 4 1 0………0 1 4 1172d1d2…dN−2dN−1=6×1 −32d06×2…6xN−26xN−1 −32dN.Beware that the N in the interpolation problem is not the same N as in (1)!P2 (80 points). The purpose of this project is to implement the subdivision version ofthe de Casteljau algorithm for approximating a B´ezier curve by a polygonal line.Given a cubic B´ezier curve C specified by its control points (b0, b1, b2, b3), for any t, thede Casteljau algorithm constructs pointsb10, b11, b12b20, b21b30,3using the equationsb1i = (1 − t)bi + tbi+1 i = 0, 1, 2b2i = (1 − t)b1i + tb1i+1 i = 0, 1b3i = (1 − t)b20 + tb21i = 0.This process is conveniently depicted as follows:0 1 2 3b0 = b00b10b1 = b01b20,b11b30b2 = b02b21b12b3 = b03Then, the point C(t) is given byC(t) = b30.The cubic curve is tangent to the line segment (b20, b21) at b30; see Figure 2.It turns out that the two sequences of pointsud = (b0, b10, b20, b30)andld = (b30, b21, b12, b3)are also control points for the curve C; see Figure 2.Thus, we can iterate the above method using the control points in ud and ld, to obtaina sequence of four control polygons, and if we iterate this process n times, we obtain 2ncontrol polygons which linked together yield a polygonal line that approximates very closelythe segment of B´ezier curve C(t) for t ∈ [0, 1]. Usually, we perform subdivision for t = 1/2.This method is called the subdivision version of the de Casteljau algorithm.(1) Implement the subdivision version of the de Casteljau algorithm in Matlab, for acubic specified by its control points (b0, b1, b2, b3). Your program should take as input thecontrol polygon (b0, b1, b2, b3) and the number of times n that your program subdivides.Try various control polygons, and for each one, show of the result of subdividing at least(six times n = 1, 2, . . . , 6).Make use of a function that allows you to specify the control points by clicking on themouse (screen input).4b0b1b2b3b10b11b12b20 b21 b30Figure 2: de Casteljau subdivision(2) Given a B´ezier curve C of degree m specified by its control points (b0, b1, . . . , bm), forany t, the de Casteljau algorithm constructs points bkiin m stagesb10, b11, . . . , b1m−2, b1m−1b20, b21, . . . , b2m−2…bm−10, bm−11bm0.If we write b0i = bifor i = 0, . . . , m, then the bkiare given by the following equations:bk+1i = (1 − t)bki + tbki+1 k = 0, . . . , m − 1, i = 0, . . . , m − k − 1,and as in the case m = 3, the point on the curve isC(t) = bm0.As in the case of cubic curves, the two sequences of pointsud = (b0, b10, . . . , bm−10, bm0)andld = (bm0, bm−11, . . . , b1m−1, bm)5are also control points for the curve C, so we can iterate the above method using the controlpoints in ud and ld, and we obtain a subdivision method that yields a polygonal line thatapproximates very closely the segment of B´ezier curve for t ∈ [0, 1].Implement the subdivision version of the de Casteljau algorithm in Matlab, for a B´eziercutrve of degree m specified by its control points (b0, b1, . . . , bm). Your program should takeas input the control polygon (b0, b1, . . . , bm), and the number of times n that your programsubdivides.Try various control polygons, and for each one, show of the result of subdividing at leastsix times (n = 1, 2, . . . , 6).Make use of a function that allows you to specify the control points by clicking on themouse (screen input).TOTAL: 200 points.6