algorithm - 对于矩阵中的所有标记区域，找到它们的顶点进行绘制

Question

我正在寻找一种算法来获取在 3d 应用程序中绘制矩阵的标记区域所需的数据。

输入看起来像这样:

对于每个区域，我需要按 CCW 顺序找到其外边界的顶点。我已经可以通过查看邻居来找到所有水平或垂直边缘的顶点，但我的实现是从左到右、从上到下而不是按 CCW 顺序找到顶点。这是我的代码。

for (int i = 1; i < columns-1; i++)
    for (int j = 1; j < rows - 1; j++) {
        if (grid[i][j] > 0) { // not background
            if ((grid[i + 1][j] != id) && (grid[i][j - 1] != id)) {
                getCellTopLeftCoord(i, j, &x, &y);
                polyPath[id]->Add(gcnew mPoint(x + width, y));
            }
            if ((grid[i - 1][j] != id) && (grid[i][j - 1] != id)) {
                getCellTopLeftCoord(i, j, &x, &y);
                polyPath[id]->Add(gcnew mPoint(x, y));
            }
            ... // etc..

以下是我感兴趣的边界:

Answer 1

如果没有任何带有重复标签的未连接表面，则以下过程应该有效:

• 从上到下，从左到右遍历矩阵。如果您遇到带有您尚未处理的标签的非空单元格，请为该标签创建路径。

• 您找到的点一定是东北角。把那一点放在你的道路上。

• 现在创建一个方向列表并从向南走开始。因为你是逆时针沿着边界走的，所以你应该总是在左边有一个被占用的单元格，在右边有一个未被占用的单元格。 (这里被占用指的是一个带有所需标签的单元格。)

• 当您尝试寻找下一个方向时，请继续朝上一个方向前进并检查左右两侧的单元格。如果两者都无人居住，请向左转。如果至少右边的那个被占用，请右转。否则，直接继续。

• 当您改变方向时，将当前点附加到您的路径。

• 根据当前方向更新坐标。重复直到到达原始坐标。

此方法不会为您提供草图中标记为 4 的区域周围的对角线；它将遵循轴对齐的锯齿状轮廓。

这是 Javascript 中的示例实现。单元格数据包含在二维数组 m 中。 cell 查找一个单元格，但考虑到越界查找。 path 创建单个标签的路径。 paths 创建一个路径列表；它调用 path:

function cell(x, y) {
    if (y < 0) return 0;
    if (y >= m.length) return 0;

    if (x < 0) return 0;
    if (x >= m[y].length) return 0;

    return m[y][x];
}

function path(x, y, c) {
    var x0 = x;
    var y0 = y;

    var res = [{x: x, y: y}];
    var dir = "s";

    var l, r;

    y++;

    while (x != x0 || y != y0) {
        var old = dir;

        switch (dir) {
        case "n":   l = (cell(x - 1, y - 1) == c) ? 1 : 0;
                    r = (cell(x, y - 1) == c) ? 2 : 0;
                    dir = ["w", "n", "e", "e"][l + r];
                    break;

        case "e":   l = (cell(x, y - 1) == c) ? 1 : 0;
                    r = (cell(x, y) == c) ? 2 : 0;
                    dir = ["n", "e", "s", "s"][l + r];
                    break;

        case "s":   l = (cell(x, y) == c) ? 1 : 0;
                    r = (cell(x - 1, y) == c) ? 2 : 0;
                    dir = ["e", "s", "w", "w"][l + r];
                    break;

        case "w":   l = (cell(x - 1, y) == c) ? 1 : 0;
                    r = (cell(x - 1, y - 1) == c) ? 2 : 0;
                    dir = ["s", "w", "n", "n"][l + r];
                    break;
        }

        if (dir != old) res.push({x: x, y: y});

        switch (dir) {
        case "n":   y--; break;
        case "e":   x++; break;
        case "s":   y++; break;
        case "w":   x--; break;
        }
    }

    return res;
}

function paths() {
    var res = {};

    for (var y = 0; y < m.length; y++) {
        for (var x = 0; x < m[y].length; x++) {
            var c = m[y][x];

            if (c && !(c in res)) {
                res[c] = path(x, y, c);
            }
        }
    }

    return res;
}