Quick Hull Algorithm 2D

Here we can learn about Convex Hull, his function.

by Ince_FS

Author Avatar

Introduction

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

img|50x50

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

img|50x50

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