Algorithm to draw outline in a colored region

Question

Suppose I have a image like this:

Each square is a pixel. They are white or red.

I want to draw a green outline around the red region given an outline width w.

I tried some algorithms but the result isn't looking good, the diagonals look strange and don't reflect the original image:

What approach should I use to get a smoother and better result with a good performance?

For simplicity, suppose I have a point p that belongs to the boundary.

Answer 1

Your green outline shows the pixels that are <= w pixels away from the red ones, as measured using manhattan distance.

You want the pixels that are <= w pixels away from the red ones, as measured using Euclidean distance.

It's a little tricky, but you can actually do this in linear (O(width*height)) time.

PASS1: make a new matrix M[y][x] gives the vertical distance from (x,y) to a red pixel, or w+1 if the distance is more than w. You can do this in linear time by scanning up and then down through each column.

PASS2: scan from left to right in each row. Where M[y][x] <= w, you can color pixel (x,y) green, along with the sqrt(w²-M[y][x]²) pixels to the right. remember how far right you've colored, and avoid recoloring pixels you've already done, so this process will take linear time, too. Do the same thing scanning from right to left.

Make a lookup table for sqrt(w²-M[y][x]²) to avoid calculating it all the time.

Since @iAmOren was nice enough to provide working JS, I will blatantly copy that and fix it to use the faster algorithm:

var matrix=[
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
];


function createMatrixDivs() {
  for(var r=0; r<16; r++) {
    for(var c=0; c<16; c++) {
      var cell=document.createElement("div");
      cell.style="border:1px solid blue;position:absolute;width:10px;height:10px;left:"+10*c+"px;top:"+10*r+"px;";
      cell.id=r+","+c;
      document.body.append(cell);
    }
  }
}

function drawMatrixDivs() {
  for(var r=0; r<16; r++) {
    for(var c=0; c<16; c++) {
      document.getElementById(r+","+c).style.backgroundColor=(matrix[r][c]==0?"white":matrix[r][c]==1?"red":matrix[r][c]==2?"green":"gray");
    }
  }
}

function outline(w) {
  var M = matrix.map(function(row) {
    return row.slice();
  });
  var x,y,d,i,s,e;

  //PASS 1 - put vertical distances in M

  for(x=0; x<16; x++) {
    d=w+1;
    for(y=0; y<16; y++) {
      if (matrix[y][x]==1) {
        d=0;
      } else if (d<=w) {
        ++d;
      }
      M[y][x]=d;
    }
    d=w+1;
    for(y=15; y>=0; y--) {
      if (matrix[y][x]==1) {
        d=0;
      } else if (d<=w) {
        ++d;
      }
      if (M[y][x] > d) {
        M[y][x] = d;
      }
    }
  }

  // Precalculate vertical distance -> horizontal span
  var spans=[];
  for (i=0; i<=w; ++i) {
    spans[i] = Math.sqrt((w+0.3)*(w+0.3) - i*i)|0;
  }

  // PASS 2 fill every pixel within w

  for(y=0; y<16; y++) {
    e=-1;
    for (x=0; x<16; ++x) {
      d = M[y][x];
      if (d<=w) {
        s=Math.max(x,e);
        e=Math.max(e,x+spans[d]);
        for(; s<=e && s<16; ++s) {
          matrix[y][s] = matrix[y][s]||2;
        }
      }
    }
    e=17;
    for (x=15; x>=0; --x) {
      d = M[y][x];
      if (d<=w) {
        s=Math.min(x,e);
        e=Math.min(e,x-spans[d]);
        for(; s>=e && s>0; --s) {
          matrix[y][s] = matrix[y][s]||2;
        }
      }
    }
  }
  drawMatrixDivs();
}
createMatrixDivs();
drawMatrixDivs();
outline(+prompt("Enter outline width: "));