LÖVE

Posted: **Tue Nov 22, 2022 1:07 pm**

Hello lovers

I come to you again because I'm a bit lost with the love.math.triangulate function.

If I understood correctly, to be able to triangulate a polygon with this function, the polygon must not be complex (it must not self-intersection). To prevent this I have three functions :

Code: Select all

local function linesIntersect(x1,y1, x2,y2, x3,y3, x4,y4)

    local dx1, dy1 = x2 - x1, y2 - y1
    local dx2, dy2 = x4 - x3, y4 - y3
    local dx3, dy3 = x1 - x3, y1 - y3
    local d = dx1*dy2 - dy1*dx2

    if d == 0 then return false end

    local t1 = (dx2*dy3 - dy2*dx3)/d
    if t1 < 0 or t1 > 1 then return false end

    local t2 = (dx1*dy3 - dy1*dx3)/d
    if t2 < 0 or t2 > 1 then return false end

    return true, x1 + t1*dx1, y1 + t1*dy1

end

local function isPolySimple(p)

    local len = #p

    for i = 1, len-1, 2 do

        local _i = i+2 < len and i+2 or 1

        local x1, y1 = p[i], p[i+1]
        local x2, y2 = p[_i], p[_i+1]

        for j = i+4, len-3, 2 do

            local _j = j+2 < len-2 and j+2 or 1

            local x3, y3 = p[j], p[j+1]
            local x4, y4 = p[_j], p[_j+1]

            if linesIntersect(
                x1,y1,x2,y2,
                x3,y3,x4,y4
            ) then
                return false
            end

        end

    end

    return true

end

local function getLinePolyIntersects(x1,y1,x2,y2,p)

    local ret = {}

    local clen = math.sqrt((x1-x2)^2+(y1-y2)^2)

    for i = 1, #p-1, 2 do

        local j = i+2 < #p and i+2 or 1

        local px1, py1 = p[i], p[i+1]
        local px2, py2 = p[j], p[j+1]

        if not (px2==x2 and py2==y2) then

            local isects, ix, iy = linesIntersect(x1,y1,x2,y2, px1,py1,px2,py2)

            if isects then

                local len =  math.sqrt((x1-ix)^2+(y1-iy)^2)

                if len > 0.1 and len < clen then
                    ret[#ret+1] = { len, ix,iy, px2,py2, j }
                end

            end

        end

    end

    table.sort(ret, function (a,b)
        return a[1] - b[1] ~= 0
    end)

    return ret

end

local function simplifyPoly(p)

    local cx, cy = p[1], p[2]   -- current point
    local nx, ny = p[3], p[4]   -- next point
    local ni = 3                -- next index

    local ret = {cx,cy}

    repeat

        local isects = getLinePolyIntersects(cx,cy,nx,ny,p)

        if #isects == 0 then

            ret[#ret+1] = nx
            ret[#ret+1] = ny
            cx, cy = nx, ny

            ni = ni+2 < #p and ni+2 or 1
            nx, ny = p[ni], p[ni+1]

        else

            local pts = isects[1]

            ret[#ret+1] = pts[2]
            ret[#ret+1] = pts[3]

            cx, cy = pts[2], pts[3]
            nx, ny, ni = pts[4], pts[5], pts[6]

        end

    until ni==1

    return ret

end

And I noticed that a polygon like this (for example) which is complex can be triangulated:

Code: Select all

{ 100,100, 200,100, 100,200, 200,200 }

Why ? Isn't the impossibility of triangulating a complex polygon systematic?

I also want to point out that I sometimes had an error when I wanted to triangulate a simple polygon which was detected as simple by my "isPolySimple" function, is it well written? I don't understand much anymore.

I am attaching a demo to show you that it is triangulable, also with the effect of simplification.

Edit: I simplified my post in case I gave too much info, anyone to answer me on this subject?

LÖVE

Question about love.math.triangulate and complex polygons

Question about love.math.triangulate and complex polygons