I recently wrote an algorithm to make rounded rectangles for a grid with “holes”. The goal was to ensure that all the convex corners of the grid sections were rounded. I looked at existing implementations in softwares that I use daily, the most used are code editors. One of my favorite text editors Zed, renders text selections with beautifully rounded convex and concave corners.

I couldn’t find a way to add external rounded corners without adding extra blocks at the beginning and end of each row, so decided to focus on internal corners, which led me to a somewhat elegant solution. The algorithm requires that I evaluate for each cell it’s neighboring cells, starting with the one to its left, and going clockwise at 45 degree increments. Here are the directions: [⇐, ⇖, ⇑, ⇗, ⇒, ⇘, ⇓, ⇙] For each corner I had to evaluate the three adjacent cells that it touches. Evaluating each corner cell clockwise staring from left-top makes it awkward as the last corner (left-bottom) requires that I look at the first direction (left) again. This would require array index shenanigans and I wanted to avoid that for the sake of obsession. However, if I duplicate the first direction at the end, it simplifies the code. The final directions array: [⇐, ⇖, ⇑, ⇗, ⇒, ⇘, ⇓, ⇙, ⇐] Now I can implement a sliding window of width three on top of this array which can account for all the corners.

Who drew the short stick?

A corner that touches three empty cells is rounded. Vice-versa an empty cell that touches three filled cells, is rounded. As I’m only concerned with the external rounding, I ended up ignoring the empty cell case.

Let’s look at an example:


       ┌───┬───┬───┬───┐
       │   │   │   │   │▐▌
       ├───┼───┼───┼───┤▐▌
       │   │ x │ x │   │▐▌
       ├───┼───┼───┼───┤▐▌
       │   │ x │ x │   │▐▌
       └───┴───┴───┴───┘▐▌
        ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▘

       ┌───┬───┬───┬───┐
       │   │   │   │   │▐▌
       ├── ╭───┬───╮ ──┤▐▌
       │   │ x │ x │   │▐▌
       ├── ├───┼───┤ ──┤▐▌
       │   │ x │ x │   │▐▌
       └── ╰───┴───╯ ──┘▐▌
        ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▘

        // Expected outcome

Evaluating the cell marked with *, xs are filled, and _s are empty.

By looking at the rectangle I can deduce that * should have the left top corner rounded and nothing else.


       ┌───┬───┬───┬───┐
       │ _ │ _ │ _ │ _ │▐▌
       ├── ╭───┬───┼───┤▐▌
       │ _ │ * │ x │ _ │▐▌
       ├── ├───┼───┼───┤▐▌
       │ _ │ x │ x │ _ │▐▌
       └───┴───┴───┴───┘▐▌
        ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▘

Dry running the algorithm for the top left corner, I start by checking the cell to the left, then the one to the left and above, and then finally the one above.


       ┌───┬───┬───┬───┐
       │ 2 │ 3 │ _ │ _ │▐▌
       ├───┼───┼───┼───┤▐▌
       │ 1 │ * │ x │ _ │▐▌
       ├───┼───┼───┼───┤▐▌
       │ _ │ x │ x │ _ │▐▌
       └───┴───┴───┴───┘▐▌
        ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▘

As I was evaluating a filled cell, and all the neighboring cells for the left top corner are empty, I can mark the corner as rounded.

Let’s look at a more complicated example:


       ┌───┬───┬───┬───┐
       │ x │ _ │ _ │ _ │▐▌
       ├───┼───┼───┼───┤▐▌
       │ _ │ x │ x │ _ │▐▌
       ├───┼───┼───┼───┤▐▌
       │ _ │ x │ x │ _ │▐▌
       └───┴───┴───┴───┘▐▌
        ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▘

For ths particular case, all the corners except the corner that’s common between the large and the small rectangle should be rounded. The clockwise sweeping algorithm is a generalized solution and works fine for this case.

Expected Outcome:


       ╭───╮ ──┬───┬───┐
       │ x │   │   │   │▐▌
       ╰───┼───┬───╮ ──┤▐▌
       │   │ x │ x │   │▐▌
       ├── ├───┼───┤ ──┤▐▌
       │   │ x │ x │   │▐▌
       └── ╰───┴───╯ ──┘▐▌
        ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▘

Let’s look at the cell marked with *, starting with the top left corner:


     2   3
      →┌───┬───┬───┬───┐
     1 │ * │ _ │ _ │ _ │▐▌
       ├───┼───┼───┼───┤▐▌
       │ _ │ x │ x │ _ │▐▌
       ├───┼───┼───┼───┤▐▌
       │ _ │ x │ x │ _ │▐▌
       └───┴───┴───┴───┘▐▌
        ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▘

As the three relevant adjacent cells are out of bounds, I can mark the corner rounded.

