# 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.

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

A line with two external points is 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`

.

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.

## 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
```

See dotgrid and ronin for interesting implementations.

## References

- Bézier curve (wikipedia)
- Bitmap/Bézier curves/Quadratic (Rosetta Code) - I think its hard to understand the Haskell version and it doesn't seem to be generalized.