Wiki2
BezierCurves

Bézier curves in Haskell

I have always been fascinated by the simplicity and versatility of the pen tool in Adobe Illustrator.

The tool support creation and editing of bézier curves using a simple user interaction. Illustrator support linear, quadratic and cubic bézier curves.

A straight line is a linear bézier curve.

linear bézier curve

A line with one external point is quadratic bézier curve.

quadratic bézier curve

A line with two external points is cubic bézier curve.

cubic bézier curve

The way Illustrator support creation and editing of bézier curves is to put a handle on each line end point. On a cubic curve one handle is located on point P1 and one on point P2.

cubic bézier curve

different bézier curves

A curve with a single handle represent a quadratic bézier curve and a line with no handles a linear.

Haskell implementation

First I would like to implement bézier curve approximation in Haskell.

The implementation is quite straight forward. The bezier function defines one basic implementation for a linear bézier curve.

Quadratic or higher bézier can be calculated by defining a new set of lines between the bézier points of each line segment and recursively calculating the bézier of that line set, until we only have a single line left. See animations above.

For instance for a cubic bézier you have 3 line segments (P01, P12, P23). Two lines is defined by connecting the bézier points on these three lines which is used to calculate a quadratic bézier. The quadratic bézier can in the same way be reduced to a linear (which we have implemented).

module Main (main) where

import Graphics.Gloss
import Graphics.Gloss.Data.Vector
import Data.List

{- Bezier curve approximation 
   See: http://en.wikipedia.org/wiki/B%C3%A9zier_curve
   Compile: ghc -O2 Bezier.hs
   Run: ./Bezier 
 -}

type Bezier = [Point]   -- A linear, quadratic, cubic or higher order Bézier line segment
                        -- E.g. [P1, P2] (linear) or [P1, P2, P3, P4] (cubic)

-- Helpers
addV :: Vector -> Vector -> Vector
addV (a,b) (c,d) = (a+c,b+d)

subV :: Vector -> Vector -> Vector
subV (a,b) (c,d) = (a-c,b-d)

-- generate pairs from list [e1, e2, ... ] as [(e1,e2), (e2,e3), ... (e(n-1),en)]
make_pairs :: [a] -> [(a,a)]
make_pairs es = let es'  = take (length es - 1) es
                    es'' = drop 1 es
                in zip es' es''

listify :: (a,a) -> [a]
listify (a,b) = [a,b]

-- Generalized higher order Bézier approximation in a single point u [0..1]
bezier :: Float -> Bezier -> Vector
bezier u (p1:p2:[]) = p1 + mulSV u (p2 `subV` p1)                 -- linear
bezier u ps         = let pairs = map (listify) $ make_pairs ps   -- quadratic or higher
                      in  bezier u $ (map (bezier u)) $ pairs      

-- Draw Bézier as picture
draw_bezier :: Bezier -> Picture
draw_bezier ps = let p1 = head ps
                     pn = last ps
                     nsteps = (magV $ pn `subV` p1) / 5           -- ~ 5 pixel steps 
                     steps = [0, (min 0.5 (1/nsteps)) .. 1]
                     curve = Color green $ Line $ map (\u -> bezier u ps) steps
                     linear = Color orange $ Line [p1, pn]
                     outer = Color (greyN 0.75) $ Line ps
                 in pictures [curve, linear, outer]

-- Demo
b0 = [(0,0),(0,100),(250,200),(200,0)]

main = do
 display 
   (InWindow "Bézier" (600,600) (100,100))
   white              -- background
   (draw_bezier b0)

The resulting screenshot can be found below.

Bezier screen shot

UI for manipulating Bézier curves

The following table summarize a minimal set of actions to allow creation and modification of Bézier curves.

State       | Mouse Loc.   | Action            | Description                    | New state
----------- | ------------ | ----------------- | ------------------------------ | ---------
Select      | Empty space  | Click             | Start path with (no handles)   | Draw
"           | Empty space  | Click-drag        | Start path (handles)           | Draw
Draw        | Empty space  | Click             | Add point to path (no handles) | -
"           | Empty space  | Click-drag        | Add point to path (handles)    | -
"           | -            | Escape            | Undo last edit                 | -
Draw/Select | Handle       | Click-drag        | Modify handles on path [^1]    | -
"           | Handle       | Alt + Click-drag  | Modify single handle on path   | -
"           | Point        | Click-drag        | Modify point on path           | -
Draw        | Empty space  | Right-Click       | Finish path                    | Select
Select      | Point        | Alt + Click       | Toggle point in selection      | -
"           | Point        | Alt2 + Click-drag | Add handles to point           | -
"           | Path segmemt | Alt + Click       | Toggle path in selection       | -
"           | Path segmemt | Alt2 + Click      | Insert/remove point on path    | -
"           | Selection    | Click-drag        | Move selection                 | -
"           | Empty space  | Click             | Clear selection                | -
"           | -            | Delete            | Delete selection               | -

[^1]: Handle may be dropped on a point to remove the handle

TODO: Support square select/deselect in Select mode 

References