# Building Glyphs with Chaikin Curves

While playing around with Chaikin curves (which I first heard about from Ben Kovach in his talk about generative art) I saw that using them to connect some random points on a screen made some cool-looking glyphs. A randomly generated language!

## Overview

Chaikin curves (developed by George Chaikin in '74) create a smooth curve from a series of points by cutting the corners off of the curve.

Given a set of points, we take each line segment and:

1. Split it into three segments: the first 25% of the curve, the middle 50%, and the last 25%.
2. Discard the first and last quarters of the original segment
3. Save the start and end points of the middle line segment as the new points in the curve

In doing so, we add more points each time we run the algorithm, with the line segments getting shorter, resulting in a smoother curve. We can run the algorithm recursively and get progressively shorter line segments and a smoother line.

And then if we're dealing with a closed shape instead of a series of line segments, we also need to make a line segment out of the first and last points.

That's pretty much it, so let's build it.

## Coding the algorithm

First, we're going to code the algorithm, and then we'll use it on a canvas to make some glyphs that are pretty and unintelligible (what I strive for in my life, too).

Let's start off with some tests so that we're clear on what we're building.

### Base case

This is going to be a recursive algorithm. On the first run through with this algorithm, we're still going to have a pretty jagged curve. But once we run through it four or five times, the curve's going to be as smooth as butter.

Since it's recursive, we want to return the points of the curve once we have no more steps so that we don't get caught in an infinite loop.

`// chaikin.js// javascript's standard assert library - no need to install anything for thisconst { deepEqual } = require("assert")// write a simple assert method with slightly better loggingconst assert = (actual, expected, message) => {  try {    deepEqual(actual, expected, message)  } catch (err) {    console.error("ERROR! ", message)    console.log("Expected: ")    console.dir(err.expected)    console.log("Actual: ")    console.dir(err.actual)  }}const chaikin = () => {  /* Coming soon! */  return {}}// our test pointsconst points = [  [100, 100],  [400, 300],  [700, 200],]assert(  chaikin({ points, step: 0 }).points,  points,  "returns input points once base case is reached")`

If we run this test (with `node chaikin.js`), we get an error, since the `chaikin` function doesn't currently do anything. So, let's get the test passing:

`const { deepEqual } = require("assert")const assert = (actual, expected, message) => {  try {    deepEqual(actual, expected, message)  } catch (err) {    console.error("ERROR! ", message)    console.log("Expected: ")    console.dir(err.expected)    console.log("Actual: ")    console.dir(err.actual)  }}// NEW!const chaikin = ({ points, level }) => {  if (step <= 0) {    // return this in an object, in case we need to return more properties later    return { points }  }}const points = [  [100, 100],  [400, 300],  [700, 200],]assert(  chaikin({ points, step: 0 }).points,  points,  "returns input points once base case is reached")`

### Recursive case for open curves

Base case is covered! Now we can start finding the points. We'll start with open curves. The test case is going to involve us doing a little bit of math by hand with our test points to ensure we're looking for the correct numbers.

#### Calculating test case result by hand

Given points of `[100,100], [400, 300], [700, 200]`, what would we expect the output to be? The algorithm says that we want one point to be one quarter through the line segment, and the other point to be three quarters through. Let's calculate the end points of the middle 50% line segment.

We know the first point and second point (`[100,100]` and `[400, 300]`) `x` values are `400 - 100 = 300` pixels apart. 25% of that is `75`, and 75% is `225`, so we would expect `x1` to be at `100 + 75 = 175` and `x2` to be at `100 + 225 = 325`.

For the `y` values, we've got a difference of `300 - 100 = 200`. 25% and 75% are `50` and `150`, respectively. So, `y1` and `y2` are going to be `100 + 50` and `100 + 150`.

So, the two points that come from the first line segment are `[175, 150]` and `[325, 250]`.

And for the second line segment (`[400, 300]` and `[700, 200]`), the two points will be: `[475, 270]` and `[625, 225]`.

Let's add those for the test case, using a `step` of `1` so that we don't hit the base case immediately.

`deepEqual(  chaikin({ points, step: 1 }).points,  [    [175, 150],    [325, 250],    [475, 275],    [625, 225],  ],  "returns points 25% and 75% through each line segment")`

#### Finding the formula to calculate these values

Okay, we've got our test case. But as it stands, it's going to be hard to write an algorithm to calculate these points with the step-by-step math. Let's find a formula to make this all easier.

To get the first points values, the 25% one, we took the difference between the `x` values and then added `25%` of that difference to the first point's `x` value.

And for the second point, the `75%` one, we took the difference between the `x` values and then added `75%` of that difference to the first `x` value. In a formula:

`point1's x:xP1 = x1 + 0.25 * (x2 - x1)xP1 = x1 + (0.25 * x2) - (0.25 * x1)xP1 = (0.75 * x1) + (0.25 * x2)point2's x:xP2 = x1 + (0.75) * (x2 - x1)xP2 = x1 + (0.75 * x2) - (0.75 * x1)xP2 = (0.25 * x1) + (0.75 * x2)`

Okay! Let's get these formulas into the `chaikin` algorithm. For each line segment, we need to use these formulas on both the `x` and `y` values to create the two new points.

`const chaikin = ({ points, step }) => {  if (step <= 0) {    return { points }  }  // NEW!  const result = []  for (let i = 0; i < points.length - 1; i++) {    // current and next point in the curve    const pointA = points[i]    const pointB = points[i + 1]    const [xA, yA] = pointA    const [xB, yB] = pointB    // 25%-in point's x and y    const x1 = 0.25 * xB + 0.75 * xA    const y1 = 0.25 * yB + 0.75 * yA    // 75%-in point's x and y    const x2 = 0.75 * xB + 0.25 * xA    const y2 = 0.75 * yB + 0.25 * yA    result.push([x1, y1])    result.push([x2, y2])  }  // call chaikin again with:  // - one fewer step remaining  // - our result points that we just calculated as the new input  return chaikin({ points: result, step: step - 1 })}`

When we run the tests again, all should be passing. At this point, we could run the `chaikin` function with greater numbers of levels, and we'd get a smoother and smoother curve, as we'll see displayed soon. But first, let's cover the case for closed polygons.

### Covering the closed curve case

The difference here between the open curves is that we need to make one last extra line segment that connects the last point with the first point.

Using the same input points for our test case, we'd now expect to get 2 more points, from the `[700, 500]` and `[100,100]` line segment.

Let's calculate these two new points' values by hand first again:

`const x1 = 0.75 * 700 + 0.25 * 100 // 550const y1 = 0.75 * 200 + 0.25 * 100 // 175const x2 = 0.25 * 700 + 0.75 * 100 // 250const y2 = 0.25 * 200 + 0.75 * 100 // 125`

The last two expected points are `[550, 175]` and `[250, 125]`. We'll also need to told when we run the function whether we should calculate these last two points with a boolean flag. I'll name it `isClosed`. The test case will look like this:

`assert(  chaikin({ points, step: 1, isClosed: true }).points, // new isClosed flag is true  [    [175, 150],    [325, 250],    [475, 350],    [625, 450],    [550, 175],    [250, 125],  ],  "returns points 25% and 75% through each line segment for a closed polygon")`

Running this test fails because we're not doing anything with the `isClosed` value in our `chaikin` function yet. If the value is `true`, we just want to run the `for` loop one more time, meaning we'll run the function `points.length` times (`3`, in our test case) instead of `points.length - 1` times. Let's toss that in:

`// NEW! add the isClosed argument, defaulting to falseconst chaikin = ({ points, step, isClosed = false }) => {  if (step <= 0) {    return { points, isClosed }  }  const result = []  // NEW! use the isClosed variable to determine the max for loop index  const maxIndex = isClosed ? points.length : points.length - 1  for (let i = 0; i < maxIndex; i++) {    const pointA = points[i]    const pointB = points[i + 1]    const [xA, yA] = pointA    const [xB, yB] = pointB    // 25% in point's x and y    const x1 = 0.25 * xB + 0.75 * xA    const y1 = 0.25 * yB + 0.75 * yA    // 75% in point's x and y    const x2 = 0.75 * xB + 0.25 * xA    const y2 = 0.75 * yB + 0.25 * yA    result.push([x1, y1])    result.push([x2, y2])  }  // NEW! pass the isClosed value to any future calls  return chaikin({ points: result, step: step - 1, isClosed })}`

Almost there, but we've still got a problem. If you can't spot it, you can see an error message when we try to run this as is. If the curve is closed, `i` can get up to `2` with our test input points of length `3`. When we get to `i` being `2`, we can calculate `pointA` as `points`. But when we try to get `pointB`, we're trying to get `points`, which doesn't exist!

Instead, we want to get `points`, the first point, for `pointB`. `0` just so happens to be the remainder when we divide the index of `3` by `points.length`. We'll use that fact in order to prevent our current error with the modulus, or remainder, operator. Then, instead of finding `points`, we'll look for `points[(the remainder of i+1) / points.length] == points[0 / 3] == points`.

Let's make the switch:

`const chaikin = ({ points, step, isClosed = false }) => {  if (step <= 0) {    return { points, isClosed }  }  const result = []  const maxIndex = isClosed ? points.length : points.length - 1  for (let i = 0; i < maxIndex; i++) {    const pointA = points[i]    // NEW: use the modulus operator to avoid an index that's too high    const pointB = points[(i + 1) % points.length]    const [xA, yA] = pointA    const [xB, yB] = pointB    // 25% in point's x and y    const x1 = 0.25 * xB + 0.75 * xA    const y1 = 0.25 * yB + 0.75 * yA    // 75% in point's x and y    const x2 = 0.75 * xB + 0.25 * xA    const y2 = 0.75 * yB + 0.25 * yA    result.push([x1, y1])    result.push([x2, y2])  }  return chaikin({ points: result, step: step - 1, isClosed })}`

Our `chaikin` function is complete! We've got some test cases to give us some confidence that the algorithm is working. Let's get it onto a canvas now to see it in action.

## Using the algorithm on a canvas

### Set up the canvas

To start using this on a canvas, we'll need to make an `html` page. We can take our `chaikin` implementation and put it into a `script` tag at the end of the body.

`<!-- index.html --><body>  <canvas></canvas>  <script>    const chaikin = ({ points, step, isClosed = false }) => {      /* exact implementation we just wrote */    }    var canvas = document.querySelector("canvas")    var context = canvas.getContext("2d")    // set the size to smaller of window width or height    var size = Math.min(window.innerWidth, window.innerHeight)    canvas.width = size - 100    canvas.height = size - 100    // draw a gray rectangle covering the entire canvas    context.rect(0, 0, canvas.width, canvas.height)    context.fillStyle = "rgba(0,0,0, 0.1)"    context.fill()  </script></body>`

If you open up this `html` file and see a gray box, all is working well. You can also throw all of this code into an HTML file on Codepen to see it all working:

### Draw some curves

First, let's just draw some hard-coded points. Let's move down the canvas and ping pong between 0 and the full width as the x coordinates. Then, we'll draw both that curve and the chaikin curve with 5 steps of recursion, which should lead to a pretty smooth curve.

`<body>  <canvas></canvas>  <script>    const chaikin = ({ points, step, isClosed = false }) => {      /* ... */    }    var canvas = document.querySelector("canvas")    var context = canvas.getContext("2d")    var size = Math.min(window.innerWidth, window.innerHeight)    canvas.width = size - 100    canvas.height = size - 100    context.rect(0, 0, canvas.width, canvas.height)    context.fillStyle = "rgba(0,0,0, 0.1)"    context.fill()    // NEW!    // create the points    const points = [      [0, 0],      [canvas.width, canvas.height * 0.25],      [0, canvas.height * 0.5],      [canvas.width, canvas.height * 0.75],      [0, canvas.height],    ]    // draw the original points as a thin black line    context.beginPath()    context.lineWidth = 1    context.moveTo(points, points)    points.forEach(([x, y]) => {      context.lineTo(x, y)    })    context.stroke()    // draw the chaikin-ed points    const { points: chaikinPoints } = chaikin({ points, step: 5 })    context.lineWidth = 5    context.strokeStyle = "red"    context.beginPath()    context.moveTo(chaikinPoints, chaikinPoints)    chaikinPoints.forEach(([x, y]) => {      context.lineTo(x, y)    })    context.stroke()  </script></body>`

### Draw a glyph

A chaikin curve on a canvas! We did it! If we want to make some random glyphs, all we'll need to do is use random points instead of the hard-coded ping-pong points I made.

To make this easier on ourselves, let's make a helper function to create a point. Given a starting `x` and `y`, as well as a `width` and `height` of the box that the point needs to be in, we'll return an `[x,y]` point with a random coordinates inside of that box.

Then we'll create a set of 10 or so random points and draw a curve of those ten points at 4 steps.

`<body>  <canvas></canvas>  <script>    const chaikin = ({ points, step, isClosed = false }) => {      /* ... */    }    var canvas = document.querySelector("canvas")    var context = canvas.getContext("2d")    var size = Math.min(window.innerWidth, window.innerHeight)    canvas.width = size - 100    canvas.height = size - 100    context.lineWidth = 1    context.rect(0, 0, canvas.width, canvas.height)    context.fillStyle = "rgba(0,0,0, 0.1)"    context.fill()    // NEW!    const createRandomPoint = ({ x, y, width, height }) => {      const randomX = x + Math.random() * width      const randomY = y + Math.random() * height      return [Math.floor(randomX), Math.floor(randomY)]    }    const points = []    const pointsCount = 10    for (let i = 0; i < pointsCount; i++) {      points.push(        createRandomPoint({          x: 0,          y: 0,          width: canvas.width,          height: canvas.height,        })      )    }    // draw the chaikin-ed points    const { points: chaikinPoints } = chaikin({ points, step: 5 })    context.lineWidth = 5    context.strokeStyle = "black"    context.beginPath()    context.moveTo(chaikinPoints, chaikinPoints)    chaikinPoints.forEach(([x, y]) => {      context.lineTo(x, y)    })    context.stroke()  </script></body>`

## Bonus! Further refinements

We're pretty much where we need to be already. Refreshing the page will keep creating new random glyphs. There are two more steps I want to tackle to make the glyphs more centered and more random.

### Center the glyph

First, let's work on centering the glyph. To do this, my plan is to find the bounding box of the chaikin points to get the minimum and maximum `x` and `y` values in the curve. Then, we can find the center of the outer box we put the chaikin curve's random points in as well as the center of the chaikin bounding box. With both centers, we can calculate how far off the center of the smaller chaikin box is, and then shift every point in the chaikin curve that many pixels so that the centers for both boxes are the same.

For that, we'll first need to create a `getBounds` function that will return the minimum and maximum `x` and `y` values for a set of points.

#### Writing the getBounds function

`const getBounds = points => {  let minX, minY, maxX, maxY  if (!Array.isArray(points) || !points.length) {    throw "Expected an array with more than zero elements"  }  points.forEach(([x, y]) => {    // set new minimum if value:    //  1. doesn't exist (but isn't 0)    //  2. is less than the current minimum    if ((!minX && minX !== 0) || x <= minX) {      minX = x    }    // set new maximum if value:    //  1. doesn't exist (but isn't 0)    //  2. is more than the current maximum    if ((!maxX && maxX !== 0) || x >= maxX) {      maxX = x    }    if ((!minY && minY !== 0) || y <= minY) {      minY = y    }    if ((!maxY && maxY !== 0) || y >= maxY) {      maxY = y    }  })  return {    min: [minX, minY],    max: [maxX, maxY],  }}`

#### Use getBounds

Okay, now let's figure out the center of both boxes and shift the chaikin box to line up with the center of the outer box.

`<script>  const getBounds = points => {    /* ... */  }  const { points: chaikinPoints } = chaikin({ points, step: 5 })  // use the getBounds function to determine the height, width, and center  // of the chaikin curve  const { min: chaikinMin, max: chaikinMax } = getBounds(chaikinPoints)  const [chaikinMinX, chaikinMinY] = chaikinMin  const [chaikinMaxX, chaikinMaxY] = chaikinMax  const chaikinWidth = chaikinMaxX - chaikinMinX  const chaikinHeight = chaikinMaxY - chaikinMinY  const chaikinCenterX = chaikinMinX + chaikinWidth / 2  const chaikinCenterY = chaikinMinY + chaikinHeight / 2  // these values need to correspond to the x, y, width and height  // values we used to create the random points.  const outerBoxCenterX = 0 + canvas.width / 2  const outerBoxCenterY = 0 + canvas.height / 2  // find the difference between the outerBoxCenter and chaikinCenter  const xShiftForChaikin = outerBoxCenterX - chaikinCenterX  const yShiftForChaikin = outerBoxCenterY - chaikinCenterY  // shift the chaikin curve points by the required shift to center them  const shiftedChaikinPoints = chaikinPoints.map(([x, y]) => {    return [x + xShiftForChaikin, y + yShiftForChaikin]  })  // draw the new, shifted chaikin curve  context.beginPath()  context.moveTo(shiftedChaikinPoints, shiftedChaikinPoints)  shiftedChaikinPoints.forEach(([x, y]) => {    context.lineTo(x, y)  })  context.stroke()</script>`

Whew! Okay, now when you refresh the page, you should be getting a chaikin curve glyph that looks centered in the canvas.

### Randomize the glyph creation

Last thing we'll do today is randomize the number of points in the curve, as well as whether the curve is closed. These are much easier than the centering. All we'll need to do is change the `pointsCount` variable from a hard-coded `10` to use two new `pointsMinimum` and `pointsVariance` variables.

`const pointsMinimum = 5const pointsVariance = 5const pointsCount = pointsMinimum + Math.floor(Math.random() * pointsVariance)`

You can play around with the minimum and variance to get the shapes that you want.

And then for randomly choosing whether the curve is closed, update the `chaikin` call to have an `isClosed` parameter of `Math.random() > 0.5`. You'll also want to now return the `isClosed` parameter where we call `chaikin` so that we can draw the curve with the final line segment connected.

`const { points: chaikinPoints, isClosed: isChaikinClosed } = chaikin({  points,  step: 5,  isClosed: Math.random() > 0.5,})`

And then we'll update the drawing portion of the code to check whether the curve is closed:

`/* ... */context.beginPath()context.moveTo(chaikinPoints, chaikinPoints)chaikinPoints.forEach(([x, y]) => {  context.lineTo(x, y)})// NEW!if (isChaikinClosed) {  context.lineTo(chaikinPoints, chaikinPoints)}context.stroke()`

## Conclusion

Check out the Codepen below for the code we wrote.

From here, you'd be ready to explore what else chaikin curves could do. Some options:

1. arrange a number of glyphs in a nice grid
2. randomly place 100 chaikin curves on the screen
3. lower the opacity of the curve and draw hundreds on the screen
4. create a curve from a starting curve of 100 random points

If you make something cool, send me a screenshot!

Until next time ✌️