How can I check if there is a black pixel in between two pixels of interest in Python?

Question

I have an image with a white background and black pixels which represent walls or boundaries. I want to know if there is a boundary between two points on the image.

The way I approached this was to find all integer points on the line between the two points of interest and check if any of these points were a black pixel. Here is what it looks like when I plot it (the blue circles show the two points of interest and the red dots are all the points passing through the line):

As you can see, it looks like the black line does not pass through one of the integer points that lie on the line between the points of interest. How do I find if a black line passes through a line between two points.

PS: I need to check this for a large number of pair of points and the image has many boundaries, so a time efficient algorithm would help.

You could flood-fill with another colour, say blue, starting at either point of interest with a flood-fill that cannot cross black. Then check if the other point of interest is touching any blue neighbours. — Mark Setchell
Or solve for the intersection of the two lines and see if it falls in the rectangle whose diagonally opposite corners are the two line endpoiints. — Mark Setchell

Captain Trojan Captain Trojan · Accepted Answer · 2021-03-15T23:00:14

You're looking for the supercover algorithm. See this link for the specific code.

Here's a solution written in 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;
}

How can I check if there is a black pixel in between two pixels of interest in Python?

1 Answers