[021] Quad Tree

[021] Quad Tree

[21h] Tree Data Structure for Quick Rect Query

[Jan 31] 02h - Quad Tree Review
[Feb 01] 08h - Quad Tree Research / Build / Draw
[Feb 02] 09h - Quad Tree Nearest Search / UI
[Feb 03] 02h - Quad Tree Upload

Pseudocode:
    # youtu.be/OJxEcs0w_kE
    var _root_node: TreeNode
    var _max_size: Vector2 = Vector2(1025, 768)

    class QuadTree:
        var bounds: Rect2
        var points: Array[Vector2]
        var capacity: int = 4
        var depth: int = 0

        var divided: bool = false
        var north_west: QuadTree
        var north_east: QuadTree
        var south_west: QuadTree
        var south_east: QuadTree

    func _ready() -> void:
        _root_node = _new_quad_node(Rect2(Vector2(0, 0), _max_size))

    func _new_quad_node(bounds: Rect2, depth: int = 0) -> QuadTree:
        var new_quad_node: QuadTree = QuadTree.new()
        new_quad_node.bounds = bounds
        new_quad_node.depth = depth
        return new_quad_node

    func _insert(node: QuadTree, point: Vector2) -> bool:
        if node.bounds.has_point(point) == false:                  # point outside Rect2
            return false

        if node.divided == false:                                  # not yet divided
            if node.points.size() < node.capacity:                 # if not capacity
                node.points.append(point)                          # add point
                return true

            _subdivide(node)                                       # if capacity, subdivide

        if _insert(node.north_west, point): return true            # recursive insert
        if _insert(node.north_east, point): return true
        if _insert(node.south_west, point): return true
        if _insert(node.south_east, point): return true

        return false

    func _subdivide(node: QuadTree) -> void:                       # divide into 4 squares
        node.divided = true

        var subdivide_size: Vector2 = node.bounds.size / 2
        var north_west_rect: Rect2 = Rect2(node.bounds.position, subdivide_size)
        var north_east_rect: Rect2 = Rect2(node.bounds.position + Vector2(subdivide_size.x, 0), subdivide_size)
        var south_west_rect: Rect2 = Rect2(node.bounds.position + Vector2(0, subdivide_size.y), subdivide_size)
        var south_east_rect: Rect2 = Rect2(node.bounds.position + Vector2(subdivide_size.x, subdivide_size.y), subdivide_size)

        node.north_west = _new_quad_node(north_west_rect, node.depth + 1)
        node.north_east = _new_quad_node(north_east_rect, node.depth + 1)
        node.south_west = _new_quad_node(south_west_rect, node.depth + 1)
        node.south_east = _new_quad_node(south_east_rect, node.depth + 1)

        for point in node.points:                                   # move points to children (for performance)
            if _insert(node.north_west, point): continue            # recursive insert
            if _insert(node.north_east, point): continue
            if _insert(node.south_west, point): continue
            if _insert(node.south_east, point): continue

        node.points.clear()

    func _query(rect: Rect2) -> void:
        _points_found.clear()
        _query_helper(_root_node, rect, _points_found)

    func _query_helper(node: QuadTree, rect: Rect2, found: Array[Vector2]) -> void:
        if node.bounds.intersects(rect) == false:
            return

        if node.divided == true:                                    # divided, will not have any points
            _query_helper(node.north_west, rect, found)
            _query_helper(node.north_east, rect, found)
            _query_helper(node.south_west, rect, found)
            _query_helper(node.south_east, rect, found)
            return

        for point in node.points:
            if rect.has_point(point) == true:
                found.append(point)

        return