Filling a Polygon from given nodes

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:

Ok :grimacing:

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.

Necroposting this again to give a more definitive solution, as people were still struggling with bugs in the later posts

Waffle gave a lot of good advice and code about how to prevent an ear from forming:

  1. line segment between the two neighboring elements of the array (wrapping around when necessary) intersects any edge of the polygon

  2. midpoint of the ear is NOT inside the polygon

But there was a crucial conditional missing that I don’t think anyone mentioned - you also need to make sure there are no other points in the remaining polygon that are inside the ear!

As you can tell from this very crude diagram, if we use 1-2-3 as the ear, both of the above criteria won’t trigger the ear to stop forming, which is wrong. We need the 3rd conditional to check if 4 is inside the 1-2-3 triangle, in which this case it is true, therefore skipping 1-2-3 and moving forward to try 2-3-4 and then 2-4-1

Only through doing this extra step (and also swapping my checkInPolygon algorithm to a more robust version from github) did I manage to solve this completely without any more errors.

(You should also use checkInPolygon for doing this third step of checking for points inside the ear)

function checkInPolygon(pos, polygonPoints) 
    local minX = polygonPoints[1].X;
    local maxX = polygonPoints[1].X;
    local minZ = polygonPoints[1].Z;
    local maxZ = polygonPoints[1].Z;

    for i=2,len(polygonPoints) do
        local polygonPos = polygonPoints[i]
        minX = math.min(minX, polygonPos.X);
        maxX = math.max(maxX, polygonPos.X);
        minZ = math.min(minZ, polygonPos.Z);
        maxZ = math.max(maxZ, polygonPos.Z);

    end

    if (pos.X < minX) or (pos.X > maxX) or (pos.Z < minZ) or (pos.Z > maxZ) then
        return false
    end

    local inside = false
    local j

    for i=1,len(polygonPoints) do
        j = i - 1

        if j <= 0 then
            j = len(polygonPoints)
        end

        -- print(i, j)

        if ( ( polygonPoints[i].Z > pos.Z ) ~= ( polygonPoints[j].Z > pos.Z ) and (pos.X < ( polygonPoints[ j ].X - polygonPoints[ i ].X ) * ( pos.Z - polygonPoints[ i ].Z ) / ( polygonPoints[ j ].Z - polygonPoints[ i ].Z ) + polygonPoints[ i ].X )  ) then
            inside = not inside
        end
        

    end

    return inside

end

I noticed several other posts and even a community resource about ear clipping that got this wrong - and therefore failed in a lot of specific cases like the one above. Hopefully this helps any new people trying to make this feature

2 Likes