LÖVE

Code: Select all

local ccw = function(a,b,c)
    return (b[1] - a[1]) * (c[2] - a[2]) > (b[2] - a[2]) * (c[1] - a[1])
end

local convexHull = function(pl)
    if #pl == 0 then return {} end

    table.sort(pl, function(left,right)
        return left[1] < right[1]
    end)

    local h = {}

    -- lower hull
    for i,pt in pairs(pl) do
        while #h >= 2 and not ccw(h[#h-1], h[#h], pt) do
            table.remove(h,#h)
        end
        table.insert(h,pt)
    end

    -- upper hull
    local t = #h + 1
    for i=#pl, 1, -1 do
        local pt = pl[i]
        while #h >= t and not ccw(h[#h-1], h[#h], pt) do
            table.remove(h,#h)
        end
        table.insert(h,pt)
    end

    table.remove(h,#h)

    return h
end

return convexHull

Code: Select all

local path = ...
local alphaShape = {}

alphaShape.delaunay = require(path.."/delaunay")
alphaShape.getConvexHull = require(path.."/convexHull")

local Point = alphaShape.delaunay.Point

local addEdge = function(edge_points, points, edges, i, j)

    -- Add a line between the i-th and j-th points, if not in the list already

    for _, v in pairs(edges) do
        if v[1] == i and v[2] == j
        or v[1] == j and v[2] == i
        then return end -- already added
    end

    table.insert(edge_points, points[i])
    table.insert(edge_points, points[j])
    table.insert(edges, {i, j})

end

alphaShape.getConcaveHull = function(points, alpha)

    --[[
        Compute the alpha shape (concave hull) of a set of points.

        @param points: Iterable container of points.
        @param alpha: alpha value to influence the gooeyness of the border. Smaller
                        numbers don't fall inward as much as larger numbers. Too large,
                        and you lose everything!
    ]]

    if #points < 4 then -- When you have a triangle, there is no sense in computing an alpha shape.
        return alphaShape.getConvexHull(points)
    end

    local coords = {}
    for _, point in pairs(points) do
        table.insert(coords, Point(point[1], point[2]))
    end

    local triangles = alphaShape.delaunay.triangulate(unpack(coords))

    local edge_points, edges = {}, {}

    -- Loop over triangles: ia, ib, ic = indices of corner points of the triangle

    for _, tri in pairs(triangles) do

        local ia = tri.p1.id
        local ib = tri.p2.id
        local ic = tri.p3.id

        local pa = points[ia] -- or : {tri.p1.x, tri.p1.y}
        local pb = points[ib]
        local pc = points[ic]

        -- Computing radius of triangle circumcircle
        local a = math.sqrt((pa[1] - pb[1]) ^ 2 + (pa[2] - pb[2]) ^ 2)
        local b = math.sqrt((pb[1] - pc[1]) ^ 2 + (pb[2] - pc[2]) ^ 2)
        local c = math.sqrt((pc[1] - pa[1]) ^ 2 + (pc[2] - pa[2]) ^ 2)

        local s = (a + b + c) / 2.0
        local area = math.sqrt(s * (s - a) * (s - b) * (s - c))
        local circum_r = a * b * c / (4.0 * area)

        if circum_r < alpha then
            addEdge(edge_points, points, edges, ia, ib)
            addEdge(edge_points, points, edges, ib, ic)
            addEdge(edge_points, points, edges, ic, ia)
        end

    end

    return edge_points, edges

end

return alphaShape

Code: Select all

            local newZoneVerts = {}

            for i = 1, self.zone:getVertexCount() do -- Get previous polygon
                local x, y = self.zone:getVertex(i)
                table.insert(newZoneVerts, {x, y})
            end

            for _, v in pairs(self.snakeVerts) do -- Add new polygon
                x, y = v[1] - self.ozone.x, v[2] - self.ozone.y
                table.insert(newZoneVerts, {x, y})
            end