c++ - 如何在矩阵（坐标系）中找到对象表示的边界

Question

我在矩阵中有一个对象的足迹，简而言之，对象确实占据了哪些单元格（对象是一部分，标记为 0 的单元格未被占用，标记为 1 的单元格被对象占用）。然后，我有一个list<pair<int, int> >带有矩阵坐标的占用单元格列表。

如何找到属于该对象的该对象的所有边界单元格？（相邻的单元格是例如(x1, y1)和(x2, y2) if abs(x1-x2)<=1 && abs(y1-y2)<=1）。

0  0  0  0  0
0  0  1  1  0 
0  1  1  1  0 
0  1  1  1  0
0  0  1  0  0 

Answer 1

如果所有相邻像素都是 1，则将像素设置为 0。剩余的 1 位于边界上：

for (x = 1; x < width-1; ++x) {
  for (y = 1; y < height-1; ++y) {
    if (data(x+1,y) && data(x-1,y) && data(x,y+1) && data(x,y-1)) {
      data(x,y) = 0;
    }
  }
}

Answer 2

1. 首先，找到对象。可以使用洪水填充来完成。
2. (1) 中找到的所有单元格都是候选单元格，遍历所有候选单元格并产生具有一个或多个相邻单元格且值=0 的单元格。（或者如果它在矩阵的边缘）

---

一种可能的优化是仅“探索”具有相邻单元格的单元格，该单元格具有矩阵的 0/边缘。

Answer 3

使用边缘行走：定义一个 2x2 单元格的窗口并从对象外部的某个位置开始，例如在左上角。然后，根据窗口内看到的模式移动窗口：

0 0
0 0

-> 你仍然需要找到对象的边缘。向右移动两步；如果碰到右边缘，则向下移动两步并一直向左移动（一种行扫描）。

0 0
0 1

-> 向右移动一步。

0 0
1 1

-> 向右移动一步。

0 0
1 0

-> 下移一步。

0 1
0 1

-> 上移一步。

0 1
1 1

-> 上移一步。

等等

你以这种方式绕着边缘顺时针移动。你遇到的任何1都可以看作是物体的边缘部分；尽管您可以将上面最后一个示例中的右下角 1 视为不是边缘（这是定义问题）。

一旦你遇到你第一次碰到边缘的位置，你就完成了。

请注意以下可能需要特殊处理的极端情况（例如记住遇到过它）：

0 1
1 0