An algorithm for polygons with rounded corners

01/26/2022

Quick Index

  1. Introduction: An algorithm for rounded corners
  2. Credit where credit’s due
  3. An intuitive explanation of the algorithm
  4. Breakdown of the algorithm
  5. Two Vectors from three Points
  6. Calculating the angle using the cross product
  7. Ambiguity of the cross product
  8. Positioning the circle
  9. The rendering context
  10. Drawing the final shape

Further Improvements

  1. Blindman67’s method using p5 vectors
  2. Dave’s acceleration method
  3. Dave’s Bezier curve method

Introduction: An algorithm for rounded corners

If you spent some time doing creative coding, you’ll very quickly come to the realization that anything, which has a shape that is little more complicated than your average rectangle or circle, quickly starts requiring a fair amount of code to be summoned onto your canvas.

This post/tutorial was initially sparked by a snippet of code that I’ve found on stackoverflow. In the past months, this algorithm has unlocked a number shapes and sketches for me, that I otherwise wouldn’t have been able to make. In essence, the algorithm allows you to create arbitrarily shaped polygons, with any number of vertices while at the same time being able to control the roundness (or curvature) of each vertex.

I came across this code when I attempted a sketch in which I wanted to round off the corners of some triangles:

In p5js there is no out-of-the-box method for doing so, except when it comes to rectangular shapes, where the 5th to 8th parameters can be used for that purpose. You could technically do it with a series of curveVertex() calls, however that strategy doesn’t offer much control. Here’s another sketch that I made during #GENUARY2022, which also makes use of the same algorithm, even if it might not be as obvious:

You can notice that you can even mix between pointy corners and round corners, which is another thing that isn’t possible with pure p5js (without writing a lot of additional code towards that end). This definitely came in clutch this Genuary. The remainder of this post will walk you through this really cool and useful algorithm, step by step.

Credit where credit's due

The code discussed in this post stems from this stackoverflow answer by stackoverflow user Blindman67. (Go give him some upvotes on his answer if you find this useful!) Blindman67 explains his strategy succinctly, and is more than sufficient for you to start using his code.

But for the sake of REALLY understanding the algorithm, we’ll recreate it from scratch based off of his explanation and analyzing his code! There are a number of noteworthy things going on, that are worth inspecting in more detail, and can be generalized to a number of other scenarios.

An intuitive explanation of the algorithm

We’ll begin with an intuitive depiction of what the algorithm is accomplishing. The idea behind what we’re trying to do is generally simple: We’re going to take an imaginary circle of a certain radius, and push it as far as possible into a corner (any kind of corner, not necessarily 90 degrees) that we’re trying to round. Next, we erase the lines that form the pointy corner, starting from the place where they are tangential to the imaginary circle, and close the shape again by tracing the outward facing portion of our circle.

And voila, we have obtained a rounded corner with a specific radius. Seems straightforward, right? However, to accomplish this there are a number of steps that we need to follow.

Breakdown of the algorithm

Given a specific radius, the difficulty lies within finding where to exactly position the circle that rounds the corner to that radius. If we can exactly pinpoint where this circle is positioned, we can also determine where it is tangential to the lines that form the pointy corner. Those two points will determine the start and end of the arc that will form the rounded corner. Overall, given three points A, B and C that form a corner, as well as a given radius, the steps are:

  1. Converting 3 points into 2 vectors
  2. Calculating the angle between those two vectors
  3. Calculating and locating the half-angle between the two vectors
  4. Finding the distance from the circle center to the corner
  5. Drawing the arc

Two Vectors from three Points

First we’ll need to find the value of the angle that is formed by three points. To do so we first need to turn these 3 points into two vectors. For three points A, B and C we can find the vectors BA and BC by using the following function:

// p1 -> first point
// p2 -> second point
// v -> container that we will fill
// we could also not pass v and simply return it
function toVec(p1, p2, v) {

    // center the vector based on the coordinates of p2 (the point B in this case)
    v.x = p2.x - p1.x;
    v.y = p2.y - p1.y;

    // compute magnitude (length) of the vector
    v.len = Math.sqrt(v.x * v.x + v.y * v.y);
    
    // alternatively and more concisely v.len = Math.hypot(v.x, v.y); 

    // normalized coordinates
    v.nx = v.x / v.len;
    v.ny = v.y / v.len;

    // calculate the angle
    v.ang = Math.atan2(v.ny, v.nx);
}

