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 curves (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 algol>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
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>
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>
J
Solution:
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: [xincrement] getBezierPoints controlpoints NB. y is: y0 x0, y1 x1, y2 x2 ... getBezierPoints=: verb define
2 getBezierPoints y
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 800 1200
]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 viewRGB (randomctrlpts; 255 255 0) drawBezier myimg</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 = let rec aux prev = function | [] -> () | x::xs -> f prev x; aux x xs in aux (List.hd li) (List.tl li) in by_pair pts (fun p0 p1 -> line ~p0 ~p1);
- </lang>
Ruby
<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
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