Finding all pixels at least partially within an arbitrarily oriented rectangle

Question

I have a rectangle with real-valued vertices (x0,y0), (x1,y1), (x2,y2), (x3,y3), which may be oriented at any angle in the plane. I'm looking for an efficient way of finding (or iterating over) all pixels (i.e., 1x1 squares) which are at least partially within this rectangle.

It's trivial to do this for rectangles which are oriented orthogonally, and it's also trivial to check whether any particular pixel is within the rectangle. I could check each pixel within the rectangle's bounding box, but in the worst case I would be checking O(n^2) pixels when only O(n) will be within the target rectangle. (This is when the target rectangle is at 45 degrees and is very long and narrow.)

Answer 1

You can compute the range in the x-direction (floor of the minimum x-coordinate, to the ceiling of the maximum x-coordinate). For each x in that range, you can compute the range in the y-direction. You have a few different cases to consider in the generic case, depending on how the rectangle is oriented.

In essence, you have one leftmost point, one rightmost point, one upper point and one lower point. y1 will start at the leftmost, go trough the lower, and end in the rightmost point. y2 will instead go trough the upper point.

To include all touching pixels, we need to look half a pixel in all directions. I chose to use the center of each pixel as the coordinates. This was so that you get a more natural look of the final image.

Here are some F#-code to demonstrate:

let plot_rectangle p0 p1 p2 p3 =
    seq {
        // sort by x-coordinate
        let points = List.sortBy fst [p0; p1; p2; p3]
        let pLeft, pMid1, pMid2, pRight =
            points.[0], points.[1], points.[2], points.[3]

        // sort 2 middle points by y-coordinate
        let points = List.sortBy snd [pMid1; pMid2]
        let pBottom, pTop = points.[0], points.[1]

        // Easier access to the coordinates
        let pLeftX, pLeftY = pLeft
        let pRightX, pRightY = pRight
        let pBottomX, pBottomY = pBottom
        let pTopX, pTopY = pTop
        let pMid1X, pMid1Y = pMid1
        let pMid2X, pMid2Y = pMid2

        // Function: Get the minimum Y for a given X
        let getMinY x0 y0 x1 y1 x =
            let slope = (y1 - y0)/(x1 - x0)
            // Step half a pixel left or right, but not too far
            if slope >= 0.0 then
                let xl = max x0 (x - 0.5)
                y0 + slope * (xl - x0)
                |> round
                |> int
            else
                let xr = min x1 (x + 0.5)
                y0 + slope * (xr - x0)
                |> round
                |> int

        // Function: Get the maximum Y for a given X
        let getMaxY x0 y0 x1 y1 x =
            let slope = (y1 - y0)/(x1 - x0)
            // Step half a pixel left or right, but not too far
            if slope >= 0.0 then
                let xr = min x1 (x + 0.5)
                y0 + slope * (xr - x0)
                |> round
                |> int
            else
                let xl = max x0 (x - 0.5)
                y0 + slope * (xl - x0)
                |> round
                |> int

        let x1 = int (pLeftX + 0.5)
        let x2 = int (pRightX + 0.5)
        for x = x1 to x2 do
            let xf = float x
            if xf < pMid1X then
                // Phase I: Left to Top and Bottom
                // Line from pLeft to pBottom
                let y1 = getMinY pLeftX pLeftY pBottomX pBottomY xf
                // Line from pLeft to pTop
                let y2 = getMaxY pLeftX pLeftY pTopX pTopY xf
                for y = y1 to y2 do
                    yield (x, y)

            elif xf < pMid2X && pMid1Y < pMid2Y then
                // Phase IIa: left/bottom --> top/right
                // Line from pBottom to pRight
                let y1 = getMinY pBottomX pBottomY pRightX pRightY xf
                // Line from pLeft to pTop (still)
                let y2 = getMaxY pLeftX pLeftY pTopX pTopY xf
                for y = y1 to y2 do
                    yield (x, y)

            elif xf < pMid2X && pMid1Y >= pMid2Y then
                // Phase IIb: left/top --> bottom/right
                // Line from pLeft to pBottom (still)
                let y1 = getMinY pLeftX pLeftY pBottomX pBottomY xf
                // Line from pTop to pRight
                let y2 = getMaxY pTopX pTopY pRightX pRightY xf
                for y = y1 to y2 do
                    yield (x, y)

            else
                // Phase III: bottom/top --> right
                // Line from pBottom to pRight
                let y1 = getMinY pBottomX pBottomY pRightX pRightY xf
                // Line from pTop to pRight
                let y2 = getMaxY pTopX pTopY pRightX pRightY xf
                for y = y1 to y2 do
                    yield (x, y)
    }

Example: