[SOLVED] Concave hull algorithm in lua

[Bigfoot71]

Hello everyone !

I am looking for (if it already exists) an algorithm to obtain the concave envelope of a polygon, I explain myself: I have two lists of vertices that I "merge" to give a single polygon, the problem is that a number of the vertices are inside this polygon which causes problems, so I managed to find an algorithm (based on Graham's scan) which I adapted a bit to retrieve a convex hull of the polygon , here it is :

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

But I can't find an already existing module (or other) in Lua to get a concave envelope, I saw that there were modules like alphashape in Python and a lot of other projects that seem to do it in Javascript / C++ / C# / Java. Does this already exist in Lua?

If not, I'll share my progress on this subject or if I manage to re-write one in Lua, but if it already exists I don't really want to reinvent the wheel

[darkfrei]

https://rosettacode.org/wiki/Convex_hull

[Bigfoot71]

https://rosettacode.org/wiki/Convex_hull

Yes this is where the piece of code that I presented originally comes from but it only serves to render only a convex shape and not concave as I explained.

[Bigfoot71]

Small update

I tried to take inspiration from this gist on GitHub: https://gist.github.com/dwyerk/10561690
And using this Lua adaptation of the Delaunay triangulation to replace the Python module scipy.spatial.Delaunay: https://github.com/Yonaba/delaunay

I also reused the script from my first post if the number of points given is less than 4.

Here's where I'm at so far, but it's not working:

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

The problem is that the condition 'if circum_r < alpha then' is never true because 'circum_r' is always greater than +/- 100x the 'alpha' value (which equals 0.4 in my tests).

I'm still working on it, if anyone has any suggestions I'm all ears !

[pgimeno]

How do you define the concave hull?

[Bigfoot71]

How do you define the concave hull?

This image shows very well what I would like:


My problem, in details, is that first I have a list of vertices that represents an area (a polygon) and to enlarge this area I have another list of vertices that I merge with the first one, all like this :

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

The problem is that some of the vertices of the first list are inside the new polygon, which unnecessarily weighs it down and causes me collision problems, so I first used the function I've shown in the first post but it only returns convex shapes (as shown in the image with the blue segment) while I want to get a concave shape as shown with the red segments in the image.

[darkfrei]

It looks that you need to define the largest distance between vertices or subdivide one concave polygon to several convex and than after hulling merge the polygons to the big concave polygon.

[pgimeno]

How do you define the concave hull?

This image shows very well what I would like:

No it doesn't.

What makes that one more correct than for example this one?



There are many possible concave hulls. The convex hull (which is unique) is one possible hull; any other hull is concave. What requisites does a concave hull need to meet, to be considered "correct" for your purpose?

[Bigfoot71]

What makes that one more correct than for example this one?

I agree that nothing makes it more correct than another objectively but this can be regulated by the alpha value given for example for the alphashape module in Python.

There are many possible concave hulls. The convex hull (which is unique) is one possible hull; any other hull is concave. What requisites does a concave hull need to meet, to be considered "correct" for your purpose?

To be more precise, in my case, the list of vertices that is added to the first corresponds to a succession of player position between the moment he left the zone and the moment he re-entered it. The edges of the shape would therefore have to follow exactly the path taken by the player.


Here's a capture of what I'm doing if I'm not clear enough: https://streamable.com/keqktq (sorry for the sprite, I put one quickly to make it prettier but it failed)

[darkfrei]

I've made the Areas from loop-erased random walk
https://youtu.be/5NE5RIeeMXI

So when your path cross itself, it creates the filed area.

Here you are need to make a new polygon and fill the area of it after the loop was closed and then merge it with the old polygon.

Update
See
viewtopic.php?p=203623&sid=b16f9d821753 ... 1a#p203623

Update 2
https://sean.cm/a/polygon-clipping-pt1