Hard Written By Ince_FS

Quick Hull Algorithm 2D Created on: 15-07-2019

Here we can learn about Convex Hull, his function.

Introduction

Convex Hull, is a algorithm that find the openest distance between nodes:



How we do it?

Basically we need nodes and check the nodes, here we go;

First we need to sort the table of nodes: local Nodes = workspace.Nodes:GetChildren() table.sort(Nodes, function(A, B) return A.Position.X < B.Position.X or B.Position.X == B.Position.X and A.Position.Z < B.Position.Z end We sortered the nodes for a better learn about these positions.

Now we will use Cross Product to calculate where are the openest nodes. Cross Product that I use: local function Cross(A, B, C) return (A.Position.X-C.Position.X) (B.Position.Z-C.Position.Z) (A.Position.Z-C.Position.Z) *(B.Position.X-C.Position.X) end First we need to check lower nodes with a for loop #Low >= 2 and Cross() <= 0

local Low = {}
for _, I in next, Nodes do

while #Low >= 2 and Cross(Low[#Low-1], Low[#Low], I) <= 0 do Low[#Low] = nil end Low[#Low+1] = I

end

Second, upper nodes, we will check the childrens in reverse for this

local Up = {}
for I = #Nodes, 1, -1 do
   while #Up >= 2 and Cross(Up[#Up-1], Up[#Up], Nodes[I]) <= 0 do

Up[#Up] = nil end Up[#Up+1] = Nodes[I]

end

We need to delete the last values of these tables Low[#Low] = nil Up[#Up] = nil Now organization for _, I in next, Up do Low[#Low+1] = I end Finally we got our final product



Final Code:

local Nodes = workspace.Nodes:GetChildren()

local function Cross(A, B, C)
     return (A.Position.X-C.Position.X)

(B.Position.Z-C.Position.Z) (A.Position.Z-C.Position.Z) *(B.Position.X-C.Position.X)

end

table.sort(Nodes, function(A, B)
    return A.Position.X < B.Position.X

or B.Position.X == B.Position.X and A.Position.Z < B.Position.Z

end

local Low = {} --Order Lowers
for _, I in next, Nodes do

while #Low >= 2 and Cross(Low[#Low-1], Low[#Low], I) <= 0 do Low[#Low] = nil end Low[#Low+1] = I

end

local Up = {}
for I = #Nodes, 1, -1 do --Order Uppers
   while #Up >= 2 and Cross(Up[#Up-1], Up[#Up], Nodes[I]) <= 0 do

Up[#Up] = nil end Up[#Up+1] = Nodes[I]

end

Low[#Low] = nil
Up[#Up] = nil

for _, I in next, Up do --Order

Low[#Low+1] = I

end

for n, I in next, Low do
local Part = Instance.new("Part")
local Dis = (I.Position-Low[Low[n+1] 
			and n+1 or 1].Position).Magnitude
	Part.Anchored = true
	Part.CanCollide = false
	Part.BrickColor = BrickColor.new("Really red")
	Part.Size = Vector3.new(1, 1, Dis)
	Part.CFrame = CFrame.new(I.Position, Low[Low[n+1] 
			and n+1 or 1].Position)*CFrame.new(0, 0, -Dis/2)
	Part.Parent = workspace
	print(I)
end

Hard Written By Ince_FS

See Ince_FS's profile on Roblox

Discussion