Bitmap/Bézier curves/Cubic
Using the data storage type defined on this page for raster images, and the draw_line function defined in this other one, draw a cubic bezier curve (definition on Wikipedia).
You are encouraged to solve this task according to the task description, using any language you may know.
Ada
<lang ada>procedure Cubic_Bezier
( Picture : in out Image; P1, P2, P3, P4 : Point; Color : Pixel; N : Positive := 20 ) is Points : array (0..N) of Point;
begin
for I in Points'Range loop declare T : constant Float := Float (I) / Float (N); A : constant Float := (1.0 - T)**3; B : constant Float := 3.0 * T * (1.0 - T)**2; C : constant Float := 3.0 * T**2 * (1.0 - T); D : constant Float := T**3; begin Points (I).X := Positive (A * Float (P1.X) + B * Float (P2.X) + C * Float (P3.X) + D * Float (P4.X)); Points (I).Y := Positive (A * Float (P1.Y) + B * Float (P2.Y) + C * Float (P3.Y) + D * Float (P4.Y)); end; end loop; for I in Points'First..Points'Last - 1 loop Line (Picture, Points (I), Points (I + 1), Color); end loop;
end Cubic_Bezier;</lang> The following test <lang ada> X : Image (1..16, 1..16); begin
Fill (X, White); Cubic_Bezier (X, (16, 1), (1, 4), (3, 16), (15, 11), Black); Print (X);</lang>
should produce output:
HH HH HH H H H H H H H H H H H H H H H H H H H
ALGOL 68
<lang algol68>PRAGMAT READ "Bresenhams_line_algorithm.a68" PRAGMAT;
cubic bezier OF class image :=
( REF IMAGE picture, POINT p1, p2, p3, p4, PIXEL color, UNION(INT, VOID) in n )VOID:
BEGIN
INT n = (in n|(INT n):n|20); # default 20 # [0:n]POINT points; FOR i FROM LWB points TO UPB points DO REAL t = i / n, a = (1 - t)**3, b = 3 * t * (1 - t)**2, c = 3 * t**2 * (1 - t), d = t**3; x OF points [i] := ENTIER (0.5 + a * x OF p1 + b * x OF p2 + c * x OF p3 + d * x OF p4); y OF points [i] := ENTIER (0.5 + a * y OF p1 + b * y OF p2 + c * y OF p3 + d * y OF p4) OD; FOR i FROM LWB points TO UPB points - 1 DO (line OF class image)(picture, points (i), points (i + 1), color) OD
END # cubic bezier #;
The following test
IF test THEN
REF IMAGE x = INIT LOC[16,16]PIXEL; (fill OF class image)(x, (white OF class image)); (cubic bezier OF class image)(x, (16, 1), (1, 4), (3, 16), (15, 11), (black OF class image), EMPTY); (print OF class image) (x)
FI</lang> Output:
ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff ffffffffffffffffffffffffffffffffffffffffff000000000000ffffffffffffffffffffffffffffffffffffffffff ffffffffffffffffffffffffffffff000000000000ffffffffffff000000000000ffffffffffffffffffffffffffffff ffffffffffffffffffffffff000000ffffffffffffffffffffffffffffffffffff000000ffffffffffffffffffffffff ffffffffffffffffffffffff000000ffffffffffffffffffffffffffffffffffff000000ffffffffffffffffffffffff ffffffffffffffffff000000ffffffffffffffffffffffffffffffffffffffffff000000ffffffffffffffffffffffff ffffffffffff000000ffffffffffffffffffffffffffffffffffffffffffffffff000000ffffffffffffffffffffffff ffffff000000ffffffffffffffffffffffffffffffffffffffffffffffffffffff000000ffffffffffffffffffffffff ffffff000000ffffffffffffffffffffffffffffffffffffffffffffffffffffff000000ffffffffffffffffffffffff ffffff000000ffffffffffffffffffffffffffffffffffffffffffffffffffffff000000ffffffffffffffffffffffff ffffff000000ffffffffffffffffffffffffffffffffffffffffffffffffffffff000000ffffffffffffffffffffffff 000000ffffffffffffffffffffffffffffffffffffffffffffffffffffff000000ffffffffffffffffffffffffffffff 000000ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
BBC BASIC
<lang bbcbasic> Width% = 200
Height% = 200 REM Set window size: VDU 23,22,Width%;Height%;8,16,16,128 REM Draw cubic Bézier curve: PROCbeziercubic(160,150, 10,120, 30,0, 150,50, 20, 0,0,0) END DEF PROCbeziercubic(x1,y1,x2,y2,x3,y3,x4,y4,n%,r%,g%,b%) LOCAL i%, t, t1, a, b, c, d, p{()} DIM p{(n%) x%,y%} FOR i% = 0 TO n% t = i% / n% t1 = 1 - t a = t1^3 b = 3 * t * t1^2 c = 3 * t^2 * t1 d = t^3 p{(i%)}.x% = INT(a * x1 + b * x2 + c * x3 + d * x4 + 0.5) p{(i%)}.y% = INT(a * y1 + b * y2 + c * y3 + d * y4 + 0.5) NEXT FOR i% = 0 TO n%-1 PROCbresenham(p{(i%)}.x%,p{(i%)}.y%,p{(i%+1)}.x%,p{(i%+1)}.y%, \ \ r%,g%,b%) NEXT ENDPROC DEF PROCbresenham(x1%,y1%,x2%,y2%,r%,g%,b%) LOCAL dx%, dy%, sx%, sy%, e dx% = ABS(x2% - x1%) : sx% = SGN(x2% - x1%) dy% = ABS(y2% - y1%) : sy% = SGN(y2% - y1%) IF dx% < dy% e = dx% / 2 ELSE e = dy% / 2 REPEAT PROCsetpixel(x1%,y1%,r%,g%,b%) IF x1% = x2% IF y1% = y2% EXIT REPEAT IF dx% > dy% THEN x1% += sx% : e -= dy% : IF e < 0 e += dx% : y1% += sy% ELSE y1% += sy% : e -= dx% : IF e < 0 e += dy% : x1% += sx% ENDIF UNTIL FALSE ENDPROC DEF PROCsetpixel(x%,y%,r%,g%,b%) COLOUR 1,r%,g%,b% GCOL 1 LINE x%*2,y%*2,x%*2,y%*2 ENDPROC</lang>
C
"Interface" imglib.h.
<lang c>void cubic_bezier(
image img, unsigned int x1, unsigned int y1, unsigned int x2, unsigned int y2, unsigned int x3, unsigned int y3, unsigned int x4, unsigned int y4, color_component r, color_component g, color_component b );</lang>
<lang c>#include <math.h>
/* number of segments for the curve */
- define N_SEG 20
- define plot(x, y) put_pixel_clip(img, x, y, r, g, b)
- define line(x0,y0,x1,y1) draw_line(img, x0,y0,x1,y1, r,g,b)
void cubic_bezier(
image img, unsigned int x1, unsigned int y1, unsigned int x2, unsigned int y2, unsigned int x3, unsigned int y3, unsigned int x4, unsigned int y4, color_component r, color_component g, color_component b )
{
unsigned int i; double pts[N_SEG+1][2]; for (i=0; i <= N_SEG; ++i) { double t = (double)i / (double)N_SEG;
double a = pow((1.0 - t), 3.0); double b = 3.0 * t * pow((1.0 - t), 2.0); double c = 3.0 * pow(t, 2.0) * (1.0 - t); double d = pow(t, 3.0);
double x = a * x1 + b * x2 + c * x3 + d * x4; double y = a * y1 + b * y2 + c * y3 + d * y4; pts[i][0] = x; pts[i][1] = y; }
- if 0
/* draw only points */ for (i=0; i <= N_SEG; ++i) { plot( pts[i][0], pts[i][1] ); }
- else
/* draw segments */ for (i=0; i < N_SEG; ++i) { int j = i + 1;
line( pts[i][0], pts[i][1],
pts[j][0], pts[j][1] ); }
- endif
}
- undef plot
- undef line</lang>
D
This solution uses two modules, from the Grayscale image and Bresenham's line algorithm Tasks. <lang d>import grayscale_image, bitmap_bresenhams_line_algorithm;
struct Pt { int x, y; } // Signed.
void cubicBezier(size_t nSegments=20, Color)
(Image!Color im, in Pt p1, in Pt p2, in Pt p3, in Pt p4, in Color color)
pure nothrow if (nSegments > 0) {
Pt[nSegments + 1] points = void;
foreach (immutable i, ref p; points) { immutable double t = i / cast(double)nSegments, a = (1.0 - t) ^^ 3, b = 3.0 * t * (1.0 - t) ^^ 2, c = 3.0 * t ^^ 2 * (1.0 - t), d = t ^^ 3;
alias T = typeof(Pt.x); p = Pt(cast(T)(a * p1.x + b * p2.x + c * p3.x + d * p4.x), cast(T)(a * p1.y + b * p2.y + c * p3.y + d * p4.y)); }
foreach (immutable i, immutable p; points[0 .. $ - 1]) im.drawLine(p.x, p.y, points[i + 1].x, points[i + 1].y, color);
}
void main() {
auto im = new Image!Gray(17, 17); im.clear(Gray.white); im.cubicBezier(Pt(16, 1), Pt(1, 4), Pt(3, 16), Pt(15, 11), Gray.black); im.textualShow();
}</lang>
- Output:
................. .............#### .........####.... ........#........ .......#......... ......#.......... ......#.......... .....#........... .....#........... .....#........... .....#........... ......##....####. ........####..... ................. ................. ................. .................
F#
<lang f#> /// Uses Vector<float> from Microsoft.FSharp.Math (in F# PowerPack) module CubicBezier
/// Create bezier curve from p1 to p4, using the control points p2, p3 /// Returns the requested number of segments let cubic_bezier (p1:vector) (p2:vector) (p3:vector) (p4:vector) segments =
[0 .. segments - 1] |> List.map(fun i -> let t = float i / float segments let a = (1. - t) ** 3. let b = 3. * t * ((1. - t) ** 2.) let c = 3. * (t ** 2.) * (1. - t) let d = t ** 3. let x = a * p1.[0] + b * p2.[0] + c * p3.[0] + d * p4.[0] let y = a * p1.[1] + b * p2.[1] + c * p3.[1] + d * p4.[1] vector [x; y])
</lang> <lang f#> // For rendering.. let drawPoints points (canvas:System.Windows.Controls.Canvas) =
let addLineToScreen (v1:vector) (v2:vector) = canvas.Children.Add(new System.Windows.Shapes.Line(X1 = v1.[0], Y1 = -v1.[1], X2 = v2.[0], Y2 = -v2.[1], StrokeThickness = 2.)) |> ignore let renderPoint (previous:vector) (current:vector) = addLineToScreen previous current current
points |> List.fold renderPoint points.Head
</lang>
FBSL
Windows' graphics origin is the bottom-left corner of device bitmap.
Translation of BBC BASIC using pure FBSL's built-in graphics functions: <lang qbasic>#DEFINE WM_LBUTTONDOWN 513
- DEFINE WM_CLOSE 16
FBSLSETTEXT(ME, "Bezier Cubic") FBSLSETFORMCOLOR(ME, RGB(0, 255, 255)) ' Cyan: persistent background color DRAWWIDTH(5) ' Adjust point size FBSL.GETDC(ME) ' Use volatile FBSL.GETDC below to avoid extra assignments
RESIZE(ME, 0, 0, 235, 235) CENTER(ME) SHOW(ME)
DIM %Height FBSL.GETCLIENTRECT(ME, 0, 0, 0, Height)
BEGIN EVENTS SELECT CASE CBMSG CASE WM_LBUTTONDOWN: BezierCube(160, 150, 10, 120, 30, 0, 150, 50, 20) ' Draw CASE WM_CLOSE: FBSL.RELEASEDC(ME, FBSL.GETDC) ' Clean up END SELECT END EVENTS
SUB BezierCube(x1, y1, x2, y2, x3, y3, x4, y4, n) TYPE POINTAPI x AS INTEGER y AS INTEGER END TYPE
DIM t, t1, a, b, c, d, p[n] AS POINTAPI
FOR DIM i = 0 TO n t = i / n: t1 = 1 - t a = t1 ^ 3 b = 3 * t * t1 ^ 2 c = 3 * t ^ 2 * t1 d = t ^ 3 p[i].x = a * x1 + b * x2 + c * x3 + d * x4 + 0.5 p[i].y = Height - (a * y1 + b * y2 + c * y3 + d * y4 + 0.5) NEXT
FOR i = 0 TO n - 1 Bresenham(p[i].x, p[i].y, p[i + 1].x, p[i + 1].y) NEXT
SUB Bresenham(x0, y0, x1, y1) DIM dx = ABS(x0 - x1), sx = SGN(x0 - x1) DIM dy = ABS(y0 - y1), sy = SGN(y0 - y1) DIM tmp, er = IIF(dx > dy, dx, -dy) / 2
WHILE NOT (x0 = x1 ANDALSO y0 = y1) PSET(FBSL.GETDC, x0, y0, &HFF) ' Red: Windows stores colors in BGR order tmp = er IF tmp > -dx THEN: er = er - dy: x0 = x0 + sx: END IF IF tmp < +dy THEN: er = er + dx: y0 = y0 + sy: END IF WEND END SUB END SUB</lang> Output:
Factor
The points should probably be in a sequence... <lang factor>USING: arrays kernel locals math math.functions
rosettacode.raster.storage sequences ;
IN: rosettacode.raster.line
! this gives a function
- (cubic-bezier) ( P0 P1 P2 P3 -- bezier )
[ :> x 1 x - 3 ^ P0 n*v 1 x - sq 3 * x * P1 n*v 1 x - 3 * x sq * P2 n*v x 3 ^ P3 n*v v+ v+ v+ ] ; inline
! gives an interval of x from 0 to 1 to map the bezier function
- t-interval ( x -- interval )
[ iota ] keep 1 - [ / ] curry map ;
! turns a list of points into the list of lines between them
- points-to-lines ( seq -- seq )
dup rest [ 2array ] 2map ;
- draw-lines ( {R,G,B} points image -- )
[ [ first2 ] dip draw-line ] curry with each ;
- bezier-lines ( {R,G,B} P0 P1 P2 P3 image -- )
! 100 is an arbitrary value.. could be given as a parameter.. 100 t-interval P0 P1 P2 P3 (cubic-bezier) map points-to-lines {R,G,B} swap image draw-lines ;</lang>
Fortran
This subroutine should go inside the RCImagePrimitive
module (see Bresenham's line algorithm)
<lang fortran>subroutine cubic_bezier(img, p1, p2, p3, p4, color)
type(rgbimage), intent(inout) :: img type(point), intent(in) :: p1, p2, p3, p4 type(rgb), intent(in) :: color
integer :: i, j real :: pts(0:N_SEG,0:1), t, a, b, c, d, x, y
do i = 0, N_SEG t = real(i) / real(N_SEG) a = (1.0 - t)**3.0 b = 3.0 * t * (1.0 - t)**2.0 c = 3.0 * (1.0 - t) * t**2.0 d = t**3.0 x = a * p1%x + b * p2%x + c * p3%x + d * p4%x y = a * p1%y + b * p2%y + c * p3%y + d * p4%y pts(i,0) = x pts(i,1) = y end do
do i = 0, N_SEG-1 j = i + 1 call draw_line(img, point(pts(i,0), pts(i,1)), & point(pts(j,0), pts(j,1)), color) end do
end subroutine cubic_bezier</lang>
Go
<lang go>package raster
const b3Seg = 30
func (b *Bitmap) Bézier3(x1, y1, x2, y2, x3, y3, x4, y4 int, p Pixel) {
var px, py [b3Seg + 1]int fx1, fy1 := float64(x1), float64(y1) fx2, fy2 := float64(x2), float64(y2) fx3, fy3 := float64(x3), float64(y3) fx4, fy4 := float64(x4), float64(y4) for i := range px { d := float64(i) / b3Seg a := 1 - d b, c := a * a, d * d a, b, c, d = a*b, 3*b*d, 3*a*c, c*d px[i] = int(a*fx1 + b*fx2 + c*fx3 + d*fx4) py[i] = int(a*fy1 + b*fy2 + c*fy3 + d*fy4) } x0, y0 := px[0], py[0] for i := 1; i <= b3Seg; i++ { x1, y1 := px[i], py[i] b.Line(x0, y0, x1, y1, p) x0, y0 = x1, y1 }
}
func (b *Bitmap) Bézier3Rgb(x1, y1, x2, y2, x3, y3, x4, y4 int, c Rgb) {
b.Bézier3(x1, y1, x2, y2, x3, y3, x4, y4, c.Pixel())
}</lang> Demonstration program:
<lang go>package main
import (
"fmt" "raster"
)
func main() {
b := raster.NewBitmap(400, 300) b.FillRgb(0xffefbf) b.Bézier3Rgb(20, 200, 700, 50, -300, 50, 380, 150, raster.Rgb(0x3f8fef)) if err := b.WritePpmFile("bez3.ppm"); err != nil { fmt.Println(err) }
}</lang>
J
Solution:
See the Bernstein Polynomials essay on the J Wiki.
Uses code from Basic bitmap storage, Bresenham's line algorithm and Midpoint circle algorithm.
<lang j>require 'numeric'
bik=: 2 : '((*&(u!v))@(^&u * ^&(v-u)@-.))' basiscoeffs=: <: 4 : 'x bik y t. i.>:y'"0~ i. linearcomb=: basiscoeffs@#@[ evalBernstein=: ([ +/ .* linearcomb) p. ] NB. evaluate Bernstein Polynomial (general)
NB.*getBezierPoints v Returns points for bezier curve given control points (y) NB. eg: getBezierPoints controlpoints NB. y is: y0 x0, y1 x1, y2 x2 ... getBezierPoints=: monad define
ctrlpts=. (/: {:"1) _2]\ y NB. sort ctrlpts for increasing x xvals=. ({: ,~ {. + +:@:i.@<.@-:@-~/) ({:"1) 0 _1{ctrlpts tvals=. ((] - {.) % ({: - {.)) xvals xvals ,.~ ({."1 ctrlpts) evalBernstein tvals
)
NB.*drawBezier v Draws bezier curve defined by (x) on image (y) NB. eg: (42 40 10 30 186 269 26 187;255 0 0) drawBezier myimg NB. x is: 2-item list of boxed (controlpoints) ; (color) drawBezier=: (1&{:: ;~ 2 ]\ [: roundint@getBezierPoints"1 (0&{::))@[ drawLines ]</lang>
Example usage: <lang j>myimg=: 0 0 255 makeRGB 300 300 ]randomctrlpts=: ,3 2 ?@$ }:$ myimg NB. 3 control points - quadratic ]randomctrlpts=: ,4 2 ?@$ }:$ myimg NB. 4 control points - cubic myimg=: ((2 ,.~ _2]\randomctrlpts);255 0 255) drawCircles myimg NB. draw control points viewRGB (randomctrlpts; 255 255 0) drawBezier myimg NB. display image with bezier line</lang>
Mathematica
<lang Mathematica>points= {{0, 0}, {1, 1}, {2, -1}, {3, 0}}; Graphics[{BSplineCurve[points], Green, Line[points], Red, Point[points]}]</lang>
MATLAB
Note: Store this function in a file named "bezierCubic.mat" in the @Bitmap folder for the Bitmap class defined here. <lang MATLAB> function bezierCubic(obj,pixel_0,pixel_1,pixel_2,pixel_3,color,varargin)
if( isempty(varargin) ) resolution = 20; else resolution = varargin{1}; end
%Calculate time axis time = (0:1/resolution:1)'; timeMinus = 1-time;
%The formula for the curve is expanded for clarity, the lack of %loops is because its calculation has been vectorized curve = (timeMinus).^3*pixel_0; %First term of polynomial curve = curve + (3.*time.*timeMinus.^2)*pixel_1; %second term of polynomial curve = curve + (3.*timeMinus.*time.^2)*pixel_2; %third term of polynomial curve = curve + time.^3*pixel_3; %Fourth term of polynomial
curve = round(curve); %round each of the points to the nearest integer
%connect each of the points in the curve with a line using the %Bresenham Line algorithm for i = (1:length(curve)-1) obj.bresenhamLine(curve(i,:),curve(i+1,:),color); end assignin('caller',inputname(1),obj); %saves the changes to the object
end </lang>
Sample usage: This will generate the image example for the PHP solution. <lang MATLAB> >> img = Bitmap(200,200); >> img.fill([255 255 255]); >> img.bezierCubic([160 10],[10 40],[30 160],[150 110],[255 0 0],110); >> disp(img) </lang>
OCaml
<lang ocaml>let cubic_bezier ~img ~color
~p1:(_x1, _y1) ~p2:(_x2, _y2) ~p3:(_x3, _y3) ~p4:(_x4, _y4) = let x1, y1, x2, y2, x3, y3, x4, y4 = (float _x1, float _y1, float _x2, float _y2, float _x3, float _y3, float _x4, float _y4) in let bz t = let a = (1.0 -. t) ** 3.0 and b = 3.0 *. t *. ((1.0 -. t) ** 2.0) and c = 3.0 *. (t ** 2.0) *. (1.0 -. t) and d = t ** 3.0 in let x = a *. x1 +. b *. x2 +. c *. x3 +. d *. x4 and y = a *. y1 +. b *. y2 +. c *. y3 +. d *. y4 in (int_of_float x, int_of_float y) in let rec loop _t acc = if _t > 20 then acc else begin let t = (float _t) /. 20.0 in let x, y = bz t in loop (succ _t) ((x,y)::acc) end in let pts = loop 0 [] in
(* (* draw only points *) List.iter (fun (x, y) -> put_pixel img color x y) pts; *)
(* draw segments *) let line = draw_line ~img ~color in let by_pair li f = ignore (List.fold_left (fun prev x -> f prev x; x) (List.hd li) (List.tl li)) in by_pair pts (fun p0 p1 -> line ~p0 ~p1);
- </lang>
PHP
Outputs image to the right directly to browser or stdout.
<lang php><?
$image = imagecreate(200, 200); // The first allocated color will be the background color: imagecolorallocate($image, 255, 255, 255); $color = imagecolorallocate($image, 255, 0, 0); cubicbezier($image, $color, 160, 10, 10, 40, 30, 160, 150, 110); imagepng($image);
function cubicbezier($img, $col, $x0, $y0, $x1, $y1, $x2, $y2, $x3, $y3, $n = 20) { $pts = array();
for($i = 0; $i <= $n; $i++) { $t = $i / $n; $t1 = 1 - $t; $a = pow($t1, 3); $b = 3 * $t * pow($t1, 2); $c = 3 * pow($t, 2) * $t1; $d = pow($t, 3);
$x = round($a * $x0 + $b * $x1 + $c * $x2 + $d * $x3); $y = round($a * $y0 + $b * $y1 + $c * $y2 + $d * $y3); $pts[$i] = array($x, $y); }
for($i = 0; $i < $n; $i++) { imageline($img, $pts[$i][0], $pts[$i][1], $pts[$i+1][0], $pts[$i+1][1], $col); } } </lang>
PicoLisp
This uses the 'brez' line drawing function from Bitmap/Bresenham's line algorithm#PicoLisp. <lang PicoLisp>(scl 6)
(de cubicBezier (Img N X1 Y1 X2 Y2 X3 Y3 X4 Y4)
(let (R (* N N N) X X1 Y Y1 DX 0 DY 0) (for I N (let (J (- N I) A (*/ 1.0 J J J R) B (*/ 3.0 I J J R) C (*/ 3.0 I I J R) D (*/ 1.0 I I I R) ) (brez Img X Y (setq DX (- (+ (*/ A X1 1.0) (*/ B X2 1.0) (*/ C X3 1.0) (*/ D X4 1.0)) X ) ) (setq DY (- (+ (*/ A Y1 1.0) (*/ B Y2 1.0) (*/ C Y3 1.0) (*/ D Y4 1.0)) Y ) ) ) (inc 'X DX) (inc 'Y DY) ) ) ) )</lang>
Test: <lang PicoLisp>(let Img (make (do 200 (link (need 300 0)))) # Create image 300 x 200
(cubicBezier Img 24 20 120 540 33 -225 33 285 100) (out "img.pbm" # Write to bitmap file (prinl "P1") (prinl 300 " " 200) (mapc prinl Img) ) )
(call 'display "img.pbm")</lang>
PureBasic
<lang PureBasic>Procedure cubic_bezier(img, p1x, p1y, p2x, p2y, p3x, p3y, p4x, p4y, Color, n_seg)
Protected i Protected.f t, t1, a, b, c, d Dim pts.POINT(n_seg) For i = 0 To n_seg t = i / n_seg t1 = 1.0 - t a = Pow(t1, 3) b = 3.0 * t * Pow(t1, 2) c = 3.0 * Pow(t, 2) * t1 d = Pow(t, 3) pts(i)\x = a * p1x + b * p2x + c * p3x + d * p4x pts(i)\y = a * p1y + b * p2y + c * p3y + d * p4y Next StartDrawing(ImageOutput(img)) FrontColor(Color) For i = 0 To n_seg - 1 BresenhamLine(pts(i)\x, pts(i)\y, pts(i + 1)\x, pts(i + 1)\y) ;this calls the implementation of a draw_line routine Next StopDrawing()
EndProcedure
Define w, h, img w = 200: h = 200: img = 1 CreateImage(img, w, h) ;img is internal id of the image
OpenWindow(0, 0, 0, w, h,"Bezier curve, cubic", #PB_Window_SystemMenu) cubic_bezier(1, 160,10, 10,40, 30,160, 150,110, RGB(255, 255, 255), 20) ImageGadget(0, 0, 0, w, h, ImageID(1))
Define event Repeat
event = WaitWindowEvent()
Until event = #PB_Event_CloseWindow</lang>
Python
Extending the example given here and using the algorithm from the C solution above: <lang python>def cubicbezier(self, x0, y0, x1, y1, x2, y2, x3, y3, n=20):
pts = [] for i in range(n+1): t = i / n a = (1. - t)**3 b = 3. * t * (1. - t)**2 c = 3.0 * t**2 * (1.0 - t) d = t**3 x = int(a * x0 + b * x1 + c * x2 + d * x3) y = int(a * y0 + b * y1 + c * y2 + d * y3) pts.append( (x, y) ) for i in range(n): self.line(pts[i][0], pts[i][1], pts[i+1][0], pts[i+1][1])
Bitmap.cubicbezier = cubicbezier
bitmap = Bitmap(17,17) bitmap.cubicbezier(16,1, 1,4, 3,16, 15,11) bitmap.chardisplay()
The origin, 0,0; is the lower left, with x increasing to the right,
and Y increasing upwards.
The chardisplay above produces the following output : +-----------------+ | | | | | | | | | @@@@ | | @@@ @@@ | | @ | | @ | | @ | | @ | | @ | | @ | | @ | | @ | | @@@@ | | @@@@| | | +-----------------+ </lang>
R
<lang R># x, y: the x and y coordinates of the hull points
- n: the number of points in the curve.
bezierCurve <- function(x, y, n=10) { outx <- NULL outy <- NULL
i <- 1 for (t in seq(0, 1, length.out=n)) { b <- bez(x, y, t) outx[i] <- b$x outy[i] <- b$y
i <- i+1 }
return (list(x=outx, y=outy)) }
bez <- function(x, y, t) { outx <- 0 outy <- 0 n <- length(x)-1 for (i in 0:n) { outx <- outx + choose(n, i)*((1-t)^(n-i))*t^i*x[i+1] outy <- outy + choose(n, i)*((1-t)^(n-i))*t^i*y[i+1] }
return (list(x=outx, y=outy)) }
- Example usage
x <- c(4,6,4,5,6,7) y <- 1:6 plot(x, y, "o", pch=20) points(bezierCurve(x,y,20), type="l", col="red")</lang>
Ruby
Requires code from the Bitmap and Bitmap/Bresenham's line algorithm#Ruby Bresenham's line algorithm tasks
<lang ruby>class Pixmap
def draw_bezier_curve(points, colour) # ensure the points are increasing along the x-axis points = points.sort_by {|p| [p.x, p.y]} xmin = points[0].x xmax = points[-1].x increment = 2 prev = points[0] ((xmin + increment) .. xmax).step(increment) do |x| t = 1.0 * (x - xmin) / (xmax - xmin) p = Pixel[x, bezier(t, points).round] draw_line(prev, p, colour) prev = p end end
end
- the generalized n-degree Bezier summation
def bezier(t, points)
n = points.length - 1 points.each_with_index.inject(0.0) do |sum, (point, i)| sum += n.choose(i) * (1-t)**(n - i) * t**i * point.y end
end
class Fixnum
def choose(k) self.factorial / (k.factorial * (self - k).factorial) end def factorial (2 .. self).reduce(1, :*) end
end
bitmap = Pixmap.new(400, 400) points = [
Pixel[40,100], Pixel[100,350], Pixel[150,50], Pixel[150,150], Pixel[350,250], Pixel[250,250]
] points.each {|p| bitmap.draw_circle(p, 3, RGBColour::RED)} bitmap.draw_bezier_curve(points, RGBColour::BLUE)</lang>
Tcl
This solution can be applied to any number of points. Uses code from Basic bitmap storage (newImage, fill), Bresenham's line algorithm (drawLine), and Midpoint circle algorithm (drawCircle) <lang tcl>package require Tcl 8.5 package require Tk
proc drawBezier {img colour args} {
# ensure the points are increasing along the x-axis set points [lsort -real -index 0 $args] set xmin [x [lindex $points 0]] set xmax [x [lindex $points end]] set prev [lindex $points 0] set increment 2 for {set x [expr {$xmin + $increment}]} {$x <= $xmax} {incr x $increment} { set t [expr {1.0 * ($x - $xmin) / ($xmax - $xmin)}] set this [list $x [::tcl::mathfunc::round [bezier $t $points]]] drawLine $img $colour $prev $this set prev $this }
}
- the generalized n-degree Bezier summation
proc bezier {t points} {
set n [expr {[llength $points] - 1}] for {set i 0; set sum 0.0} {$i <= $n} {incr i} { set sum [expr {$sum + [C $n $i] * (1-$t)**($n - $i) * $t**$i * [y [lindex $points $i]]}] } return $sum
}
proc C {n i} {expr {[ifact $n] / ([ifact $i] * [ifact [expr {$n - $i}]])}} proc ifact n {
for {set i $n; set sum 1} {$i >= 2} {incr i -1} { set sum [expr {$sum * $i}] } return $sum
}
proc x p {lindex $p 0} proc y p {lindex $p 1}
proc newbezier {n w} {
set size 400 set bezier [newImage $size $size] fill $bezier white for {set i 1} {$i <= $n} {incr i} { set point [list [expr {int($size*rand())}] [expr {int($size*rand())}]] lappend points $point drawCircle $bezier red $point 3 } puts $points drawBezier $bezier blue {*}$points $w configure -image $bezier
}
set degree 4 ;# cubic bezier -- for quadratic, use 3 label .img button .new -command [list newbezier $degree .img] -text New button .exit -command exit -text Exit pack .new .img .exit -side top</lang> Results in:
TI-89 BASIC
<lang ti89b>Define cubic(p1,p2,p3,p4,segs) = Prgm
Local i,t,u,prev,pt 0 → pt For i,1,segs+1 (i-1.0)/segs → t © Decimal to avoid slow exact arithetic (1-t) → u pt → prev u^3*p1 + 3t*u^2*p2 + 3t^2*u*p3 + t^3*p4 → pt If i>1 Then PxlLine floor(prev[1,1]), floor(prev[1,2]), floor(pt[1,1]), floor(pt[1,2]) EndIf EndFor
EndPrgm</lang>
XPL0
<lang XPL0>include c:\cxpl\codes; \intrinsic 'code' declarations func real Power(X, Y); \X raised to the Y power; (X > 0.0) real X, Y; return Exp(Y * Ln(X));
proc Bezier(P0, P1, P2, P3); \Draw cubic Bezier curve real P0, P1, P2, P3; def Segments = 8; int I; real T, A, B, C, D, X, Y; [Move(fix(P0(0)), fix(P0(1))); for I:= 1 to Segments-1 do
[T:= float(I)/float(Segments); A:= Power((1.-T), 3.); B:= 3.*T*Power((1.-T), 2.); C:= 3.*Power(T, 2.)*(1.-T); D:= Power(T, 3.); X:= A*P0(0) + B*P1(0) + C*P2(0) + D*P3(0); Y:= A*P0(1) + B*P1(1) + C*P2(1) + D*P3(1); Line(fix(X), fix(Y), $00FFFF); \cyan line segments ]; Line(fix(P3(0)), fix(P3(1)), $00FFFF);
Point(fix(P0(0)), fix(P0(1)), $FF0000); \red control points Point(fix(P1(0)), fix(P1(1)), $FF0000); Point(fix(P2(0)), fix(P2(1)), $FF0000); Point(fix(P3(0)), fix(P3(1)), $FF0000); ];
[SetVid($112); \set 640x480x24 video graphics Bezier([0., 0.], [30., 100.], [120., 20.], [160., 120.]); if ChIn(1) then []; \wait for keystroke SetVid(3); \restore normal text display ]</lang>