求多个正方形组成多边形的轮廓？

Question

输入参数就是一个0 1的二维数组，会告诉哪些坐标是1，然后每个1当做是一个土地，会有四个顶点x,y x, y+1 x+1, y+1 x+1, y 。顺序输出描边的坐标

Answer 1

假设恰好有一个岛屿，岛屿中没有湖。

• 岛屿：由一个或多个土地相连组成
• 湖：在岛屿内部的水域且不和岛屿周围的水相连
• 水：值为 0 的格子或者网格外的区域

以上定义参考自岛屿的周长，你的图也是出自这里，不过问题不一样。

思路一

先遍历网格找到一个土地，从该土地左上角的点出发，沿着岛屿轮廓走一圈回到起点即可。
每一步，可以选择上下左右四个方向的网格线走，条件是这条网格线不是上一步走的网格线，且必须是轮廓线。
一条网格线是轮廓线，当且仅当网格线两侧一边是土地一边是水。

思路二

先遍历网格找到一个土地，从该土地左上角的点出发，顺时针沿着岛屿轮廓走一圈回到起点，保证土地始终在右侧。
每一步，可以选择左拐、直走或右拐，当左前方是土地时左拐，否则当右前方是土地时直走，否则右拐。

思路一的参考代码

const isLand = (g, x, y) => {
  return y >= 0 && x >= 0 && y < g.length && x < g[0].length && g[y][x];
};

const findLand = (g) => {
  for (let y = 0; y < g.length; ++y) {
    for (let x = 0; x < g[0].length; ++x) {
      if (g[y][x]) return [x, y];
    }
  }
  return [-1, -1];
};

const isOutline = (g, x, y, dx, dy) => {
  let x2, y2;
  if (dx == 0) {
    x2 = x - 1;
    y2 = y += dy >> 1;
  } else {
    x2 = x += dx >> 1;
    y2 = y - 1;
  }
  return isLand(g, x, y) != isLand(g, x2, y2);
};

const findOutline = (g) => {
  const res = [];
  const [fx, fy] = findLand(g);
  if (fx == -1) return res;
  res.push([fx, fy]);
  let [px, py, x, y, dx, dy] = [-1, -1, fx, fy, 1, 0];
  for (;;) {
    const [nx, ny] = [x + dx, y + dy];
    if (!(nx == px && ny == py) && isOutline(g, x, y, dx, dy)) {
      if (nx == fx && ny == fy) return res;
      [px, py, x, y] = [x, y, nx, ny];
      res.push([x, y]);
    } else {
      [dx, dy] = [-dy, dx];
    }
  }
};

console.log(
  findOutline([
    [0, 1, 0, 0],
    [1, 1, 1, 0],
    [0, 1, 0, 0],
    [1, 1, 0, 0],
  ])
);

[
  [ 1, 0 ], [ 2, 0 ],
  [ 2, 1 ], [ 3, 1 ],
  [ 3, 2 ], [ 2, 2 ],
  [ 2, 3 ], [ 2, 4 ],
  [ 1, 4 ], [ 0, 4 ],
  [ 0, 3 ], [ 1, 3 ],
  [ 1, 2 ], [ 0, 2 ],
  [ 0, 1 ], [ 1, 1 ]
]