Return pixels in polygon

[Chief]

I've got a humongous problem!

I need a function that returns the pixels that are located within an area of 4 points (not just a rectangular area),
example:

Just for examples sake, we make the screen 16x16:


We choose 4 points:


And then to return the pixels inside the polygon (table).

Any suggestions?

EDIT:
Im making a game which has to select a group of grids to display on the screen. The grid is isometric, so i need to choose grids inside a rotated rectangle.

[vrld]

You can do it with a scan/sweep line algorithm:

The scanline is a vertical line that moves to the right scanning the interior. Initialize it with the x-coordinate of the leftmost point.
Repeat until you hit the rightmost point:
Find the intersections points of the shapes outer segments with the scanline.
Determine the maximum and minimum y-coordinate of these intersection points.
Add pixels with x-coordinates of the scanline and y-coordinates between the max/min to the pixel list.
Move the scanline one pixel to the right.

In (untested) code:

Code: Select all

-- get the y-coordinate of the intersection of a vertical line and a segment
function intersect(x, x1,y1, x2,y2)
    -- assuming x2 and x1 are different:
    local t = (x - x1) / (x2 - x1)
    if t >= 0 and t <= 1 then
        return y1 + t * (y1 - y1)
    end
    return nil -- explicit nil
end

-- x1,y1, ..., x4,y4 are integer coordinates of the bounding points
function inside_pixels(x1,y1, x2,y2, x3,y3, x4,y4)
    local rightmost = math.max(x1,x2,x3,x4)
    local leftmost = math.min(x1,x2,x3,x4)
    local pixels = {}
    for x = leftmost, rightmost do
        local i1 = intersect(x, x1,y1, x2,y2)
        local i2 = intersect(x, x2,y2, x3,y3)
        local i3 = intersect(x, x3,y3, x4,y4)
        local i4 = intersect(x, x4,y4, x1,y1)
        -- this wont work, you need to account for nil values here
        local y_upper, y_lower = math.min(i1,i2,i3,i4), math.max(i1,i2,i3,i4)
        for y = y_lower,y_upper do
            pixels[#pixels+1] = {x, y}
        end
    end
    return pixels
end

This algorithm will work with any convex polygon, not just with a tetragon. Welcome to computational geometry.