# Quick Hull Algorithm 2D

## Here we can learn about Convex Hull, his function.

### by Ince_FS # 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
``````