Filling a Polygon from given nodes

I’m trying to make an algorithm that fills in any polygon, in 2D, using nodes placed by the player. Imagine drawing points on a piece of paper, connecting them with lines, connecting the last point to the first point, then filling in all the enclosed spaces, that’s what I want to achieve using Roblox parts.

image

I started solving this problem by creating a “FillTriangle” function which takes 3 points, and uses two wedge parts (right angled triangles) to fill them. This function is working perfectly.

Like this (open spoiler)

image

Then, when the number of nodes was greater than 3, what I did was fill triangles as follows:
Create a triangle between nodes 1-2-3 :small_red_triangle:
Create a triangle between nodes 1-3-4 :small_red_triangle:
Create a triangle between nodes 1-4-5 :small_red_triangle:
etc.

A filled quadrilateral using the method described above (open spoiler)

image

This seems to fill in the polygon correctly in all cases where the polygon has interior angles that are less than 90 degrees. However, if this is not the case, my script often fills in the polygons wrong:

In this example I created a shape with 2 reflex angles (>180) at nodes 2 and 5

image

As you can see it didn’t fill in my shape correctly because the script always fills in a triangle between points 1-2-3, whereas in the case above, we didn’t need a triangle there. And we didn’t want a 1-3-4 triangle created either.

So what I need help with is improving my algorithm to fill in more complex shapes. I don’t know how much complexity this would add to the code. :thinking:

Another thing is, I don’t mind about overlapping the parts, I think it would be really difficult to create an algorithm that never overlaps any of the triangles.

Thanks for any help you may have to offer! :grinning:

11 Likes

One bit of information you need is the path of the border (the order of the nodes). One could be found by applying a traveling salesman algorithm on the set of nodes to get a shape with no overlapping edges, but it might not be the intended shape. Once you have the order, it becomes a triangulation problem, which gets tricky if you want it to be fast for lots of points.

The order of nodes is just determined by the order the player places them in.

I just need to somehow figure out where to create the triangles

This Roblox wiki article has the math (and code!) for drawing 2D triangles. Maybe you can mod the code to fit your purposes?

If you’re fine with the order of vertices then in order to triangulate a cocave polygon, you want to check certain conditions for each vertex. Start with an array containing every vertex in order. For each vertex, check if the line segment between the two neighboring elements of the array (wrapping around when necessary) intersects any edge of the polygon. If it does not, and the midpoint is inside the polygon, then draw a triangle using those three vertices and remove the current one from the array. Repeat this until after there are only 3 vertices remaining.

6 Likes

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
image

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:

image

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 :confused:

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 :grimacing: 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 :weary:

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 :sweat_smile: But it comes so close to working :weary:

Here’s the code, not really that helpful tbh cause I can’t explain what any of it does :sweat_smile:

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 :confused:

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! :stuck_out_tongue: