Quadtrees (Location Based Services)

┌─────────────────┐
│ 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, private depth = 0, private maxDepth = 24) {
    if (!Number.isInteger(capacity) || capacity < 1 || !Number.isInteger(maxDepth) || maxDepth < 1 || maxDepth > 32) throw new Error("Invalid capacity or maximum depth");
    if (![boundary.x, boundary.y, boundary.width, boundary.height].every(Number.isFinite) || boundary.width <= 0 || boundary.height <= 0) throw new Error("Invalid boundary");
    this.boundary = boundary;
    this.capacity = capacity;
  }
  
  // Insert point into quadtree
  insert(point: Point): boolean {
    // Point not in boundary
    if (!Number.isFinite(point.x) || !Number.isFinite(point.y) || !this.contains(this.boundary, point)) {
      return false;
    }
    
    // Space available in this quad
    if (!this.divided && (this.points.length < this.capacity || this.depth >= this.maxDepth)) {
      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.depth + 1, this.maxDepth
    );
    this.northeast = new Quadtree(
      { x: x + halfWidth, y: y - halfHeight, width: halfWidth, height: halfHeight },
      this.capacity, this.depth + 1, this.maxDepth
    );
    this.southwest = new Quadtree(
      { x: x - halfWidth, y: y + halfHeight, width: halfWidth, height: halfHeight },
      this.capacity, this.depth + 1, this.maxDepth
    );
    this.southeast = new Quadtree(
      { x: x + halfWidth, y: y + halfHeight, width: halfWidth, height: halfHeight },
      this.capacity, this.depth + 1, this.maxDepth
    );
    
    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[] {
    if (![center.x, center.y, radius].every(Number.isFinite) || radius < 0) throw new Error("Invalid centre or radius");
    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

// Search intersecting regions, then filter candidates by distance
const nearbyDrivers = sfMap.queryRadius(user, radius);

console.log(`Found ${nearbyDrivers.length} drivers within 1km`);
// The number of candidates depends on their distribution and the radius.

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!