Code Notes made by Vaibhav Rathod

Quadtree

2 min read

Written by Vaibhav Rathod

Explanation:

  • A Quadtree is a tree data structure used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions.
  • It is particularly useful in applications such as image processing, spatial indexing, and computer graphics.

Steps:

  • The space is recursively divided into four quadrants until a predefined condition is met (such as a maximum number of points in a quadrant or a minimum size of the region).
  • Each node in the tree represents a quadrant, and each child node corresponds to a subdivision of the parent quadrant.

Time Complexity:

  • Insertion: O(log n) for balanced trees, or O(n) in the worst case if all points are in the same quadrant.
  • Querying: O(log n) for searching in balanced structures.
class QuadtreeNode:
    def __init__(self, x, y, value):
        self.x = x
        self.y = y
        self.value = value
        self.nw = self.ne = self.sw = self.se = None
 
class Quadtree:
    def __init__(self, x_min, x_max, y_min, y_max):
        self.boundary = (x_min, x_max, y_min, y_max)
        self.root = None
 
    def insert(self, node, x, y, value):
        if node is None:
            return QuadtreeNode(x, y, value)
        if x < node.x:
            if y < node.y:
                node.sw = self.insert(node.sw, x, y, value)
            else:
                node.nw = self.insert(node.nw, x, y, value)
        else:
            if y < node.y:
                node.se = self.insert(node.se, x, y, value)
            else:
                node.ne = self.insert(node.ne, x, y, value)
        return node
 
    def add(self, x, y, value):
        self.root = self.insert(self.root, x, y, value)
 
    def search(self, node, x, y):
        if node is None:
            return None
        if node.x == x and node.y == y:
            return node
        if x < node.x:
            if y < node.y:
                return self.search(node.sw, x, y)
            else:
                return self.search(node.nw, x, y)
        else:
            if y < node.y:
                return self.search(node.se, x, y)
            else:
                return self.search(node.ne, x, y)
 
# Example usage
quadtree = Quadtree(0, 10, 0, 10)
quadtree.add(1, 1, "A")
quadtree.add(2, 3, "B")
 
node = quadtree.search(quadtree.root, 1, 1)
if node:
    print(f"Found point: {node.value}")
else:
    print("Point not found")

Graph View

Backlinks

Recently Updated