Just a naive quadtree implementation intended for use in FiveM

quadtree.lua

local insert = table.insert
local ipairs = ipairs
local format = string.format
local assert = assert
local type = type
local print = print
local vec2 = vec2
local setmetatable = setmetatable
local newPromise = promise.new
local thread = Citizen.CreateThread
local await  = Citizen.Await
local wait = Citizen.Wait

local MAX_OBJECTS = 15 -- Max objects per level before a split happens
local MAX_LEVELS = 10 -- How many levels deep the tree goes before it stops splitting

function CoordsInsideBounds(bounds, coords)
    local min,max = bounds[1], bounds[2]
    if coords.x > max.x then return false end
    if coords.x < min.x then return false end
    if coords.x < min.x then return false end
    if coords.y < min.y then return false end
    return true
end
function BoundsInsideBounds(outerBounds, innerBounds)
    local outer = ExtentOfBounds(outerBounds)
    local inner = ExtentOfBounds(innerBounds)

    if inner.top < outer.top then return false end
    if inner.bottom > outer.bottom then return false end
    if inner.left < outer.left then return false end
    if inner.right > outer.right then return false end

    return true
end
function BoundsOverlap(firstBounds, secondBounds)
    local first = ExtentOfBounds(firstBounds)
    local second = ExtentOfBounds(secondBounds)

    if first.left > second.right then return false end
    if first.right < second.left then return false end
    if first.bottom < second.top then return false end
    if first.top > second.bottom then return false end

    return true
end

function ExtentOfBounds(bounds)
    local top = bounds[1].y
    local bottom = bounds[2].y
    local left = bounds[1].x
    local right = bounds[2].x
    return {top=top, bottom=bottom, left=left, right=right}
end
function Bounds(center, size)
    --[[
    local top = center.y - (size.y/2)
    local bottom = center.y + (size.y/2)
    local left = center.x - (size.x/2)
    local right = center.x + (size.x/2)
    return {vec2(top, left), vec2(bottom, right)}
    ]]
    return {center-(size/2), center+(size/2)}
end
function RadiusToBounds(center, radius)
    local top = center.y - radius
    local bottom = center.y + radius
    local left = center.x - radius
    local right = center.x + radius
    return {vec2(left, top), vec2(right, bottom)}
end

local nodeMethods = {}
function nodeMethods:Search(coords, radius, searchBounds, results, comparisons, maxLevel)
    searchBounds = searchBounds or RadiusToBounds(coords, radius)
    results = results or {}
    comparisons = comparisons or 0

    maxLevel = maxLevel or 0
    if self.level > maxLevel then
        maxLevel = self.level
    end

    if BoundsOverlap(self.bounds, searchBounds) then
        for _, object in ipairs(self.objects) do
            comparisons += 1
            local dist = #(object.coords - coords)
            if dist <= radius then
                insert(results, object)
            end
        end
        for i, node in ipairs(self.nodes) do
            results, comparisons, maxLevel = node:Search(coords, radius, searchBounds, results, comparisons, maxLevel)
        end
    end

    return results, comparisons, maxLevel
end
function nodeMethods:SelectSubnode(point)
    if #self.nodes == 0 then
        return
    end
    for _, node in ipairs(self.nodes) do
        if CoordsInsideBounds(node.bounds, point) then
            return node
        end
    end
end
function nodeMethods:Split()
    if #self.nodes > 0 then return false end
    local subLevel = self.level + 1
    local subSize = self.size / 2
    self.nodes = {
        QuadTreeNode(subLevel, vec2(self.center.x - subSize.x/2, self.center.y + subSize.y/2), subSize),
        QuadTreeNode(subLevel, vec2(self.center.x - subSize.x/2, self.center.y - subSize.y/2), subSize),
        QuadTreeNode(subLevel, vec2(self.center.x + subSize.x/2, self.center.y + subSize.y/2), subSize),
        QuadTreeNode(subLevel, vec2(self.center.x + subSize.x/2, self.center.y - subSize.y/2), subSize),
    }
    return true
end
function nodeMethods:Insert(point)
    if not CoordsInsideBounds(self.bounds, point.coords) then
        return "Point out of bounds"
    end
    local subNode = self:SelectSubnode(point.coords)
    if subNode then
        return subNode:Insert(point)
    end

    point.node = self
    point.nindex = #self.objects + 1
    insert(self.objects, point)

    if #self.nodes == 0 and #self.objects > MAX_OBJECTS and self.level < MAX_LEVELS then
        local limbo = self.objects
        self.objects = {}
        self:Split()
        for _, object in ipairs(limbo) do
            local subNode = self:SelectSubnode(object.coords)
            if subNode then
                subNode:Insert(object)
            else
                object.nindex = #self.objects + 1
                insert(self.objects, object)
            end
        end
    end

