Polygon to Triangles

I have spend the last few days 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 :smile:.

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
15 Likes

i recognize this legend but i think you meant “okeanskiy”?

i have tried to do this as well but i ended up giving up after 5 minutes :ok_hand:

1 Like

thank you, I didn’t realize this. let the legend live on.

2 Likes


it doesnt works on some polygons like this… :pensive:

1 Like

yeah I realized this after posting, I ended up rewriting this from scratch and it works, due to increased popularity/competition I don’t want to share that result, I hope you understand :slight_smile: good luck with whatever you are trying todo.

1 Like

!amazing work

keep going what you do, the script is amazing and clean