How can I remove unnecessary vertices from wall edges?

Question

I've got a pretty simple tile based 2d top-down map with an array of walls. In order to figure where to cast light and shadows, I've generated an array of vertex coordinates along the walls like so:

The blue points I'd like to keep while removing the green points. How can I check if a point should be kept or removed?

Answer 1

Instead of guiding a wall-following algorithm along the wall tiles, which is a method that probably would have worked, I decided to solve this problem by finding the line segments that make up the edge of the walls instead.

Here is the code I ended up writing!

For reference, "colmap" refers to the array of walls. colmap[y][x] returns the tile value. My tiles are 8x8 pixels, which is why some vectors are being multiplied by 8.

// find wall vertices

// first, get the edges of walls in lines
let lines = [];
let overlaps = function(l) {
  for (let i in lines) {
    let line = lines[i];

    if (
      line.a.x == l.a.x &&
      line.a.y == l.a.y &&
      line.b.x == l.b.x &&
      line.b.y == l.b.y
    ) {
      return true
    }
  }
  return false
};
let lineAngle = function(cx, cy, ex, ey) {
  var dy = ey - cy;
  var dx = ex - cx;
  var theta = Math.atan2(dy, dx);
  theta *= 180 / Math.PI;
  return theta;
};
for (let y=0; y<this.colmap.length; y++) {
  for (let x=0; x<this.colmap[y].length; x++) {
    if (this.colmap[y][x] != "wall") continue;

    let tx = x*8;
    let ty = y*8;

    let line;

    // 4 lines for each wall tile
    // top
    if (y > 0 && this.colmap[y-1][x] != "wall") {
      line = {
        a: { x: tx, y: ty },
        b: { x: tx+8, y: ty },
        angle: lineAngle(tx, ty, tx+8, ty)
      };
      if (!overlaps(line)) lines.push(line);
    }
    // right
    if (x+1 < this.colmap[y].length && this.colmap[y][x+1] != "wall") {
      line = {
        a: { x: tx+8, y: ty },
        b: { x: tx+8, y: ty+8 },
        angle: lineAngle(tx+8, ty, tx+8, ty+8)
      };
      if (!overlaps(line)) lines.push(line);
    }
    // bottom
    if (
      x+1 < this.colmap[y].length &&
      y+1 < this.colmap.length &&
      this.colmap[y+1][x] != "wall"
    ) {
      line = {
        a: { x: tx, y: ty+8 },
        b: { x: tx+8, y: ty+8 },
        angle: lineAngle(tx, ty+8, tx+8, ty+8)
      };
      if (!overlaps(line)) lines.push(line);
    }
    // left
    if (x > 0 && this.colmap[y][x-1] != "wall") {
      line = {
        a: { x: tx, y: ty },
        b: { x: tx, y: ty+8 },
        angle: lineAngle(tx, ty, tx, ty+8)
      };
      if (!overlaps(line)) lines.push(line);
    }
  }
}

// second, consolidate lines that connect and have the same angle
for (let i=lines.length-1; i>0; i--) {
  let l = lines[i];
  for (let x in lines) {
    let n = lines[x];

    if (
      l.a.x == n.b.x &&
      l.a.y == n.b.y &&
      l.angle == n.angle
    ) {
      n.b = { x: l.b.x, y: l.b.y };
      lines.splice(i, 1);
    } 
  }
}

// lastly, generate vertices from the lines!
let verts = [];
overlaps = function(v) {
  for (let i in verts) {
    let n = verts[i];
    if (v.x == n.x && v.y == n.y) {
      return true
    }
    return false
  }
};
for (let i in lines) {
  let l = lines[i];
  let v = { x: l.a.x, y: l.a.y };
  if (!overlaps(v)) verts.push(v);
  v = { x: l.b.x, y: l.b.y };
  if (!overlaps(v)) verts.push(v);
}

this.vertices = verts;