I have spend the last few day trying to figure out how to fill a polygon with triangles. With the help of google and a lot of ChatGPT I figured it out. All the results I found online didn’t quite do what I wanted. Since this even handles concave polygons, enjoy 
.
Final product
explorer layout
main script
local Polygon = require(script.Parent.PolygonToTriangle)
local makeTriangle = require(script.Parent.MakeTriangle)
local vertices = {}
for i, newVertice in pairs(workspace.ExampleNodes:GetChildren()) do
table.insert(vertices, Vector2.new(newVertice.Position.X, newVertice.Position.Z))
end
local polygon = Polygon.new(unpack(vertices))
local triangles = polygon:GetTriangles()
for i, triangle in ipairs(triangles) do
print(triangle)
local a = Vector3.new(triangle[1].X, 0, triangle[1].Y)
local b = Vector3.new(triangle[2].X, 0, triangle[2].Y)
local c = Vector3.new(triangle[3].X, 0, triangle[3].Y)
makeTriangle(a, b, c)
end
PolygonToTriangle script
local Polygon = {}
Polygon.__index = Polygon
function Polygon.new(...)
local vertices = { ... }
local obj = setmetatable({}, Polygon)
obj.vertices = toVertexList(vertices)
return obj
end
function Polygon:IsConvex()
if #self.vertices == 3 then
return true
end
if not ccw(self.vertices[#self.vertices], self.vertices[1], self.vertices[2]) then
return false
end
for i = 2, #self.vertices - 1 do
if ccw(self.vertices[i - 1], self.vertices[i], self.vertices[i + 1]) then
return false
end
end
return true
end
function Polygon:GetTriangles()
local triangles = {}
local vertices = self.vertices
while #vertices >= 3 do
local earIndex = findEar(vertices)
local triangle = {
vertices[(earIndex - 2) % #vertices + 1],
vertices[earIndex],
vertices[(earIndex % #vertices) + 1]
}
table.insert(triangles, triangle)
table.remove(vertices, earIndex)
end
return triangles
end
--------------------------------------------------------------
-- Helper functions
--------------------------------------------------------------
function toVertexList(vertices)
local result = {}
for i = 1, #vertices do
if typeof(vertices[i]) == "Vector2" then
result[#result + 1] = vertices[i]
elseif typeof(vertices[i]) == "table" then
result[#result + 1] = Vector2.new(vertices[i][1], vertices[i][2])
end
end
return result
end
function ccw(p1, p2, p3)
return (p2.X - p1.X) * (p3.Y - p1.Y) - (p2.Y - p1.Y) * (p3.X - p1.X) > 0
end
function sortVerticesCounterclockwise(vertices)
local center = Vector2.new(0, 0)
for i = 1, #vertices do
center = center + vertices[i]
end
center = center / #vertices
table.sort(vertices, function(a, b)
local angleA = math.atan2(a.Y - center.Y, a.X - center.X)
local angleB = math.atan2(b.Y - center.Y, b.X - center.X)
return angleA < angleB
end)
end
function isEar(vertex, prevVertex, nextVertex, vertices)
for i, v in ipairs(vertices) do
if v ~= vertex and v ~= prevVertex and v ~= nextVertex then
if pointInTriangle(vertex, prevVertex, nextVertex, v) then
return false
end
end
end
return true
end
function findEar(vertices)
sortVerticesCounterclockwise(vertices)
local count = #vertices
for i = 1, count do
local prevIndex = (i - 2 + count) % count + 1
local nextIndex = i % count + 1
local prevVertex = vertices[prevIndex]
local vertex = vertices[i]
local nextVertex = vertices[nextIndex]
if isEar(vertex, prevVertex, nextVertex, vertices) then
return i
end
end
end
function pointInTriangle(p, p0, p1, p2)
local area = 0.5 * (-p1.Y * p2.X + p0.Y * (-p1.X + p2.X) + p0.X * (p1.Y - p2.Y) + p1.X * p2.Y)
local s = 1 / (2 * area) * (p0.Y * p2.X - p0.X * p2.Y + (p2.Y - p0.Y) * p.X + (p0.X - p2.X) * p.Y)
local t = 1 / (2 * area) * (p0.X * p1.Y - p0.Y * p1.X + (p0.Y - p1.Y) * p.X + (p1.X - p0.X) * p.Y)
return s > 0 and t > 0 and 1 - s - t > 0
end
return Polygon
MakeTriangle script
--credit Okeanskiy
local workspace = workspace
local abs = math.abs
local cfFromMatrix = CFrame.fromMatrix
local newV3 = Vector3.new
local WEDGE = Instance.new("WedgePart")
WEDGE.Anchored = true
WEDGE.TopSurface = Enum.SurfaceType.Smooth
WEDGE.BottomSurface = Enum.SurfaceType.Smooth
WEDGE.CastShadow = false
return function (a, b, c)
a,b,c = a, b, c
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 = abs(ab:Dot(up))
local w1 = WEDGE:Clone()
w1.Size = newV3(0, height, abs(ab:Dot(back)))
w1.CFrame = cfFromMatrix((a + b)/2, right, up, back)
w1.Parent = workspace.GeneratedTerrain
local w2 = WEDGE:Clone()
w2.Size = newV3(0, height, abs(ac:Dot(back)))
w2.CFrame = cfFromMatrix((a + c)/2, -right, up, -back)
w2.Parent = workspace.GeneratedTerrain
return w1, w2
end
