Node Finder

local class = {}
class.threshold = 200 -- Determines when the program decides to stop cutting tables in half.
class.axis = { -- Me being lazy.
    "X"; "Z"
}

function class.new(list)
    local self = {}
    setmetatable(self, {__index = class})

    self.list = list

    return self
end

function class:get_axis(depth)
    return self.axis[depth%2+1]
end

function class:bake()
    -- Processes the map and breaks it down to be used by get_scope.
    self.system = self:bisect(self.list, 1)
end

function class:get_scope(coord)
    local scope = self.system
    repeat
        if coord[scope.axis] > scope.center then
            scope = scope[1]
        else
            scope = scope[2]
        end
    until not scope.axis
    return scope
end

function class:bisect(list, depth)
    if #list <= self.threshold then
        return list
    end
    local axis = self:get_axis(depth)
    table.sort(list, function(a, b)
        return a.Position[axis] > b.Position[axis]
    end)

    local size = #list
    local half = size / 2
    local i1 = list[1].Position[axis]
    local i2 = list[size].Position[axis]
    local center = (i1 + i2) / 2

    local output = {}
    output.axis = axis
    output.center = center
    output[1] = {}
    output[2] = {}

    for i,node in ipairs(list)do
        if i <= half then
            table.insert(output[1], node)
        else
            table.insert(output[2], node)
        end
    end
    output[1] = self:bisect(output[1], depth + 1)
    output[2] = self:bisect(output[2], depth + 1)

    return output
end

return class