The algorithm that 1waffle1 described above is referred to as ‘ear clipping’ for polygon triangulation.
There’s some instructive information here: https://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf
3 Likes
This is a very good solution, i’m just having trouble determining whether the midpoint is inside the polygon. How do I differentiate between two cases like this, for example?
thanks i will read this, i’ll probably just figure out the answer to my question above ^^
Hmm I’m still struggling to find a way to find if an angle is <180 or >180 in relation to the shape. From there, I will do the ear clipping but avoid reflex angles like #1 in my last example
Any help on this would be appreciated!
Have you tried checking if there is a line created by those points by seeing if point[i-1] (or i+1) is connected to that one
here’s some code for this in another public thread
7 Likes
Thanks so much!
After about an hour of fixing bugs, I finally got it working perfectly with the help of your functions! Its also working really fast, I just need to limit the number of nodes the user can place down. And for nonsimple shapes I’m probably just going to fill the polygon using my original code, which will never error
Although I did have a bit of trouble with your CreatePolygonFromPoints function, I don’t think it was working correctly because for me it always created an extra table index, with a next and a previous, but with no position. (e.g. a square would create 5 polygon point tables and the last one didn’t have a position)
I made a fix for this:
3 Likes
Code was untested, updated it to fix that
local function CreatePolygonFromPoints(Points)
local Polygon = {Position = Points[1]}
local First = Polygon
for i = 2, #Points do
Polygon.Next = {Previous = Polygon, Position = Points[i]}
Polygon = Polygon.Next
end
Polygon.Next, First.Previous = First, Polygon
return First
end
3 Likes
This doesn’t work for me 
local function CreatePolygonFromPoints(Points)
local Polygon = {Position = Points[1]}
local First = Polygon
for i = 2, #Points do
Polygon.Next = {Previous = Polygon, Position = Points[i]}
Polygon = Polygon.Next
end
Polygon.Next, First.Previous = First, Polygon
return First
end
local Vectors = {}
for i, v in pairs(PlayersPlot.CameraPart.Floor:GetChildren()) do
table.insert(Vectors, v.Position)
end
CreatePolygonFromPoints(Vectors) -- 'Vectors' contains 4 Vector3's
I’m not sure what you expect to happen, this just creates a data structure that represents the array of polygon vertices as a circular doubly linked list. Just saying it doesn’t work doesn’t tell me anything.
Oh, how do I create the polygon tho?
I think that was already covered in the rest of this thread.
@NinjoOnline I managed to create a fully working system for this. If you need help, let me know how far you are with it. I started with making a script which makes fills a triangle using 2 right-angled triangles (wedge parts)
All I managed to get was the player to place down the nodes 
haven’t figured out how to even go about following the area in between.
Edit - upon reading through this and using it’s scripts and plonking it into my code, I got so close 
Even though it does kinda create everything from each node, I want the shape be shaped around the nodes, instead of just having sharp edges jotting out
Needless to say, I got no clue how the code works 
But it comes so close to working
Here’s the code, not really that helpful tbh cause I can’t explain what any of it does
local CreateFloor = {}
function GetPointInFront(point, listOfPoints)
if point == #listOfPoints then
return listOfPoints[1]
else
return listOfPoints[point+1]
end
end
function GetPointBehind(point, listOfPoints)
if point == 1 then
return listOfPoints[#listOfPoints]
else
if point == 4 then
print("______")
print(listOfPoints[point-1])
end
return listOfPoints[point-1]
end
end
function IsPointConvex(behind, point, infront, previousDirection)
local v1 = point.Position - behind.Position
local v2 = infront.Position - point.Position
local crossproduct = v2:Cross(v1)
local currentDirection
if crossproduct.Y > 0 then
currentDirection = 1
else
currentDirection = -1
end
return currentDirection ~= previousDirection
end
function GetAreaOfTriangle(A, B, C)
local BA = A.Position - B.Position
local CA = C.Position - B.Position
return (BA:Cross(CA).magnitude/2)
end
function GetEarOfPolygon(parts, direction, folder)
local i = 1
local earFound = false
local newTable
while not earFound and i <= #parts do wait()
local point = parts[i]
local A, B, C = GetPointBehind(i, parts), point, GetPointInFront(i, parts)
if IsPointConvex(A,B,C, direction) then
-- Check no parts contained within this triangle now
local contained = false
for x,v in pairs(parts) do
if v ~= A and v ~= B and v ~= C then
-- check if this triangle contains any stray verticles. If so, can't do anything :(
local a1,a2,a3 = GetAreaOfTriangle(A, B, v), GetAreaOfTriangle(A, C, v), GetAreaOfTriangle(B, C, v)
if a1 + a2 + a3 == GetAreaOfTriangle(A, B, C) then
contained = true
end
end
end
if not contained then
--[[print("i is " .. tostring(i))
print("I've decided " .. point.Name .. " is a concave point.")
print(GetPointBehind(i, parts).Name .. " is behind")
print(GetPointInFront(i, parts).Name .. " is infront")--]]
earFound = point
drawTriangle(A.Position, B.Position, C.Position, folder)
newTable = {}
for x,v in pairs(parts) do
if v ~= point then
table.insert(newTable, v)
end
end
end
end
i=i+1
end
return earFound, newTable
end
function CreateFloor:TriangulatePolygon(points)
table.sort(points, function(a,b) return tonumber(a.Name) < tonumber(b.Name) end)
local folder = Instance.new("Folder", game.Workspace)
while true do
local newTable = points
local done = false
while #newTable > 2 do
done,newTable = GetEarOfPolygon(newTable, -1, folder)
table.sort(newTable, function(a,b) return tonumber(a.Name) < tonumber(b.Name) end) -- ERROR HERE
wait()
end
break
end
end
local wedge = Instance.new("WedgePart")
wedge.Material = Enum.Material.SmoothPlastic
wedge.Transparency = 0
wedge.Anchored = true
wedge.CanCollide = false
wedge.TopSurface = Enum.SurfaceType.Smooth
wedge.BottomSurface = Enum.SurfaceType.Smooth
wedge.Color = Color3.fromRGB(125, 125, 125)
local wedgeMesh = Instance.new("SpecialMesh", wedge)
wedgeMesh.MeshType = Enum.MeshType.Wedge
wedgeMesh.Scale = Vector3.new(1,1,1)
function drawTriangle(a, b, c, parent)
local edges = {
{longest = (c - b), other = (a - b), position = b};
{longest = (a - c), other = (b - c), position = c};
{longest = (b - a), other = (c - a), position = a};
};
table.sort(edges, function(a, b) return a.longest.magnitude > b.longest.magnitude end);
local edge = edges[1];
local theta = math.acos(edge.longest.unit:Dot(edge.other.unit))
local s1 = Vector2.new(edge.other.magnitude * math.cos(theta), edge.other.magnitude * math.sin(theta));
local s2 = Vector2.new(edge.longest.magnitude - s1.x, s1.y);
local p1 = edge.position + edge.other * 0.5
local p2 = edge.position + edge.longest + (edge.other - edge.longest) * 0.5
local right = edge.longest:Cross(edge.other).unit;
local up = right:Cross(edge.longest).unit;
local back = edge.longest.unit;
local cf1 = CFrame.new(
p1.x, p1.y, p1.z,
-right.x, up.x, back.x,
-right.y, up.y, back.y,
-right.z, up.z, back.z
);
local cf2 = CFrame.new(
p2.x, p2.y, p2.z,
right.x, up.x, -back.x,
right.y, up.y, -back.y,
right.z, up.z, -back.z
);
local w1 = wedge:Clone();
local w2 = wedge:Clone();
w1.Parent = parent;
w2.Parent = parent;
w1.Size = Vector3.new(0.01, s1.y, s1.x);
w2.Size = Vector3.new(0.01, s2.y, s2.x);
w1.CFrame = cf1;
w2.CFrame = cf2;
end
return CreateFloor
But I do get this error
[ bad argument #1 to ‘sort’ (table expected, got nil)]
and made a comment in the script on the line that it occurs
Tried sending gif but it don’t wanna play
Basically the end goal for me would be to have something like this
And so basically it would generate around what you’ve placed as you place more points, and the lines go from your last placed point to the new one. If it does any irrelgular shapes (like the last shape pictured) then it would just show the outline and not create the shape.
Just experimenting with trying to do what bloxburg did with the lines, but ye XD judge for yourself
function createLines(points, model)
local lastNumber = #points
local nextPoint = points[lastNumber]
for _,obj in pairs(model:GetChildren()) do
if obj.Name == 'Line' then
obj:Destroy()
end
end
for i, point in pairs(points) do
if point.Name ~= '1' then
local part = Instance.new("Part", model)
part.Anchored = true
part.TopSurface = "Smooth"
part.Name = 'Line'
local distance = (point.Position - nextPoint.Position).magnitude
part.Size = Vector3.new(0.3, 0.3, distance)
part.CFrame = CFrame.new(point.Position, nextPoint.Position) * CFrame.new(0, 0, -distance / 2)
end
end
end
2 Likes
Hey there!
I’m working on a way to try and solve this problem. No promises yet! 
Ok
I’ll keep my fingers crossed
Is there a reason why overlapping nodes error out?
The code I wrote was only ever meant to work for a polygon that doesn’t overlap with itself so it has unexpected behaviour if the polygon overlaps
Why though direction variable is only -1?
In this case i can only draw polygons from right to left…
What if i wanted to draw opposite? lol
Sorry for necroposting but I’m doing some work and I’m wondering how did you use the data structure from the CreatePolygonFromPoints, I tried to index the Next value from the tables but with some shapes, it just crashed or did draw something very weird.