The comments should be sufficient to understand what is happening, we also use the atan2() function to calculate the angle of the vectors with respect to the zero angle. For simplicity’s sake we’ll make the origin at the center of the canvas. To fill our vector containers, we can do as such:

function setup() {
  w = min(windowWidth, windowHeight)
  createCanvas(w, w);
}

function draw() {
  background(220);

  // make origin at center of canvas
  translate(w/2,w/2)

  p1 = {x: 100, y: 0}
  p2 = {x: 0, y: 0}
  p3 = {x: 0, y: -100}

  strokeWeight(5)
  point(p1.x,p1.y)
  point(p2.x,p2.y)
  point(p3.x,p3.y)

  v1 = {}
  v2 = {}

  toVec(p1,p2,v1)
  toVec(p3,p2,v2)

  noLoop()
}

// p1 -> first point
// p2 -> second point
// v -> container that we will fill
function toVec(p1, p2, v) {
    v.x = p2.x - p1.x;
    v.y = p2.y - p1.y;
    v.len = Math.hypot(v.x, v.y);
    v.nx = v.x / v.len;
    v.ny = v.y / v.len;
    v.ang = Math.atan2(v.ny, v.nx);
}

You might ask, why we’re not doing this with p5js’s inbuilt vector class? And fret not, at the end of this post well go over an alternative version where we use the class with all it’s functionalities. Now that we have converted our 3 points into vector form, we can tackle computing and locating the intermediary angle between the two vectors!

Calculating the angle using the cross product

Explanation

Getting the halfway angle is probably the trickiest part of the procedure, and requires a number of steps. There probably are multiple ways to do so (more on that later), but for starters we’ll begin with the method deduced from Blindman67’s code. It will require us to freshen up on our linear algebra a little bit, specifically on the cross product of two vectors. We’ll be heavily exploiting the formula of the cross product to compute the value of the formed angle, as well as where it is located with respect to the two vectors.

What the cross product actually represents algebraically, is a bit outside of the scope of this post. A perfect resource for understanding it can be found in the form of this video by 3Blue1Brown (I don’t think there’s a need for me to introduce his channel).

The important part here is how the cross product can help us find the angle between two vectors, and what problems arise from this method. Given two vectors, we observe two angles, one that is less than 180 degrees, and another ‘reflex’ angle larger than 180 degrees. Our task is thus finding the angle that allows us to draw an arc, such that we can trace it and round off the pointy corner. We can only round off a corner if we select the angle that has a value less than 180 degrees.

In this manner, we also need to determine the correct drawing order. We’re going around the polygonal shape in a clockwise manner, but depending if the angle is concave or convex (curved inwards vs being curved outwards), we’ll have to sometimes draw our arcs in a counterclockwise manner. To this end, calculating the value of the angle is not sufficient, we need an additional indicator that tells us how the second vector BC is situated with respect to the first one BA. For this we can use the cross product of BC and the perpendicular line to BA. More on that in a bit.

The Math

Generally the formula for finding the cross product, is the product of the magnitudes of our two vectors, with the sine of the angle that they form. More concretely:

\( \Vert BA \Vert * \Vert BC \Vert * sin( \Theta ) \)

This means that, finding the cross product requires us to already have the angle... who's value we're trying to find. Now, if we were to somehow already have the numerical value of the cross product, we could solve for \( sin( \Theta ) \), since we also already have the magnitudes of the two vectors concerned \( \Vert BA \Vert \) and \( \Vert BC \Vert \).

Luckily, there is another way to find the numerical value of the cross product! It is actually equal to the determinant of the 2x2 matrix formed by these vectors. This means computing this determinant will allow us to find the angle by solving the previous formula! Computing the determinant of a matrix is done as follows:

\( v_{1}x * v_{2}y - v_{2}x * v_{1}y \)

Then the value of the angle can be calculated as follows:

\( \Theta = sin^{-1}(\frac{v_{1}x * v_{2}y - v_{2}x * v_{1}y}{\Vert BA \Vert * \Vert BC \Vert}) \)

If you’re not familiar with the inverse sine function, it simply does the reverse operation that a regular sine function does. So for example, a sine function will accept a value between -PI/2 and PI/2, and return a value that ranges between -1 and 1. The inverse function will accept values between -1 and 1 and return an angle that ranges between -PI/2 and PI/2.

This formula can be further simplified! Since our vectors are already normalized \( \Vert BA \Vert * \Vert BC \Vert \), they will simply evaluate to 1, leaving us with:

\( \Theta = sin^{-1}(det) \)

Which is thus simply the inverse sine of the determinant. Now let’s implement this.

The Code

The code for all of what we have discussed in the previous section is relatively… tame, and can essentially be summarised in a single line! Let’s have a look at Blindman67’s code:

// compute and store our 2 vectors
toVec(p2, p1, v1);
toVec(p2, p3, v2);

// Cross product of the two vectors - what we discussed in the previous section
sinA = v1.nx * v2.ny - v1.ny * v2.nx;

// Cross product of v2 and the line at 90 degrees to v1
// This is necessary and will help determine where to exactly position the center of the circle
sinA90 = v1.nx * v2.nx - v1.ny * -v2.ny;

// Clamping the value of sinA to avoid NaNs
angle = Math.asin(sinA < -1 ? -1 : sinA > 1 ? 1 : sinA);

We already discussed at length the first calculation that computes the variable sinA. The second line computes the cross product of the perpendicular line to BA and the vector BC. In actuality, we don’t need to create a separate vector for this perpendicular, we can simply exploit the fact that the dot product of two vectors is zero when they’re perpendicular. A vector perpendicular to BA would be simply one that has it’s x and y values flipped, in addition to having one of their signs flipped. For example:

zeroDotProduct = v1.nx*(-v1.ny) + v1.ny*v1.nx

Of course it also matters which coordinate’s sign we flip, because it determines which perpendicular we’re selecting (the one at 90 degrees or the other one at -90 degrees). If we flip the other sign, we’ll would have to proceed differently in the calculations that follow.

Another tricky part here, I found to be the nested ternary check inside the inverse sine function. By simply expanding it, we visually get some clarity:

if(sinA<-1){
  angle = Math.asin(-1)
}else if(sinA>1){
  angle = Math.asin(1)
}else{
  angle = Math.asin(sinA)
}

Go ahead a try putting values lesser than -1 or greater than 1 into the inverse sine function. It’ll yield a NaN value. To avoid such thing, we simply clamp the value and can be done compactly as a one liner. And if you noticed, in actuality, we have already obtained the value of the angle!

Ambiguity of the cross product

There’s a couple more steps that we have to do to go through to get the correct half angle between our two vectors. We’ll start with this if/else flurry to determine the orientation of our angle:

radDirection = 1;
drawDirection = false;
if (sinA90 < 0) {
  if (angle < 0) {
    angle = Math.PI + angle;
  } else {
    angle = Math.PI - angle;
    radDirection = -1;
    drawDirection = true;
  }
} else {
  if (angle > 0) {
    radDirection = -1;
    drawDirection = true;
  }
}

In essence, the information that we’re trying to find here, is where exactly the center of the circle is located (the angle or it’s reflex) as well as the correct drawing order of the arc (clockwise or counter clockwise). This is what the above if/else block takes care of. Let’s for a second assume that the angle that we have calculated is sufficient, and simply halve it to find the bisector:

Run the snippet a couple of times and take note of where the red line falls, it only gets it right when the angle is acute. We do not get the correct bisector when the angle is obtuse.

Hence, we need another indicator to be able to determine where to position the center of the circle. For this purpose we can use the cross product of the angle formed by the perpendicular of BA and the vector BC that we previously calculated. Simultaneously observing where that perpendicular falls with respect to BC, by inspecting the sign of these two cross products we can pin point where the bisector is located. Let’s examine the different scenarios that arise:

When sinA90 < 0 and sinA > 0

When sinA90 is larger than 0, and sinA is less than 0, then we can conclude that the perpendicular lies in between BA and BC, and the vectors BA and BC form an obtuse fan. In this case we need to add PI to the angle before halving it to obtain the correct half angle.

