Issue with Polygon Triangulation

I’ve looked through numerous implementations of Polygon Triangulation, and I can’t seem to find a solution that doesn’t run in to this issue.

I’m not entirely sure how I could go about fixing it, all earclipping methods seem to run in to the problem as well, images below can be seen of what the issue is.

As you can see, when doing a ninety degree turn, like you can see above, the triangle ear clipping ignores the node, which normally would be okay, however for my case, it’s not.

I’ve looked through numerous implementations, and can’t see to find a solution for this.

local TriangleAlignments = {}

function TriangleAlignments:GetPointInFront(point, listOfPoints)
	if point == #listOfPoints then
		return listOfPoints[1]
	else
		return listOfPoints[point+1]
	end
end

function TriangleAlignments:GetPointBehind(point, listOfPoints)
	if point == 1 then
		return listOfPoints[#listOfPoints]
	else
		return listOfPoints[point-1]
	end
end

function TriangleAlignments:IsPointConvex(behind, point, infront, previousDirection)
	local v1 = point - behind
	local v2 = infront - point

	local crossproduct = v2:Cross(v1)
	local currentDirection

	if crossproduct.Y > 0 then
		currentDirection = 1
	else
		currentDirection = -1
	end
	return currentDirection ~= previousDirection
end

function TriangleAlignments:GetAreaOfTriangle(A, B, C)
	local BA = A - B
	local CA = C - B

	return (BA:Cross(CA).magnitude/2)
end

function TriangleAlignments:GetEarOfPolygon(points, direction)
	local i = 1
	local earFound = false
	local newTable

	local triangles = {}

	while not earFound and i <= #points do
		local point = points[i]
		local A, B, C = self:GetPointBehind(i, points), point, self:GetPointInFront(i, points)
		if self:IsPointConvex(A,B,C, direction) then
			local contained = false
			for x,v in pairs(points) do
				if v ~= A and v ~= B and v ~= C then
					local a1,a2,a3 = self:GetAreaOfTriangle(A, B, v), self:GetAreaOfTriangle(A, C, v), self:GetAreaOfTriangle(B, C, v)
					if a1 + a2 + a3 == self:GetAreaOfTriangle(A, B, C) then
						contained = true
					end
				end
			end				

			if not contained then
				earFound, newTable = point, {}
				table.insert(triangles, {A, B, C})
				for x,v in pairs(points) do
					if v ~= point then
						table.insert(newTable, v)
					end
				end
			end
		end
		i += 1
	end
	return earFound, newTable, triangles
end

function TriangleAlignments:TriangulatePolygon(points)
	local newTable = points
	local done, triangle, triangles = false, nil, {}	
	while #newTable > 2 do
		done, newTable, triangle = self:GetEarOfPolygon(newTable, -1)
		table.insert(triangles, triangle[1])
		
		if not newTable then break end
	end
	
	return triangles
end

function TriangleAlignments:DrawPointTriangle(a, b, c, thickness, wedge)
	local ab, ac, bc = b - a, c - a, c - b;
	local abd, acd, bcd = ab:Dot(ab), ac:Dot(ac), bc:Dot(bc);

	if (abd > acd and abd > bcd) then
		c, a = a, c;
	elseif (acd > bcd and acd > abd) then
		a, b = b, a;
	end

	ab, ac, bc = b - a, c - a, c - b;

	local right = ac:Cross(ab).unit;
	local up = bc:Cross(right).unit;
	local back = bc.unit;

	local height = math.abs(ab:Dot(up));

	local w1 = wedge:Clone();
	w1.Size = Vector3.new(thickness, height, math.abs(ab:Dot(back)));
	w1.CFrame = CFrame.fromMatrix((a + b)/2, right, up, back);
	--w1.Parent = parent;

	local w2 = wedge:Clone();
	w2.Size = Vector3.new(thickness, height, math.abs(ac:Dot(back)));
	w2.CFrame = CFrame.fromMatrix((a + c)/2, -right, up, -back);
	--w2.Parent = parent;

	return w1, w2;
end

return TriangleAlignments

My code can be found above, any help is much appreciated!

A note, all of my points are ordered properly.

2 Likes

Attempted to do implementations of Delaunay triangulation, while the end product makes the triangles, sadly the product is the same.

If anyone has any ideas, let me know!

1 Like

It’s pretty late for me right now so I can’t go into too much detail, but from some quick surfing it seems like there are a couple variations of the algorithm you listed. Have you been checking to make sure that you’re using one that is specifically marked as working on concave shapes to generate concave shaped triangulations?

I see some notes about modifications to it that allow it to work with concave shapes, and other notes about variations that are specifically for generating convex hulls of concave shapes, which is what your picture shows.

I can return to this problem to help out later, but I might need to do a bit of research on the widely known algorithms first. I have written a concave mesh decomposition algorithm, but it was with a custom proprietary solution, and it was unfortunately in a professional company setting so I don’t think I have the rights to just post the solution here. I also think it would also be more helpful if I could help you with a standard one rather than one that no one has really heard of, and probably has performance issues in comparison.

Sources where I saw mentions of concave vs convex hull decompositions:

Mention of convex hull from concave shape:

Mention of concave shape outputs:
c# - Concave Mesh Triangulation With Known Boundary - Stack Overflow (in the replies to main post)
c# - Use Constraint delaunay triangulation to Triangulate a Polygon - Stack Overflow (potential mentioned solution, again in the replies of the main post)

3 Likes

It seems that you need an algorithm that supports concave polygon triangulation as @MettaurSp pointed out.

I found this resource on GitHub. It is an implementation of Delaunay Triangulation that has a certain property that might help.

-- @field convexMultiplier multiplier heuristic for bounding triangle calculation.
-- When small (~1) produces convex-hull, when large, produces concave hulls.
-- Defaults to 1000.

This multiplier might help you to generate a concave polygon. I have not looked into the technical details of how this multiplier works, but maybe it is worth giving a try.

1 Like

I ended up finding a source which handles both Convex & Concave triangles- the primary issue I had before was my sources didn’t support concave triangles.

The source is built off of love, the LUA library, and is mainly for two dimensional use, which isn’t an issue in my case.

@Brickman808 The resource you sent was the implementation I posted in the reply above, sadly it didn’t function as intended.

Feel free to check out this resource, which I’ve found to work in this case.

With a few tweaks, I was able to make it work as intended, yay.

5 Likes

LGTM, maybe the triangulation algorithm would be nice to have as a Wally package.

1 Like

I’ve never heard of Wally packages, I’ll need to look in to those, thanks!

Also, if you, or anyone else is curious in the end product-

3 Likes

Ayyy, glad to see that you found it! Nice work!