┌─────────────────┐
│ NW  │    NE     │
│     │           │
├─────┼───────────┤
│     │     │     │
│ SW  │ SE1 │ SE2 │
│     ├─────┼─────┤
│     │ SE3 │ SE4 │
└─────┴─────┴─────┘

Tree structure:
       Root
      /  |  \  \
    NW  NE  SW  SE
             / | \ \
           SE1 SE2 SE3 SE4

1. Start at root (entire map)
2. Which quadrant does the point belong to?
3. If quadrant has < MAX_CAPACITY points:
     Add point
   Else:
     Subdivide quadrant into 4 sub-quadrants
     Redistribute existing points
     Add new point

To find all points within radius R of point P:

1. Start at root
2. For each quadrant:
   - Does circle (P, R) intersect this quadrant?
   - Yes: Recursively search this quadrant
   - No: Skip this quadrant entirely
3. Return all points found

interface Point {
  x: number;
  y: number;
  data?: any;  // Driver ID, restaurant info, etc.
}

interface Rectangle {
  x: number;        // Center x
  y: number;        // Center y
  width: number;    // Half-width
  height: number;   // Half-height
}

class Quadtree {
  private boundary: Rectangle;
  private capacity: number;
  private points: Point[] = [];
  private divided: boolean = false;
  
  // Child quadrants
  private northwest?: Quadtree;
  private northeast?: Quadtree;
  private southwest?: Quadtree;
  private southeast?: Quadtree;
  
  constructor(boundary: Rectangle, capacity: number = 4) {
    this.boundary = boundary;
    this.capacity = capacity;
  }
  
  // Insert point into quadtree
  insert(point: Point): boolean {
    // Point not in boundary
    if (!this.contains(this.boundary, point)) {
      return false;
    }
    
    // Space available in this quad
    if (this.points.length < this.capacity) {
      this.points.push(point);
      return true;
    }
    
    // Need to subdivide
    if (!this.divided) {
      this.subdivide();
    }
    
    // Insert into appropriate child
    return (
      this.northwest!.insert(point) ||
      this.northeast!.insert(point) ||
      this.southwest!.insert(point) ||
      this.southeast!.insert(point)
    );
  }
  
  // Subdivide into 4 quadrants
  private subdivide(): void {
    const { x, y, width, height } = this.boundary;
    const halfWidth = width / 2;
    const halfHeight = height / 2;
    
    // Create 4 child quadrants
    this.northwest = new Quadtree(
      { x: x - halfWidth, y: y - halfHeight, width: halfWidth, height: halfHeight },
      this.capacity
    );
    this.northeast = new Quadtree(
      { x: x + halfWidth, y: y - halfHeight, width: halfWidth, height: halfHeight },
      this.capacity
    );
    this.southwest = new Quadtree(
      { x: x - halfWidth, y: y + halfHeight, width: halfWidth, height: halfHeight },
      this.capacity
    );
    this.southeast = new Quadtree(
      { x: x + halfWidth, y: y + halfHeight, width: halfWidth, height: halfHeight },
      this.capacity
    );
    
    this.divided = true;
    
    // Redistribute existing points to children
    for (const point of this.points) {
      this.northwest.insert(point) ||
      this.northeast.insert(point) ||
      this.southwest.insert(point) ||
      this.southeast.insert(point);
    }
    
    // Clear points from parent (now in children)
    this.points = [];
  }
  
  // Query: find all points within range
  query(range: Rectangle, found: Point[] = []): Point[] {
    // Range doesn't intersect this quad
    if (!this.intersects(this.boundary, range)) {
      return found;
    }
    
    // Check points in this quad
    for (const point of this.points) {
      if (this.contains(range, point)) {
        found.push(point);
      }
    }
    
    // Recursively check children
    if (this.divided) {
      this.northwest!.query(range, found);
      this.northeast!.query(range, found);
      this.southwest!.query(range, found);
      this.southeast!.query(range, found);
    }
    
    return found;
  }
  
  // Query: find all points within radius
  queryRadius(center: Point, radius: number): Point[] {
    const found: Point[] = [];
    
    // Create bounding rectangle for circle
    const range: Rectangle = {
      x: center.x,
      y: center.y,
      width: radius,
      height: radius
    };
    
    const candidates = this.query(range);
    
    // Filter by actual distance
    for (const point of candidates) {
      const dist = this.distance(center, point);
      if (dist <= radius) {
        found.push(point);
      }
    }
    
    return found;
  }
  
  // Helper: Check if rectangle contains point
  private contains(rect: Rectangle, point: Point): boolean {
    return (
      point.x >= rect.x - rect.width &&
      point.x <= rect.x + rect.width &&
      point.y >= rect.y - rect.height &&
      point.y <= rect.y + rect.height
    );
  }
  
