python-3.x - 如何检查 Python 中两个感兴趣的像素之间是否有黑色像素？

Question

我有一个白色背景和黑色像素的图像，代表墙壁或边界。我想知道图像上两点之间是否有边界。

我解决这个问题的方法是在两个兴趣点之间的线上找到所有整数点，并检查这些点是否是黑色像素。这是我绘制它时的样子（蓝色圆圈表示两个兴趣点，红点是通过线的所有点）：

如您所见，黑线似乎没有通过位于兴趣点之间的线上的整数点之一。如何查找黑线是否穿过两点之间的线。

PS：我需要检查大量的点对并且图像有很多边界，所以一个省时的算法会有所帮助。

标签： python-3.xmatplotlibimage-processing

Answer 1

您正在寻找超级覆盖算法。具体代码见此链接。

这是一个用javascript编写的解决方案：

function supercover_line(p0, p1) {
    let dx = p1.x-p0.x, dy = p1.y-p0.y;
    let nx = Math.abs(dx), ny = Math.abs(dy);
    let sign_x = dx > 0? 1 : -1, sign_y = dy > 0? 1 : -1;

    let p = new Point(p0.x, p0.y);
    let points = [new Point(p.x, p.y)];
    for (let ix = 0, iy = 0; ix < nx || iy < ny;) {
        let decision = (1 + 2*ix) * ny - (1 + 2*iy) * nx;
        if (decision === 0) {
            // next step is diagonal
            p.x += sign_x;
            p.y += sign_y;
            ix++;
            iy++;
       } else if (decision < 0) {
            // next step is horizontal
            p.x += sign_x;
            ix++;
        } else {
            // next step is vertical
            p.y += sign_y;
            iy++;
        }
        points.push(new Point(p.x, p.y));
    }
    return points;
}