[SOLVED] Concave hull algorithm in lua

[pgimeno]

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.

Okay, so what you actually want is the union of two polygons. Google that and you'll find answers.

[Bigfoot71]

Thank you very much for your help, to be able to properly merge the two polygons I found a function that could have done it properly in the Lua HC module (HC.polygon - https://github.com/vrld/HC/blob/master/polygon.lua)

I therefore recovered the two functions mergedWith() and getSharedEdge() which I adapted as follows:

Code: Select all

local getSharedEdge = function(p,q)
	local pindex = setmetatable({}, {__index = function(t,k)
		local s = {}
		t[k] = s
		return s
	end})

	for i = 1,#p do
		pindex[p[i][1]][p[i][2]] = i
	end

	local i,k = #q,1
	for k = 1,#q do
		local v,w = q[i], q[k]
		if pindex[v[1]][v[2]] and pindex[w[1]][w[2]] then
			return pindex[w[1]][w[2]], k
		end
		i = k
	end
end

local mergePolygons = function(poly1, poly2)
	local p,q = getSharedEdge(poly1, poly2)
	assert(p and q, "Polygons do not share an edge")

	local ret = {}
	for i = 1,p-1 do
		ret[#ret+1] = {poly1[i][1], poly1[i][2]}
	end

	for i = 0,#poly2-2 do
		i = ((i-1 + q) % #poly2) + 1
		ret[#ret+1] = {poly2[i][1], poly2[i][2]}
	end

	for i = p+1,#poly1 do
		ret[#ret+1] = {poly1[i][1], poly1[i][2]}
	end

	return ret
end

return mergePolygons

But it still fails when calling getSharedEdge() because it doesn't find any shared edge...
I'm still thinking about it, I tried a lot of other things but I always end up with points inside the polygon which causes me collision problems.
I'm thinking of directly using HC.polygon because maybe I'm adapting it badly...

Update:

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

I hadn't seen this answer, so I tried to adapt it for "mesh vertices" but without success, so I then abandoned the idea of ​​using meshes, I rewrote everything to display the polygons with love.graphics.polygon() and be able to use the mentioned library directly. I first tried using polybool() which sometimes works and other times not...

Code: Select all

self.zone = polybool(self.zone, self.snakeVerts, "or")

'Error: Number of vertex components must be a multiple of two'

I also tried the "and" and "not" arguments but I still got the error above.

And using the polygon.concaveHull() function:

Code: Select all

for _, p in pairs(self.snakeVerts) do
    table.insert(self.zone, p)
end

self.zone = polygon.concaveHull(0.5, self.zone)

'Error: Need at least three vertices to draw a polygon'

Then testing the function polygon.convexHull() I noticed that it didn't really work, it removes pieces of the polygon for no reason...

I'm still looking for a solution...

[pgimeno]

I found this: https://stackoverflow.com/questions/266 ... x-polygons

I think it could help.

[Bigfoot71]

I finally found the solution!

Already I realized at the end that my meshes could not be displayed in a "concave way", so I solved the problem temporarily by displaying polygon triangulations.

Then I also noticed that polybool(pl1, pl2, "or") (coming from the library proposed by darkfrei - https://github.com/AlexarJING/polygon/) could return tables so I found a way to determine the right table to keep by comparing their number of elements. I then had to make a few other changes to avoid polygon triangulation issues.

Here is the code I use to be able to unite the two polygons (without the optimizations for the triangulation because it depends on the case):

Code: Select all

self.zone.polygon = polybool(self.zone.polygon, self.snakeVerts, "or")

-- If the first element is a table, we select the longest one

if type(self.zone.polygon[1]) == "table" then

    if #self.zone.polygon > 1 then
        local longest, length = 1, #self.zone.polygon[1]
        for i=2, #self.zone.polygon do
            if type(self.zone.polygon[i]) == "table"
            and #self.zone.polygon[i] > length then
                longest, length = i, #self.zone.polygon[i]
            end
        end
        self.zone.polygon = self.zone.polygon[longest]
    else
        self.zone.polygon = self.zone.polygon[1]
    end

end

self.zone.triangles = love.math.triangulate(self.zone.polygon)

And to display all that, of course:

Code: Select all

 for _, tri in pairs(self.zone.triangles) do
    lg.polygon("fill", tri)
end

It is very surely optimizable I have just written it.

Briefly, regarding optimizations for triangulation, in my case I simply set as the first points of the path drawn by the player to be the center of the nearest triangle and made sure that the first position given (and the last) by the player are well inside the polygon, for the moment with that everything is fine!

Thank you very much again for your help, I don't know if I would have succeeded without you! Love on you