  // Helper: Check if two rectangles intersect
  private intersects(r1: Rectangle, r2: Rectangle): boolean {
    return !(
      r1.x + r1.width < r2.x - r2.width ||
      r1.x - r1.width > r2.x + r2.width ||
      r1.y + r1.height < r2.y - r2.height ||
      r1.y - r1.height > r2.y + r2.height
    );
  }
  
  // Helper: Euclidean distance
  private distance(p1: Point, p2: Point): number {
    const dx = p1.x - p2.x;
    const dy = p1.y - p2.y;
    return Math.sqrt(dx * dx + dy * dy);
  }
}

// Create quadtree for San Francisco
// Boundaries: lat/long converted to x/y
const sfMap = new Quadtree({
  x: 0,      // Center x (simplified)
  y: 0,      // Center y
  width: 10000,   // 10km radius
  height: 10000
}, 10);  // Max 10 drivers per quad

// Add drivers
const drivers = [
  { x: 100, y: 200, data: { id: 'driver1', name: 'John' } },
  { x: 150, y: 250, data: { id: 'driver2', name: 'Jane' } },
  { x: 5000, y: 5000, data: { id: 'driver3', name: 'Bob' } },
  // ... 10,000 more drivers
];

for (const driver of drivers) {
  sfMap.insert(driver);
}

// User requests ride
const user = { x: 120, y: 220 };
const radius = 1000;  // 1km

// Find nearby drivers (O(log N) instead of O(N))
const nearbyDrivers = sfMap.queryRadius(user, radius);

console.log(`Found ${nearbyDrivers.length} drivers within 1km`);
// Only checked ~100 drivers instead of 10,000!

Find drivers within 1km of user:

for each driver in all_drivers:
    distance = calculate_distance(user, driver)
    if distance < 1km:
        nearby_drivers.append(driver)

Time: O(N) where N = total drivers
For 1M drivers: 1M distance calculations! ❌

1. Locate user's quadrant: O(log N)
2. Search user's quad + 8 neighbors: O(k) where k << N
3. Filter by distance: O(k)

Total: O(log N + k)
For 1M drivers: ~20 levels + maybe 100 drivers to check ✅

// Update driver location every 5 seconds
function updateDriverLocation(driverId: string, lat: number, lng: number) {
  // Remove from old position
  quadtree.remove({ driverId });
  
  // Insert at new position
  quadtree.insert({
    x: lat,
    y: lng,
    data: { driverId, available: true }
  });
}

// Match rider with nearest driver
function matchRider(riderLat: number, riderLng: number) {
  const nearbyDrivers = quadtree.queryRadius(
    { x: riderLat, y: riderLng },
    5000  // 5km search radius
  );
  
  // Sort by distance + ETA
  const sorted = nearbyDrivers.sort((a, b) => {
    return calculateETA(a) - calculateETA(b);
  });
  
  return sorted[0];  // Best driver
}

-- Traditional database query (SLOW)
SELECT * FROM restaurants
WHERE ST_Distance(location, user_location) < 1km
-- Must scan entire table!

-- With Quadtree index
1. Find user's quadrant
2. Search only nearby quads
3. Return matches

10x - 100x faster!

// Game map with quadtree
const gameMap = new Quadtree(worldBounds, 20);

// Spawn pokemon
function spawnPokemon(lat: number, lng: number, type: string) {
  gameMap.insert({
    x: lat,
    y: lng,
    data: { typ, spawnTime: Date.now() }
  });
}

// Find pokemon near player
function getNearbyPokemon(playerLat: number, playerLng: number) {
  return gameMap.queryRadius({ x: playerLat, y: playerLng }, 100);  // 100m
}

// Game objects
const gameWorld = new Quadtree(gameBounds, 10);

// Each frame
function update() {
  // Clear and rebuild quadtree
  gameWorld.clear();
  
  for (const entity of entities) {
    gameWorld.insert({
      x: entity.x,
      y: entity.y,
      data: entity
    });
  }
  
  // Check collisions
  for (const entity of entities) {
    const nearby = gameWorld.queryRadius(entity, entity.radius * 2);
    
    for (const other of nearby) {
      if (entity !== other && collides(entity, other)) {
        handleCollision(entity, other);
      }
    }
  }
}

// Instead of O(N²), now O(N log N)

function geohash(lat, lng, precision = 8) {
  // Example: San Francisco
  // geohash(37.7749, -122.4194, 8) => "9q8yyk8y"
}

// Nearby search
const myHash = "9q8yyk8y";
const prefix = myHash.substring(0, 6);  // "9q8yyk"

// SQL query
SELECT * FROM drivers
WHERE geohash LIKE '9q8yyk%'
-- All drivers with same prefix are nearby!