Katkat
Back

Quadtree for 2D Geospatial Points

UberSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests the implementation of a spatial indexing structure by requiring the construction of a Point Quadtree that recursively divides 2D space into four quadrants.

Problem Statement

Design a Quadtree class to store 2D points (x, y) within a bounded rectangular region. The tree should partition space into four children (NorthWest, NorthEast, SouthWest, SouthEast) once a node's capacity is exceeded.

Requirements:

  1. Define a Node class containing:
    • boundary: The rectangular area it covers (x, y, width, height).
    • points: A list of stored points.
    • children: A list of 4 sub-quadrants (or null if not yet subdivided).
  2. Implement insert(x, y): Add a point to the tree. If the number of points in a node exceeds capacity, split the node into four sub-quadrants.
  3. Implement query(range_x, range_y, range_w, range_h): Return all points found within a specified rectangular region.

Constraints:

  • Use a node capacity of 4.
  • Coordinates are floating-point numbers.
  • Assume x increases to the right and y increases upwards.

Example:

# Initialize with a bounding box of (0, 0) to 100x100
qt = Quadtree(0, 0, 100, 100)
qt.insert(10, 10)
qt.insert(20, 20)
# Querying a box from (0,0) to 15x15 should return only (10, 10)
result = qt.query(0, 0, 15, 15)

Edge Cases:

  • Points falling exactly on the boundary line between quadrants.
  • Inserting many duplicate coordinates.
  • Extremely skewed data (e.g., all points clustered in one corner).

Hints

Hint 1

Use a recursive approach where each node checks if its bounding box fully contains the point being inserted.

Hint 2

When splitting a node, ensure that the four children are created with perfectly halved dimensions and adjusted origins.

Hint 3

For the query method, prune branches of the tree whose boundaries do not intersect with the search rectangle to optimize performance.

Follow-up questions

  • How would you handle the deletion of a point from the quadtree, and under what conditions would you merge children back into a parent node?
  • How does the time complexity for point insertion change if all points are inserted into a single coordinate?
  • If the coordinate space were dynamic and could grow infinitely, what modifications would you need to make to the fixed-boundary quadtree?