Let’s look at the top right corner:


           ↓
       ╭───┬───┬───┬───┐
       │ * │ _ │ _ │ _ │▐▌
       ├───┼───┼───┼───┤▐▌
       │ _ │ x │ x │ _ │▐▌
       ├───┼───┼───┼───┤▐▌
       │ _ │ x │ x │ _ │▐▌
       └───┴───┴───┴───┘▐▌
        ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▘

The first two adjacent cells are out-of-bounds and hence considered empty. The last one is actually empty, I can mark that corner rounded.


         1 ↓ 2
       ╭───┬───┬───┬───┐
       │ * │ _ │ _ │ _ │▐▌
       ├───┼───┼───┼───┤▐▌
       │ _ │ x │ x │ _ │▐▌
       ├───┼───┼───┼───┤▐▌
       │ _ │ x │ x │ _ │▐▌
       └───┴───┴───┴───┘▐▌
        ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▘
        // 1 and 2 are out-of-bounds

           ↓
       ╭───┬───┬───┬───┐
       │ * │ 3 │ _ │ _ │▐▌
       ├───┼───┼───┼───┤▐▌
       │ _ │ x │ x │ _ │▐▌
       ├───┼───┼───┼───┤▐▌
       │ _ │ x │ x │ _ │▐▌
       └───┴───┴───┴───┘▐▌
        ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▘
        // 3 is empty

           ↓
       ╭───╮ ──┬───┬───┐
       │ * │ 3 │ _ │ _ │▐▌
       ├───┼───┼───┼───┤▐▌
       │ _ │ x │ x │ _ │▐▌
       ├───┼───┼───┼───┤▐▌
       │ _ │ x │ x │ _ │▐▌
       └───┴───┴───┴───┘▐▌
        ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▘
        // rounded corner

Let’s look at the bottom right corner.


       ╭───╮ ──┬───┬───┐
       │ * │ 1 │ _ │ _ │▐▌
       ├ → ┼───┼───┼───┤▐▌
       │ 3 │ 2 │ x │ _ │▐▌
       ├───┼───┼───┼───┤▐▌
       │ _ │ x │ x │ _ │▐▌
       └───┴───┴───┴───┘▐▌
        ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▘

As the cells marked 1 and 3 are empty but cell 2 is not, this corner can’t be rounded.

Last corner:


       ╭───╮ ──┬───┬───┐
     3 │ * │ _ │ _ │ _ │▐▌
      →├───┼───┼───┼───┤▐▌
     2 │ 1 │ x │ x │ _ │▐▌
       ├───┼───┼───┼───┤▐▌
       │ _ │ x │ x │ _ │▐▌
       └───┴───┴───┴───┘▐▌
        ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▘

As all the relevant cells are either empty or out of bounds, this corner can be marked as rounded similar to the right top corner.

Outcome:


       ╭───╮ ──┬───┬───┐
       │ * │ _ │ _ │ _ │▐▌
       ╰───┼───┼───┼───┤▐▌
       │ 1 │ x │ x │ _ │▐▌
       ├───┼───┼───┼───┤▐▌
       │ _ │ x │ x │ _ │▐▌
       └───┴───┴───┴───┘▐▌
        ▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▘

In practice


const DIRECTION_DELTAS = [
// ⇐        ⇖         ⇑        ⇗        ⇒       ⇘       ⇓       ⇙        ⇐
  [-1, 0], [-1, -1], [0, -1], [1, -1], [1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0],
] as const;

/**
 * Grid can be represented as a string: "x____xx__xx_"
 * and width.
 * or formatted as
 * `
 * x___
 * _xx_
 * _xx_
 * '
 */

const isEmpty = (char: string) => char === '_';

const getCornerRounding = (
  str: string,
  width: number,
  currIdx: Vec2,
): readonly [boolean, boolean, boolean, boolean] => {
	const isCurrentEmpty = isEmpty(str[currIdx]);

  // get indices of the cells to evaluate
  const surroundingIndices = DIRECTION_DELTAS.map(([dX, dY]) => {
    // ...
  });

  const isNeighborEmpty = (directionIdx: number) => {
    const neighboringIdx = surroundingIndices[directionIdx];
    return isEmpty(str[neighboringIdx]);
  };

  const directionsForTopLeft = [0, 1, 2];
  const directionsForTopRight = [2, 3, 4];
  const directionsForBottomRight = [4, 5, 6];
  const directionsForBottomLeft = [6, 7, 8];

  return [
    directionsForTopLeft
        .map(isNeighborEmpty)
        // check if the neighbors are different from the current cell
        .every(isEmpty !== isCurrentCellEmpty),
    // ...
  ] as const;
};

Q: Can this use a compute shader to find the solution much faster?

I think so.