算法 - 给定一组带坐标的像素，如何有效地找到所有连续的线？

Question

我正在使用挤压函数创建一个给定 2D 纹理及其厚度的网格。

示例：

我已经通过简单地寻找边缘附近或透明像素附近的像素来找到纹理的轮廓。它甚至对凹形（甜甜圈形）形状也很有效，但现在我只剩下一组轮廓像素。

结果如下：

问题是这些值从左上到右下排序，不适合构建实际的 3D 轮廓。

我目前的想法是：

步骤 1.

从索引[0]开始，查看与起点不同的最近连续点的右侧。

如果找到，将其移动到另一个数组中。
没有的话就往下看。继续，直到到达起点。

步骤2.

从数组中保留的像素中选择另一个像素（如果有）。

从第 1 步开始重复。

这在我看来是可行的，但似乎效率很低。通过研究，我发现了 Moore-Neighbor 跟踪算法，但我无法在任何地方找到它适用于凸形的示例。

有什么想法吗？

Answer 1

算法循环像素，我们只检查每个像素一次，跳过空单元格，并将其存储在列表中，因为不会有重复项。

isEmpty 实现取决于透明度在您的情况下如何工作，如果某种颜色被认为是透明的，下面是我们有 alpha 通道的情况。

阈值是表示单元格被视为非空的最低可见度的 alpha 级别。

isBorder 将检查是否有任何 Moore 邻居为空，在这种情况下它是一个边界单元格，否则它不是因为它被填充单元格包围。

isEmpty(x,y): image[x,y].alpha <= threshold

isBorder(x,y)
:   if isEmpty(x  , y-1): return true
:   if isEmpty(x  , y+1): return true
:   if isEmpty(x-1, y  ): return true
:   if isEmpty(x+1, y  ): return true
:   if isEmpty(x-1, y-1): return true
:   if isEmpty(x-1, y+1): return true
:   if isEmpty(x+1, y-1): return true
:   if isEmpty(x+1, y+1): return true
:   otherwise: return false

getBorderCellList()
:   l = empty-list
:   for x in 0..image.width
:   : for y in 0..image.height
:   : : if !isEmpty(x,y)
:   : : : if isBorder(x,y)
:   : : : : l.add(x,y)
:   return l

优化您可以通过预先计算的 boolean e[image.width][image.height] 来优化它，其中 e[x,y] = 1 如果 image[x,y] 不为空，则使用它直接检查，如 isBorder(x,y): e[x-1,y] | e[x+1,y] | .. | e[x+1,y+1].

init()
:   for x in 0..image.width
:   : for y in 0..image.height
:   : : e[x,y] = isEmpty(x,y)

isEmpty(x,y): image[x,y].alpha <= threshold

isBorder(x,y): e[x-1,y] | e[x+1,y] | .. | e[x+1,y+1]

getBorderCellList()
:   l = empty-list
:   for x in 0..image.width
:   : for y in 0..image.height
:   : : if not e[x,y]
:   : : : if isBorder(x,y)
:   : : : : l.add(x,y)
:   return l

Answer 2

最后我也找到了自己的答案，所以在这里分享一下：

找到给定图像的轮廓后（使用每个像素的 alpha 值），像素将按行排序，有利于绘制它们但不利于构建网格。

那么，下一步就是寻找连续的线条。这是通过首先检查找到的像素是否有任何邻居优先考虑top/left/right/bottom（否则它将跳过角落）来完成的。

继续，直到原始数组中没有像素。

这是实际的实现（对于 Babylon.js 但这个想法适用于任何其他引擎）：

游乐场：https://www.babylonjs-playground.com/#9GPMUY#11

