A way to fill a polygon with the lowest possible number of rectangles

[Duugu]

Well, I know this forum is not about graphics programming ... and the topic is not even wow-specific (at least not right now *g*).
But, I've searched for hours now and I can't figure out how to do it. So, I'm just hoping that there's someone out here, who knows a way or at least has an idea where to search for it.

I am looking for a fast way to fill a polygon (non-convex, no intersections) with the lowest possible number of rectangles.

Any idea anyone?

[semlar]

Do you mean triangles? Rectangles can't fill arbitrary polygons.

[Duugu]

No. I mean rectangles. Of variable sizes of course. (smallest ones of 1x1 units)

I would like to fill a polygon ingame. So I can't use triangles.

[semlar]

Originally Posted by Duugu I would like to fill a polygon ingame. So I can't use triangles.

Of course you can, just make a half transparent texture and skew it..

[Duugu]

Ehm. So, you use Settexcoords to rotate/modify the triangle texture to the required shape?
I don't get it. Maybe I'm a bit slow today.

[semlar]

The only addon examples for this that I can think of off the top of my head are AVR, which used triangles to draw shapes, and QuestHelper, which used triangles to fill quest blobs on the map.

I think they started with a right triangle with 1 pixel of transparency along the edges and used SetTexCoord to skew it into the desired format.

I don't have a polygon triangulation formula for you to start with since it wasn't necessary for what I was doing, but you should be able to get an idea from looking at those addons.

[Duugu]

I've peeked into the AVR code. I'll triangulate the polygon and use DrawTriangle from AVR as a black box.

Thank you so much for pushing me in this direction Semlar.

[Duugu]

Ok, the triangulation part is done ... but ...

I'm again in a need of something to fill a polygon with rectangles.
This time I would like to fill a polygon with secure buttons - which surly can't be done with triangles.

Any thoughts?


[e]
As building this was no fun: if someone ever has to triangulate a polygon in lua, here's the code (it's a simple ear clipping approach).
Triangulate() expects a table containing a sorted list of verticles data (n tables with x and y values) and returns a table containing n tables with triangle data (point 1, 2, 3 each containing a index number from the verticle table that was passed to the function).
Verticle list can be clockWise or anti-clockwise. Works with convex and concave polygons. Does not work with self intersecting polygons or polygons with holes.
No optimization right now. Could surly be faster.

function IntersectionPoint(x1, y1, x2, y2, x3, y3, x4, y4)
    if x1 and y1 and x2 and y2 and x3 and y3 and x4 and y4 then
        local d = ((y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1))
        local Ua
        local Ub 
        if d ~= 0 then
            Ua = ((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3)) / d
            Ub = ((x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3)) / d
        end 
        if Ua and Ub then
            if Ua >= -0.0 and Ua <= 1.0 and Ub >= -0.0 and Ub <= 1.0 then
                x = x1 + Ua * (x2 - x1)
                y = y1 + Ua * (y2 - y1)
                return math.floor(x), math.floor(y), Ua
            end
        end
    end
end       
 
function LineCenter(sx, sy, ex, ey)
    return (sx + ex) * 0.5, (sy + ey ) * 0.5
end
 
function InPolygon(pMeshVerticles, a, b)
    local count = 0
    for x = 1, table.getn(pMeshVerticles) do
        local s, e = x, x + 1
        if s < 1 then s = table.getn(pMeshVerticles) end
        if e > table.getn(pMeshVerticles) then e = 1 end
        if  ((a.x ~= pMeshVerticles[s].x and a.y ~= pMeshVerticles[s].y)  and (b.x ~= pMeshVerticles[e].x and b.y ~= pMeshVerticles[e].y)) and ((b.x ~= pMeshVerticles[s].x and b.y ~= pMeshVerticles[s].y) and (a.x ~= pMeshVerticles[e].x and a.y ~= pMeshVerticles[e].y)) then
            if IntersectionPoint(a.x, a.y, b.x, b.y, pMeshVerticles[s].x, pMeshVerticles[s].y, pMeshVerticles[e].x, pMeshVerticles[e].y) then
                count = count + 1
            end
        end
    end
    if count > 0 then
        return false
    else
        count = 0
        local ax, ay = LineCenter(a.x, a.y, b.x, b.y)
        if not ax and ay then print("!!! FAIL") return false end
 
        for x = 1, getn(pMeshVerticles) do
            local s, e = x, x + 1
            if s < 1 then s = getn(pMeshVerticles) end
            if e > getn(pMeshVerticles) then e = 1 end
            if IntersectionPoint(ax, ay, 5000, 5000, pMeshVerticles[s].x, pMeshVerticles[s].y, pMeshVerticles[e].x, pMeshVerticles[e].y) then
                count = count + 1
            end
        end
        local _, b = math.modf(count / 2)
        if b > 0 then
            return true
        else
            return false
        end
    end
 
    return false
end
 
function Triangulate(pMeshVerticles)
    local tTriangles = {}
    local currentVerticle
 
    local tMaxY = -10000
    for x = 1, table.getn(pMeshVerticles) do
        if pMeshVerticles[x].y > tMaxY then
            currentVerticle = x 
            tMaxY = pMeshVerticles[x].y
        end
        if x == 1 then
            pMeshVerticles[x].prev = table.getn(pMeshVerticles)
            pMeshVerticles[x].next = x + 1
        elseif x == table.getn(pMeshVerticles) then
            pMeshVerticles[x].prev = x - 1
            pMeshVerticles[x].next = 1
        else
            pMeshVerticles[x].prev = x - 1
            pMeshVerticles[x].next = x + 1
        end
        pMeshVerticles[x].out = false
    end
    
    if not currentVerticle then print("!!! FAIL") return end
 
    local tFailCounter = 0
    local tTriCounter = 0
    local numberPointsLeft = table.getn(pMeshVerticles)
    while numberPointsLeft >= 3 do
        if InPolygon(pMeshVerticles, pMeshVerticles[pMeshVerticles[currentVerticle].prev], pMeshVerticles[pMeshVerticles[currentVerticle].next]) == true then
            insert(tTriangles, {
                [1] = pMeshVerticles[currentVerticle].prev, 
                [2] = currentVerticle, 
                [3] = pMeshVerticles[currentVerticle].next
                })
            tTriCounter = tTriCounter + 1
            pMeshVerticles[pMeshVerticles[currentVerticle].prev].next = pMeshVerticles[currentVerticle].next
            pMeshVerticles[pMeshVerticles[currentVerticle].next].prev = pMeshVerticles[currentVerticle].prev
            pMeshVerticles[currentVerticle].out = true
            currentVerticle = pMeshVerticles[currentVerticle].next
            numberPointsLeft = numberPointsLeft -1
        else
            currentVerticle = pMeshVerticles[currentVerticle].next
        end
        tFailCounter = tFailCounter + 1
        if tFailCounter > table.getn(pMeshVerticles) * 3 then 
            print("FAIL: ", tFailCounter)
            print("currentVerticle:", currentVerticle, "prev:", pMeshVerticles[currentVerticle].prev, "next: ", pMeshVerticles[currentVerticle].next)
            return
        end
    end
 
    return tTriangles
end