When sinA90 < 0 and sinA > 0

In this case the angle formed is also an obtuse fan, but the perpendicular does not lie in between BA and BC. In this case we need to subtract the angle from PI and also invert the drawing order (this is what radDirection and drawDirection are used for).

When sinA90 > 0

In this case the angle formed is an acute wedge, and we need to distinguish the two cases where the vector BC lies in between BA and it’s perpendicular aka sinA < 0 and when it’s not aka sinA > 0, and in the latter case we need to invert the drawing order.

If that explanation wasn’t enough mental gymnastics, then feel welcome to sketch out a couple of angles and work them out by yourself. Important to keep in mind that if we were to select the other perpendicular, we then would have to flip some of the checks.

Example

Here’s an example of this in action. Observe the position of BC, BA and it’s perpendicular as well as the values of sinA and sinA90. The assumed drawing order is clockwise starting from BA, going to BC:

If you’ve followed until here, then congrats, the hardest part is past us!

Simpler way to calculating the angle?

Now these are a lot of hoops to go through for simply calculating. If you want to have a simpler way of finding that angle you can use:

// vectors should be normalized
angle = atan2(v2.y, v2.x) - atan2(v1.y, v1.x)
if (angle < 0) { angle += 2 * PI;}

However, this isn’t sufficient to figuring out the correct drawing order of our arc. We’ll go over a simpler way to our strategy later in this post.

A visual example

To conclude this section, here’s a visual example of why this is necessary. If we were to ignore the correct orientation and drawing order of the arcs we would end up with weird behaviour:

Positioning the circle

The next step is finding the distance from the circlecenter to the coordinate of the corner:

lenOut = abs(cos(halfAngle) * radius / sin(halfAngle));

Here, instead of finding the distance of the circle center F to corner point B, we're directly finding the distance from the corner point B to the tangential points E and F. For this we're making use of the formulas that can be applied for finding the length of the hypotenuse, which is designated by BF. We then have \( BF * cos(\Theta) = BE \) and \( BF * sin( \Theta) = FE \).

Using these two formulas we find the formula that Blindman67 used:

\( \frac{BE}{cos(\Theta)} = \frac{r}{sin(\theta)} \)

And here we also have the value of the radius (that we specified):

\( BE = abs( \frac{cos(\Theta) * r}{sin(\theta)}) \)

One problem here is that the radius that we specified as input, might not fit into the corner. Since it could techincally be longer than the edge itself. This can be remedied with the following check:


if (lenOut > min(v1.len / 2, v2.len / 2)) {
  lenOut = min(v1.len / 2, v2.len / 2);
  cRadius = abs(lenOut * sin(halfAngle) / cos(halfAngle));
} else {
  cRadius = radius;
}

Once this is dealt with, we can calculate the coordinates of one of the tangetial points to the circle:

x = p2.x + v2.nx * lenOut;
y = p2.y + v2.ny * lenOut;

Then move along the perpendicular to find the circle center:

x += -v2.ny * cRadius * radDirection;
y += v2.nx * cRadius * radDirection;

Note that this also depends on the direction that we determined earlier.

The rendering context

For drawing purposes we will make use of the javascript canvas rendering context interface, which allows us to draw all sorts of shapes. You can find an extensive documentation here.

To do so we need to invoke the context, usually I do this in the setup function, as such:

function setup(){
    ctx = canvas.getContext('2d');
}

And then we can make use of it to draw stuff:

For our purposes we’ll only need to use one function, namely the ctx.arc() call:

ctx.arc(x, y, cRadius, v1.ang + Math.PI / 2 * radDirection, v2.ang - Math.PI / 2 * radDirection, drawDirection);

Where the first two parameters are the coordinates of the arc center, followed by the radius in third place, and the starting and end angle in fourth and fifth position. the last input specifies if this arc is drawn in clockwise or counter clockwise manner.

Drawing the final shape

The final shape will be drawn by looping through the set of points that make up the vertices of our polygon. Here’s a condensed version of this loop with the calculations omitted:

ctx.beginPath();
len = points.length;

// initial point is the last point of the shape
p1 = points[len - 1];
for (i = 0; i < len; i++) {
    p2 = points[(i) % len];
    p3 = points[(i + 1) % len];
    
    // Calculations go here
    
    // get the next set of points
    p1 = p2;
    p2 = p3;
}
ctx.closePath();
ctx.stroke() // add an outline to the shape
ctx.fill()   // add color to the shape

In this manner, the first point is actually the last vertex of the polygon. The final shape would then be drawn by first positioning all of your vertices, and storing them in an array, in the following manner:

vertices = []
vertices.push({x: coordX, y:coordY})
// add more vertices etc...

And then passing the array to the drawing function:

drawRoundPoly(ctx, vertices, radius)

The final snippet of code that you would then use, is the one provided by Blindman67. Here’s a minimal example:

Also notice that you can additionally pass a ‘radius’ to each individual vertex to override the main radius passed to the function call.

Further Improvements

First off, huge thanks to Dave and Clay from the birbsnest for the feedback! Thanks to Dave (who’s a freaking coding wizard), you’re getting three additional sections here, firstly we’ll update the method that we’ve discussed so far using the inbuilt p5 vector class and it’s functionalities, and secondly we’ll have a look at the solution Dave came up with for rounding off corners. He also shared a version using Bezier Curves!

Blindman67's method using p5 vectors

Rather than defining our own asVec() function, we can make use of the p5 vector class and the functions that come along with it. In that manner we declare our vector BA and BC like this:

p2 = points[i % len];
p3 = points[(i + 1) % len];

A = createVector(p1.x, p1.y);
B = createVector(p2.x, p2.y);
C = createVector(p3.x, p3.y);

BA = A.sub(B);
BC = C.sub(B);

Next we can compute the angle and the angle of the perpendicular in the following manner:

// need to call copy() because most vector functions are in-place
BAnorm = BA.copy().normalize();
BCnorm = BC.copy().normalize();

sinA = -BAnorm.dot(BCnorm.copy().rotate(PI / 2));
sinA90 = BAnorm.dot(BCnorm);
angle = asin(sinA);

Note that we have to call the copy() function prior to functions such as normalize() and rotate(), as they will mutate and alter the vector itself. Hence we create two normalized copies of BA and BC, since we’ll need to use their magnitudes later on again.

Also note how we’re now calculating the dot product rather than the cross product! It’s still the same calculation, but for convenience it’s easier to do it in that manner. This is derived from the fact that the dot product of two vectors is equal to the cross product of one of these vectors and the perpendicular to the other vector. So we simply rotate one of them by 90 degress and compute the dot product. Same for sinA90.

The rest of the code is identical to what we had before, with the exception that we’re solely using the p5 vector properties and functions:

This makes it a little more compact, but also less readable.

Dave's acceleration method

After asking for feedback on Raph’s discord and discussing the previous method a little, Dave pointed out that an alternative way to knowing the drawing order would be using the curvature vector’s direction. Rather than using the positions of BA and it’s perpepndicular with respect to BC, and doing this check:

(radDirection = 1), (drawDirection = false);
if (sinA90 < 0) {
  angle < 0 ? (angle += PI) : ((radDirection = -1), (drawDirection = true));
} else {
  angle > 0 ? ((radDirection = -1), (drawDirection = true)) : 0;
}

We can do this:

accelDir = BAnorm.copy().add(BCnorm)
radDirection = Math.sign(accelDir.dot(BCnorm.rotate(PI / 2)))
drawDirection = radDirection === -1

We obtain the curvature vector by adding BA and BC, and this vector will generally always point into the direction of the circlecenter. Now we only need to determine if we need to draw the arc in a clockwise or counterclockwise direction. For this we recycle our previous check and observe where the curvature vector falls with respect to BC. The drawing order can then be deduced from the arc direction!

Here’s a sketch where we visualize these curvature vectors:

Using Bezier vertices

And for the final alternative method, Dave wrote this method that relies on the bezierVertex() function in p5:

And that’s a wrap! If there are any unclear notions, mistakes or questions, feel free to leave me a comment or reach out to me on social media! If you find this post useful, consider supporting me by sharing it or following me on my social medias. Otherwise, cheers and happy sketching!

News and Updates

If you enjoyed this post, consider subscribing to my mailing list for the occasional update on new blog posts. No spam, promise. Otherwise come join me on Twitter!