Bitmap/Bézier curves/Quadratic: Difference between revisions
m Fixed lang tags. |
|||
Line 6: | Line 6: | ||
=={{header|Ada}}== |
=={{header|Ada}}== |
||
<lang ada> |
<lang ada>procedure Quadratic_Bezier |
||
procedure Quadratic_Bezier |
|||
( Picture : in out Image; |
( Picture : in out Image; |
||
P1, P2, P3 : Point; |
P1, P2, P3 : Point; |
||
Line 29: | Line 28: | ||
Line (Picture, Points (I), Points (I + 1), Color); |
Line (Picture, Points (I), Points (I + 1), Color); |
||
end loop; |
end loop; |
||
end Quadratic_Bezier; |
end Quadratic_Bezier;</lang> |
||
</lang> |
|||
The following test |
The following test |
||
<lang ada> |
<lang ada> X : Image (1..16, 1..16); |
||
X : Image (1..16, 1..16); |
|||
begin |
begin |
||
Fill (X, White); |
Fill (X, White); |
||
Quadratic_Bezier (X, (8, 2), (13, 8), (2, 15), Black); |
Quadratic_Bezier (X, (8, 2), (13, 8), (2, 15), Black); |
||
Print (X); |
Print (X);</lang> |
||
</lang> |
|||
should produce; |
should produce; |
||
<pre> |
<pre> |
||
Line 129: | Line 125: | ||
(This subroutine must be inside the <code>RCImagePrimitive</code> module, see [[Bresenham's line algorithm#Fortran|here]]) |
(This subroutine must be inside the <code>RCImagePrimitive</code> module, see [[Bresenham's line algorithm#Fortran|here]]) |
||
<lang fortran> |
<lang fortran>subroutine quad_bezier(img, p1, p2, p3, color) |
||
type(rgbimage), intent(inout) :: img |
|||
type(point), intent(in) :: p1, p2, p3 |
|||
type(rgb), intent(in) :: color |
|||
integer :: i, j |
|||
real :: pts(0:N_SEG,0:1), t, a, b, c, x, y |
|||
do i = 0, N_SEG |
|||
t = real(i) / real(N_SEG) |
|||
a = (1.0 - t)**2.0 |
|||
b = 2.0 * t * (1.0 - t) |
|||
c = t**2.0 |
|||
x = a * p1%x + b * p2%x + c * p3%x |
|||
y = a * p1%y + b * p2%y + c * p3%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 quad_bezier</lang> |
|||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
Line 272: | Line 268: | ||
{{TI-image-task}} |
{{TI-image-task}} |
||
< |
<lang ti89b>Define cubic(p1,p2,p3,segs) = Prgm |
||
Local i,t,u,prev,pt |
Local i,t,u,prev,pt |
||
0 → pt |
0 → pt |
||
Line 284: | Line 280: | ||
EndIf |
EndIf |
||
EndFor |
EndFor |
||
EndPrgm</ |
EndPrgm</lang> |
||
=={{header|Vedit macro language}}== |
=={{header|Vedit macro language}}== |
||
Line 292: | Line 288: | ||
Constant recursion depth is used here. Recursion depth of 5 seems to give accurate enough result in most situations. In real world implementations, some adaptive method is often used to decide when to stop recursion. |
Constant recursion depth is used here. Recursion depth of 5 seems to give accurate enough result in most situations. In real world implementations, some adaptive method is often used to decide when to stop recursion. |
||
<lang vedit> |
<lang vedit>// Daw a Cubic bezier curve |
||
// Daw a Cubic bezier curve |
|||
// #20, #30 = Start point |
// #20, #30 = Start point |
||
// #21, #31 = Control point 1 |
// #21, #31 = Control point 1 |
||
Line 325: | Line 320: | ||
Call("DRAW_LINE") |
Call("DRAW_LINE") |
||
} |
} |
||
return |
return</lang> |
||
</lang> |
Revision as of 19:06, 21 November 2009
You are encouraged to solve this task according to the task description, using any language you may know.
Using the data storage type defined on this page for raster images, and the draw_line function defined in this one, draw a quadratic bezier curves (definition on Wikipedia).
Ada
<lang ada>procedure Quadratic_Bezier
( Picture : in out Image; P1, P2, P3 : 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)**2; B : constant Float := 2.0 * T * (1.0 - T); C : constant Float := T**2; begin Points (I).X := Positive (A * Float (P1.X) + B * Float (P2.X) + C * Float (P3.X)); Points (I).Y := Positive (A * Float (P1.Y) + B * Float (P2.Y) + C * Float (P3.Y)); end; end loop; for I in Points'First..Points'Last - 1 loop Line (Picture, Points (I), Points (I + 1), Color); end loop;
end Quadratic_Bezier;</lang> The following test <lang ada> X : Image (1..16, 1..16); begin
Fill (X, White); Quadratic_Bezier (X, (8, 2), (13, 8), (2, 15), Black); Print (X);</lang>
should produce;
H H H H H HH HH H HH HHH HH
C
Interface (to be added to all other to make the final imglib.h>):
<lang c>void quad_bezier(
image img, unsigned int x1, unsigned int y1, unsigned int x2, unsigned int y2, unsigned int x3, unsigned int y3, color_component r, color_component g, color_component b );</lang>
Implementation:
<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 quad_bezier(
image img, unsigned int x1, unsigned int y1, unsigned int x2, unsigned int y2, unsigned int x3, unsigned int y3, 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), 2.0); double b = 2.0 * t * (1.0 - t); double c = pow(t, 2.0); double x = a * x1 + b * x2 + c * x3; double y = a * y1 + b * y2 + c * y3; 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 must be inside the RCImagePrimitive
module, see here)
<lang fortran>subroutine quad_bezier(img, p1, p2, p3, color)
type(rgbimage), intent(inout) :: img type(point), intent(in) :: p1, p2, p3 type(rgb), intent(in) :: color
integer :: i, j real :: pts(0:N_SEG,0:1), t, a, b, c, x, y
do i = 0, N_SEG t = real(i) / real(N_SEG) a = (1.0 - t)**2.0 b = 2.0 * t * (1.0 - t) c = t**2.0 x = a * p1%x + b * p2%x + c * p3%x y = a * p1%y + b * p2%y + c * p3%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 quad_bezier</lang>
Haskell
<lang haskell>{-# LANGUAGE
FlexibleInstances, TypeSynonymInstances, ViewPatterns #-}
import Bitmap import Bitmap.Line import Control.Monad import Control.Monad.ST
type Point = (Double, Double) fromPixel (Pixel (x, y)) = (toEnum x, toEnum y) toPixel (x, y) = Pixel (round x, round y)
pmap :: (Double -> Double) -> Point -> Point pmap f (x, y) = (f x, f y)
onCoordinates :: (Double -> Double -> Double) -> Point -> Point -> Point onCoordinates f (xa, ya) (xb, yb) = (f xa xb, f ya yb)
instance Num Point where
(+) = onCoordinates (+) (-) = onCoordinates (-) (*) = onCoordinates (*) negate = pmap negate abs = pmap abs signum = pmap signum fromInteger i = (i', i') where i' = fromInteger i
bézier :: Color c =>
Image s c -> Pixel -> Pixel -> Pixel -> c -> Int -> ST s ()
bézier
i (fromPixel -> p1) (fromPixel -> p2) (fromPixel -> p3) c samples = zipWithM_ f ts (tail ts) where ts = map (/ top) [0 .. top] where top = toEnum $ samples - 1 curvePoint t = pt (t' ^^ 2) p1 + pt (2 * t * t') p2 + pt (t ^^ 2) p3 where t' = 1 - t pt n p = pmap (*n) p f (curvePoint -> p1) (curvePoint -> p2) = line i (toPixel p1) (toPixel p2) c</lang>
J
See Cubic bezier curves for a generalized solution.
OCaml
<lang ocaml>let quad_bezier ~img ~color
~p1:(_x1, _y1) ~p2:(_x2, _y2) ~p3:(_x3, _y3) = let (x1, y1, x2, y2, x3, y3) = (float _x1, float _y1, float _x2, float _y2, float _x3, float _y3) in let bz t = let a = (1.0 -. t) ** 2.0 and b = 2.0 *. t *. (1.0 -. t) and c = t ** 2.0 in let x = a *. x1 +. b *. x2 +. c *. x3 and y = a *. y1 +. b *. y2 +. c *. y3 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>
Python
See Cubic bezier curves#Python for a generalized solution.
R
See Cubic bezier curves#R for a generalized solution.
Ruby
See Cubic bezier curves#Ruby for a generalized solution.
Tcl
See Cubic bezier curves#Tcl for a generalized solution.
TI-89 BASIC
<lang ti89b>Define cubic(p1,p2,p3,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^2*p1 + 2*t*u*p2 + t^2*p3 → 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>
Vedit macro language
This implementation uses de Casteljau's algorithm to recursively split the Bezier curve into two smaller segments until the segment is short enough to be approximated with a straight line. The advantage of this method is that only integer calculations are needed, and the most complex operations are addition and shift right. (I have used multiplication and division here for clarity.)
Constant recursion depth is used here. Recursion depth of 5 seems to give accurate enough result in most situations. In real world implementations, some adaptive method is often used to decide when to stop recursion.
<lang vedit>// Daw a Cubic bezier curve // #20, #30 = Start point // #21, #31 = Control point 1 // #22, #32 = Control point 2 // #23, #33 = end point // #40 = depth of recursion
- CUBIC_BEZIER:
if (#40 > 0) {
#24 = (#20+#21)/2; #34 = (#30+#31)/2 #26 = (#22+#23)/2; #36 = (#32+#33)/2 #27 = (#20+#21*2+#22)/4; #37 = (#30+#31*2+#32)/4 #28 = (#21+#22*2+#23)/4; #38 = (#31+#32*2+#33)/4 #29 = (#20+#21*3+#22*3+#23)/8; #39 = (#30+#31*3+#32*3+#33)/8 Num_Push(20,40) #21 = #24; #31 = #34 // control 1 #22 = #27; #32 = #37 // control 2 #23 = #29; #33 = #39 // end point #40-- Call("CUBIC_BEZIER") // Draw "left" part Num_Pop(20,40) Num_Push(20,40) #20 = #29; #30 = #39 // start point #21 = #28; #31 = #38 // control 1 #22 = #26; #32 = #36 // control 2 #40-- Call("CUBIC_BEZIER") // Draw "right" part Num_Pop(20,40)
} else {
#1=#20; #2=#30; #3=#23; #4=#33 Call("DRAW_LINE")
} return</lang>