end

function QuadTreeNode(level, center, size)
    assert(level and type(level) == 'number' and level % 1 == 0, "Level must be an integer")
    assert(center and center.xy and type(center.xy) == 'vector2', "Center must be a vector!")
    assert(size and size.xy and type(size.xy) == 'vector2', "Size must be a vector!")
    center = center.xy
    size = size.xy

    local newNode = {
        level = level,
        center = center,
        size = size,
        bounds = Bounds(center, size),
        objects = {},
        nodes = {},
    }
    setmetatable(newNode, {__index=nodeMethods})
    return newNode
end

local treeMethods = {}
function treeMethods:print(something, ...)
    if not self.verbose or self.verbose == "" or not something then
        return
    end
    if type(something) == "function" then
        return self:print(something(...))
    end
    print(tostring(self.verbose) .. '> ' .. format(something, ...))
end
function treeMethods:Lock(wat)
    wat = wat or '[unknown]'
    if not self.locked then
        self:print("Locked for %s", wat)
        self.locked = wat
        return
    end
    local p = newPromise()
    thread(function()
        self:print("%s is waiting for unlock", wat)
        while self.locked do
            wait(0)
        end
        self:print("%s locked", wat)
        p:resolve(wat)
    end)
    self.locked = await(p)
end
function treeMethods:Unlock()

    if not self.locked  then
        self:print('Unlock call while not locked.')
        return
    end

    self:print('Lock released: %s', self.locked)
    self.locked = false
end
function treeMethods:Add(point, data)
    assert(type(point) == 'vector2', "Point to add must be a vector2")
    self:Lock('add')
    local pointWithData = {
        coords = point,
        data = data or {},
    }
    if self.built then
        if CoordsInsideBounds(self.root.bounds, point) then
            self.root:Insert(point, data)
        else
            self.root = nil
            self.built = false
        end
    end
    insert(self.points, pointWithData)
    self:Unlock()
    return #self.points
end
function treeMethods:IsBuilding()
    return self.building
end
function treeMethods:Search(point, radius)
    assert(type(point) == 'vector2', "Point to search around must be a vector2")
    radius = radius or 50.0
    assert(type(radius) == 'number', "Radius must be a number")
    if not self.built then
        self:Build()
    end
    return self.root:Search(point, radius)
end
function treeMethods:Build()
    self:Lock('build')
    self.building = true
    local p = newPromise()
    thread(function()
        local min = vec2(math.maxinteger, math.maxinteger)
        local max = vec2(math.mininteger, math.mininteger)
        self:print("Checking size of cloud with %i points", #self.points)
        for i, point in ipairs(self.points) do

            if point.coords.x < min.x then min = vec2(point.coords.x, min.y) end
            if point.coords.y < min.y then min = vec2(min.x, point.coords.y) end
            if point.coords.x > max.x then max = vec2(point.coords.x, max.y) end
            if point.coords.y > max.y then max = vec2(max.x, point.coords.y) end

            if self.chunkSize and i % self.chunkSize == 0 then
                self:print('Yielding thread during build: %i', i)
                wait(0)
            end
        end

        self:print("Bounds: {vec2(%.2f, %.2f), vec2(%.2f, %.2f)}", min.x, min.y, max.x, max.y)
        local center = vec2((min.x + max.x)/2, (min.y + max.y)/2)
        self:print("Center: vec2(%.2f, %.2f)", center.x, center.y)
        local size = (max - min)
        self:print("Size: vec2(%.2f, %.2f)", size.x, size.y)

        self:print("Inserting points into tree")
        self.root = QuadTreeNode(0, center, size)
        local err = ""
        for i, point in ipairs(self.points) do
            err = self.root:Insert(point)
            if err and err ~= "" then
                error("QuadTree could not insert point " .. i .. ": " .. tostring(err))
            end

            if self.chunkSize and i % self.chunkSize == 0 then
                self:print('Yielding thread during build: %i', i)
                wait(0)
            end
        end
        p:resolve(true)
    end)

    self.built = await(p)
    self.building = false
    self:Unlock()
end

function QuadTree(points)
    if points then
        assert(type(points) == 'table', "QuadTree() expects a table, got " .. type(points))
    end
    local new = {
        locked = false,
        verbose = "",
        building = false,
        chunkSize = 20,
        built = false,
        points = {}
    }
    setmetatable(new, {__index=treeMethods})
    for _, point in ipairs(points) do
        new:Add(point[1], point[2])
    end
    return new
end