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.