var GetTextureOutline = function (data, keepOutline, keepOtherPixels) {
    var not_outline = [];
    var pixels_list = [];
    for (var j = 0; j < data.length; j = j + 4) {
        var alpha = data[j + 3];
        var current_alpha_index = j + 3;
        // Not Invisible
        if (alpha != 0) {
            var top_alpha = data[current_alpha_index - (canvasWidth * 4)];
            var bottom_alpha = data[current_alpha_index + (canvasWidth * 4)];
            var left_alpha = data[current_alpha_index - 4];
            var right_alpha = data[current_alpha_index + 4];

            if ((top_alpha === undefined || top_alpha == 0) ||
                (bottom_alpha === undefined || bottom_alpha == 0) ||
                (left_alpha === undefined || left_alpha == 0) ||
                (right_alpha === undefined || right_alpha == 0)) {
                pixels_list.push({
                    x: (j / 4) % canvasWidth,
                    y: parseInt((j / 4) / canvasWidth),
                    color: new BABYLON.Color3(data[j] / 255, data[j + 1] / 255, data[j + 2] / 255),
                    alpha: data[j + 3] / 255
                });

                if (!keepOutline) {
                    data[j] = 255;
                    data[j + 1] = 0;
                    data[j + 2] = 255;
                }
            } else if (!keepOtherPixels) {
                not_outline.push(j);
            }
        }

    }

    // Remove not-outline pixels
    for (var i = 0; i < not_outline.length; i++) {
        if (!keepOtherPixels) {
            data[not_outline[i]] = 0;
            data[not_outline[i] + 1] = 0;
            data[not_outline[i] + 2] = 0;
            data[not_outline[i] + 3] = 0;
        }
    }


    return pixels_list;
}

var ExtractLinesFromPixelsList = function (pixelsList, sortPixels) {
    if (sortPixels) {
        // Sort pixelsList
        function sortY(a, b) {
            if (a.y == b.y) return a.x - b.x;
            return a.y - b.y;
        }
        pixelsList.sort(sortY);
    }

    var lines = [];
    var line = [];
    var pixelAdded = true;
    var skipDiagonals = true;
    line.push(pixelsList[0]);
    pixelsList.splice(0, 1);

    var countPixels = 0;
    while (pixelsList.length != 0) {
        if (!pixelAdded && !skipDiagonals) {
            lines.push(line);
            line = [];
            line.push(pixelsList[0]);
            pixelsList.splice(0, 1);
        } else if (!pixelAdded) {
            skipDiagonals = false;
        }

        pixelAdded = false;
        for (var i = 0; i < pixelsList.length; i++) {
            if ((skipDiagonals && (
                line[line.length - 1].x + 1 == pixelsList[i].x && line[line.length - 1].y == pixelsList[i].y ||
                line[line.length - 1].x - 1 == pixelsList[i].x && line[line.length - 1].y == pixelsList[i].y ||
                line[line.length - 1].x == pixelsList[i].x && line[line.length - 1].y + 1 == pixelsList[i].y ||
                line[line.length - 1].x == pixelsList[i].x && line[line.length - 1].y - 1 == pixelsList[i].y)) || (!skipDiagonals && (
                    line[line.length - 1].x + 1 == pixelsList[i].x && line[line.length - 1].y + 1 == pixelsList[i].y ||
                    line[line.length - 1].x + 1 == pixelsList[i].x && line[line.length - 1].y - 1 == pixelsList[i].y ||
                    line[line.length - 1].x - 1 == pixelsList[i].x && line[line.length - 1].y + 1 == pixelsList[i].y ||
                    line[line.length - 1].x - 1 == pixelsList[i].x && line[line.length - 1].y - 1 == pixelsList[i].y
                ))) {
                line.push(pixelsList[i]);
                pixelsList.splice(i, 1);
                i--;
                pixelAdded = true;
                skipDiagonals = true;
            }
        }


    }
    lines.push(line);
    return lines;
}

算法 - 给定一组带坐标的像素，如何有效地找到所有连续的线？

Algorithm - Given a set of pixels with coordinates, how to find all the contiguous lines in an efficient way?

algorithm

2d

pixels

outline