Quadtree — Spatial Indexing Engine

Uber cần tìm tài xế gần nhất trong 1 triệu tài xế online tại một thành phố — và phải trả lời trong vài milliseconds. Nếu duyệt toàn bộ danh sách để tính khoảng cách, mỗi query tốn O(N) = 1 triệu phép tính. Với 1000 queries/giây, đó là 1 tỷ distance calculations mỗi giây — và hệ thống sẽ sụp đổ.

Quadtree giải quyết bằng cách chia không gian 2D thành các ô đệ quy. Thay vì duyệt toàn bộ, mỗi query chỉ cần xét vài chục candidates trong vùng lân cận — giảm từ O(N) xuống O(log N). Đây là cấu trúc dữ liệu mà Uber, Grab, game engines (Unity, Unreal), Google Maps, và Elasticsearch đều sử dụng cho spatial queries.

Ngoài nearest-neighbor, Quadtree còn là nền tảng cho collision detection trong game, frustum culling trong đồ họa 3D, và spatial database indexing trong GIS — bất kỳ hệ thống nào xử lý dữ liệu 2D ở quy mô lớn.

Bức tranh tư duy

Hình dung bạn là chủ chuỗi quán cà phê ở Sài Gòn và cần tìm quán nào gần khách hàng nhất. Ban đầu, bạn có một tấm bản đồ lớn với tất cả quán đánh dấu chấm.

Cách thô: nhìn từng chấm một và đo khoảng cách → chậm.

Cách thông minh: chia bản đồ thành 4 phần (Quận 1, Quận 3, Quận 7, Thủ Đức). Khách ở Quận 7? Chỉ cần xét các quán trong ô Quận 7. Nếu ô đó vẫn có quá nhiều quán, chia tiếp thành 4 phần nhỏ hơn — Phường 1, Phường 2, ... Cứ chia đệ quy cho đến khi mỗi ô chỉ còn vài quán.

Bước 1: Toàn bộ TP.HCM            Bước 2: Chia thành 4 quận
┌────────────────────────┐         ┌───────────┬────────────┐
│  •    •                │         │  •    •   │            │
│       •    •           │   →     │       •   │    •       │
│            •    •      │         ├───────────┼────────────┤
│  •              •      │         │  •        │    •    •  │
│         •              │         │         • │            │
└────────────────────────┘         └───────────┴────────────┘

Khách ở góc phải dưới? → Chỉ xét ô SE (2 quán thay vì 8)

Khi nào analogy này breakdown: Quadtree chia theo tọa độ trung tâm, không theo ranh giới hành chính. Và điểm nằm sát biên giữa hai ô có thể bị bỏ sót nếu search range không đủ rộng.

Cốt lõi kỹ thuật

Point Quadtree vs Region Quadtree

Point Quadtree (bài này): Lưu điểm dữ liệu (tọa độ tài xế, quán ăn). Chia khi node chứa quá nhiều points.

Region Quadtree: Chia không gian thành grid đều, lưu thuộc tính vùng (pixel, terrain type). Dùng trong image processing, terrain rendering.

Cơ chế Insert

Bắt đầu từ root (toàn bộ bản đồ)
Nếu node chưa đầy (< capacity) → thêm point
Nếu đầy → chia thành 4 children (NW, NE, SW, SE), phân bổ points

Cơ chế Range Query

Nếu search range không giao với node boundary → bỏ qua (pruning)
Nếu giao → kiểm tra points trong node, rồi đệ quy vào children

Pruning là chìa khóa hiệu năng: mỗi level loại bỏ ~75% không gian.

Triển khai đầy đủ

C++PythonJavaGo

cpp

#include <vector>
#include <algorithm>
#include <cmath>
#include <memory>

struct Point {
    double x, y;
    int id;  // payload
};

struct Rect {
    double cx, cy, hw, hh;  // center + half-width/height

    bool contains(const Point& p) const {
        return p.x >= cx - hw && p.x <= cx + hw
            && p.y >= cy - hh && p.y <= cy + hh;
    }

    bool intersects(const Rect& o) const {
        return !(o.cx - o.hw > cx + hw || o.cx + o.hw < cx - hw
              || o.cy - o.hh > cy + hh || o.cy + o.hh < cy - hh);
    }
};

class Quadtree {
    static constexpr int CAPACITY = 4;
    static constexpr int MAX_DEPTH = 10;

    Rect boundary_;
    int depth_;
    std::vector<Point> points_;
    bool divided_ = false;
    std::unique_ptr<Quadtree> nw_, ne_, sw_, se_;

    void subdivide() {
        double x = boundary_.cx, y = boundary_.cy;
        double hw = boundary_.hw / 2, hh = boundary_.hh / 2;
        nw_ = std::make_unique<Quadtree>(Rect{x-hw, y-hh, hw, hh}, depth_+1);
        ne_ = std::make_unique<Quadtree>(Rect{x+hw, y-hh, hw, hh}, depth_+1);
        sw_ = std::make_unique<Quadtree>(Rect{x-hw, y+hh, hw, hh}, depth_+1);
        se_ = std::make_unique<Quadtree>(Rect{x+hw, y+hh, hw, hh}, depth_+1);
        divided_ = true;
        for (auto& p : points_) {
            nw_->insert(p) || ne_->insert(p) || sw_->insert(p) || se_->insert(p);
        }
        points_.clear();
    }

public:
    Quadtree(Rect boundary, int depth = 0)
        : boundary_(boundary), depth_(depth) {}

    bool insert(const Point& p) {
        if (!boundary_.contains(p)) return false;
        if (!divided_ && (int)points_.size() < CAPACITY) {
            points_.push_back(p);
            return true;
        }
        if (!divided_) {
            if (depth_ >= MAX_DEPTH) { points_.push_back(p); return true; }
            subdivide();
        }
        return nw_->insert(p) || ne_->insert(p)
            || sw_->insert(p) || se_->insert(p);
    }

    void query(const Rect& range, std::vector<Point>& found) const {
        if (!boundary_.intersects(range)) return;
        for (auto& p : points_)
            if (range.contains(p)) found.push_back(p);
        if (divided_) {
            nw_->query(range, found); ne_->query(range, found);
            sw_->query(range, found); se_->query(range, found);
        }
    }
};

python

from __future__ import annotations
from dataclasses import dataclass, field
from typing import Optional


@dataclass
class Point:
    x: float
    y: float
    data: object = None


@dataclass
class Rect:
    cx: float  # center x
    cy: float  # center y
    hw: float  # half-width
    hh: float  # half-height

    def contains(self, p: Point) -> bool:
        return (self.cx - self.hw <= p.x <= self.cx + self.hw
            and self.cy - self.hh <= p.y <= self.cy + self.hh)

    def intersects(self, other: Rect) -> bool:
        return not (other.cx - other.hw > self.cx + self.hw
                 or other.cx + other.hw < self.cx - self.hw
                 or other.cy - other.hh > self.cy + self.hh
                 or other.cy + other.hh < self.cy - self.hh)


class Quadtree:
    CAPACITY = 4
    MAX_DEPTH = 10

    def __init__(self, boundary: Rect, depth: int = 0) -> None:
        self.boundary = boundary
        self.depth = depth
        self.points: list[Point] = []
        self.divided = False
        self.nw: Optional[Quadtree] = None
        self.ne: Optional[Quadtree] = None
        self.sw: Optional[Quadtree] = None
        self.se: Optional[Quadtree] = None

    def insert(self, point: Point) -> bool:
        if not self.boundary.contains(point):
            return False
        if not self.divided and len(self.points) < self.CAPACITY:
            self.points.append(point)
            return True
        if not self.divided:
            if self.depth >= self.MAX_DEPTH:
                self.points.append(point)
                return True
            self._subdivide()
        return (self.nw.insert(point) or self.ne.insert(point)
             or self.sw.insert(point) or self.se.insert(point))

    def query(self, search_range: Rect) -> list[Point]:
        found: list[Point] = []
        if not self.boundary.intersects(search_range):
            return found
        for p in self.points:
            if search_range.contains(p):
                found.append(p)
        if self.divided:
            found.extend(self.nw.query(search_range))
            found.extend(self.ne.query(search_range))
            found.extend(self.sw.query(search_range))
            found.extend(self.se.query(search_range))
        return found

    def query_radius(self, center: Point, radius: float) -> list[tuple[Point, float]]:
        rect = Rect(center.x, center.y, radius, radius)
        candidates = self.query(rect)
        results = []
        for p in candidates:
            dist = ((p.x - center.x)**2 + (p.y - center.y)**2) ** 0.5
            if dist <= radius:
                results.append((p, dist))
        results.sort(key=lambda x: x[1])
        return results

    def _subdivide(self) -> None:
        cx, cy = self.boundary.cx, self.boundary.cy
        hw, hh = self.boundary.hw / 2, self.boundary.hh / 2
        self.nw = Quadtree(Rect(cx - hw, cy - hh, hw, hh), self.depth + 1)
        self.ne = Quadtree(Rect(cx + hw, cy - hh, hw, hh), self.depth + 1)
        self.sw = Quadtree(Rect(cx - hw, cy + hh, hw, hh), self.depth + 1)
        self.se = Quadtree(Rect(cx + hw, cy + hh, hw, hh), self.depth + 1)
        self.divided = True
        for p in self.points:
            self.nw.insert(p) or self.ne.insert(p) or \
            self.sw.insert(p) or self.se.insert(p)
        self.points = []

java

import java.util.ArrayList;
import java.util.List;

public class Quadtree {
    private static final int CAPACITY = 4;
    private static final int MAX_DEPTH = 10;

    private final Rect boundary;
    private final int depth;
    private final List<Point> points = new ArrayList<>();
    private boolean divided = false;
    private Quadtree nw, ne, sw, se;

    public Quadtree(Rect boundary, int depth) {
        this.boundary = boundary;
        this.depth = depth;
    }

    public boolean insert(Point p) {
        if (!boundary.contains(p)) return false;
        if (!divided && points.size() < CAPACITY) {
            points.add(p);
            return true;
        }
        if (!divided) {
            if (depth >= MAX_DEPTH) { points.add(p); return true; }
            subdivide();
        }
        return nw.insert(p) || ne.insert(p) || sw.insert(p) || se.insert(p);
    }

    public List<Point> query(Rect range) {
        List<Point> found = new ArrayList<>();
        if (!boundary.intersects(range)) return found;
        for (Point p : points)
            if (range.contains(p)) found.add(p);
        if (divided) {
            found.addAll(nw.query(range));
            found.addAll(ne.query(range));
            found.addAll(sw.query(range));
            found.addAll(se.query(range));
        }
        return found;
    }

    private void subdivide() {
        double cx = boundary.cx, cy = boundary.cy;
        double hw = boundary.hw / 2, hh = boundary.hh / 2;
        nw = new Quadtree(new Rect(cx-hw, cy-hh, hw, hh), depth+1);
        ne = new Quadtree(new Rect(cx+hw, cy-hh, hw, hh), depth+1);
        sw = new Quadtree(new Rect(cx-hw, cy+hh, hw, hh), depth+1);
        se = new Quadtree(new Rect(cx+hw, cy+hh, hw, hh), depth+1);
        divided = true;
        for (Point p : points) {
            nw.insert(p); ne.insert(p); sw.insert(p); se.insert(p);
        }
        points.clear();
    }
}

package quadtree

import (
	"math"
	"sort"
)

type Point struct {
	X, Y float64
	ID   int
}

type Rect struct {
	Cx, Cy, Hw, Hh float64
}

func (r Rect) Contains(p Point) bool {
	return p.X >= r.Cx-r.Hw && p.X <= r.Cx+r.Hw &&
		p.Y >= r.Cy-r.Hh && p.Y <= r.Cy+r.Hh
}

func (r Rect) Intersects(o Rect) bool {
	return !(o.Cx-o.Hw > r.Cx+r.Hw || o.Cx+o.Hw < r.Cx-r.Hw ||
		o.Cy-o.Hh > r.Cy+r.Hh || o.Cy+o.Hh < r.Cy-r.Hh)
}

type Quadtree struct {
	boundary Rect
	depth    int
	points   []Point
	divided  bool
	nw, ne, sw, se *Quadtree
}

const capacity = 4
const maxDepth = 10

func New(boundary Rect) *Quadtree {
	return &Quadtree{boundary: boundary}
}

func (qt *Quadtree) Insert(p Point) bool {
	if !qt.boundary.Contains(p) { return false }
	if !qt.divided && len(qt.points) < capacity {
		qt.points = append(qt.points, p)
		return true
	}
	if !qt.divided {
		if qt.depth >= maxDepth {
			qt.points = append(qt.points, p)
			return true
		}
		qt.subdivide()
	}
	return qt.nw.Insert(p) || qt.ne.Insert(p) ||
		qt.sw.Insert(p) || qt.se.Insert(p)
}

func (qt *Quadtree) Query(r Rect) []Point {
	if !qt.boundary.Intersects(r) { return nil }
	var found []Point
	for _, p := range qt.points {
		if r.Contains(p) { found = append(found, p) }
	}
	if qt.divided {
		found = append(found, qt.nw.Query(r)...)
		found = append(found, qt.ne.Query(r)...)
		found = append(found, qt.sw.Query(r)...)
		found = append(found, qt.se.Query(r)...)
	}
	return found
}

func (qt *Quadtree) subdivide() {
	cx, cy := qt.boundary.Cx, qt.boundary.Cy
	hw, hh := qt.boundary.Hw/2, qt.boundary.Hh/2
	qt.nw = &Quadtree{boundary: Rect{cx-hw, cy-hh, hw, hh}, depth: qt.depth+1}
	qt.ne = &Quadtree{boundary: Rect{cx+hw, cy-hh, hw, hh}, depth: qt.depth+1}
	qt.sw = &Quadtree{boundary: Rect{cx-hw, cy+hh, hw, hh}, depth: qt.depth+1}
	qt.se = &Quadtree{boundary: Rect{cx+hw, cy+hh, hw, hh}, depth: qt.depth+1}
	qt.divided = true
	for _, p := range qt.points {
		qt.nw.Insert(p); qt.ne.Insert(p); qt.sw.Insert(p); qt.se.Insert(p)
	}
	qt.points = nil
}

So sánh Quadtree với K-D Tree

Tiêu chí	Quadtree	K-D Tree
Phân chia	4 children (2D grid)	2 children (alternating axis)
Balance	Phụ thuộc phân bố data	Balanced nếu build từ sorted data
Insert	O(log N) avg, O(N) worst	O(log N) avg
Range query	O(log N + K)	O(√N + K) — tốt hơn lý thuyết
Khi nào dùng	Data thay đổi, insert/delete thường	Static data, build một lần
Chiều	Tối ưu cho 2D	Mở rộng tự nhiên sang nhiều chiều
Triển khai	Đơn giản hơn	Phức tạp hơn

Quy tắc chọn: Nếu data thay đổi liên tục (tài xế di chuyển) → Quadtree. Nếu data tĩnh (bản đồ, POI database) → K-D Tree.

Thực chiến

Tình huống: Nearest Driver Matching

Bối cảnh: Ứng dụng gọi xe cần tìm 5 tài xế gần nhất trong bán kính 3 km. Database có 50,000 tài xế online.

Mục tiêu: Trả kết quả trong < 5ms.

PythonJava

python

class DriverMatcher:
    def __init__(self, city_bounds: Rect) -> None:
        self.tree = Quadtree(city_bounds)
        self.drivers: dict[int, Point] = {}

    def update_location(self, driver_id: int, lat: float, lng: float) -> None:
        # Trong production: cần remove vị trí cũ trước
        point = Point(lng, lat, data=driver_id)
        self.drivers[driver_id] = point
        self.tree.insert(point)

    def find_nearest(
        self, lat: float, lng: float,
        radius_km: float = 3.0, limit: int = 5
    ) -> list[tuple[int, float]]:
        center = Point(lng, lat)
        # Chuyển km sang degree (xấp xỉ tại VN: 1° ≈ 111 km)
        radius_deg = radius_km / 111.0
        results = self.tree.query_radius(center, radius_deg)
        # Trả về top-N gần nhất
        return [
            (p.data, dist * 111.0)  # Convert back to km
            for p, dist in results[:limit]
        ]

java

public class DriverMatcher {
    private final Quadtree tree;

    public DriverMatcher(Rect cityBounds) {
        this.tree = new Quadtree(cityBounds, 0);
    }

    public void updateLocation(int driverId, double lat, double lng) {
        tree.insert(new Point(lng, lat, driverId));
    }

    public List<DriverResult> findNearest(
            double lat, double lng, double radiusKm, int limit) {
        double radiusDeg = radiusKm / 111.0;
        Rect searchArea = new Rect(lng, lat, radiusDeg, radiusDeg);
        List<Point> candidates = tree.query(searchArea);

        return candidates.stream()
            .map(p -> new DriverResult(p.id, distance(lat, lng, p.y, p.x)))
            .filter(r -> r.distanceKm <= radiusKm)
            .sorted(Comparator.comparingDouble(r -> r.distanceKm))
            .limit(limit)
            .collect(Collectors.toList());
    }
}

Phân tích:

Pruning: 50,000 tài xế nhưng query chỉ xét vùng 3 km → ~50-200 candidates
Radius query: Dùng rectangular query trước (nhanh), rồi filter circular distance sau
Coordinate conversion: 1 degree latitude ≈ 111 km tại Việt Nam — đủ chính xác cho matching

Tình huống: Game Collision Detection

Bối cảnh: Game 2D có 10,000 entities. Mỗi frame cần kiểm tra va chạm giữa tất cả entities.

Mục tiêu: Giảm từ O(N²) brute-force xuống O(N log N).

python

class CollisionSystem:
    def __init__(self, world_width: float, world_height: float) -> None:
        self.width = world_width
        self.height = world_height

    def detect_collisions(self, entities: list[Entity]) -> list[tuple[Entity, Entity]]:
        # Rebuild quadtree mỗi frame (entities di chuyển)
        bounds = Rect(self.width / 2, self.height / 2,
                      self.width / 2, self.height / 2)
        tree = Quadtree(bounds)

        for entity in entities:
            tree.insert(Point(entity.x, entity.y, data=entity))

        collisions = []
        for entity in entities:
            # Chỉ tìm entities gần trong bounding radius
            nearby = tree.query_radius(
                Point(entity.x, entity.y),
                radius=entity.collision_radius * 2
            )
            for other_point, dist in nearby:
                other = other_point.data
                if other.id > entity.id and dist <= entity.collision_radius + other.collision_radius:
                    collisions.append((entity, other))

        return collisions

Sai lầm điển hình

❌ Sai lầm 1: Không giới hạn MAX_DEPTH

Vấn đề: Points trùng tọa độ gây infinite recursion.

python

# SAI: Hai tài xế cùng tọa độ → subdivide vĩnh viễn
class BadQuadtree:
    def insert(self, point):
        if len(self.points) >= self.CAPACITY:
            self._subdivide()  # Loop forever!

Tại sao sai: Nếu 5 points có cùng tọa độ, chia bao nhiêu lần vẫn không phân tách được → stack overflow.

python

# ĐÚNG: Giới hạn depth, chấp nhận overflow ở leaf
if self.depth >= self.MAX_DEPTH:
    self.points.append(point)  # Chấp nhận > CAPACITY ở max depth
    return True

❌ Sai lầm 2: Rectangular query cho circular search

Vấn đề: Trả về points nằm ngoài bán kính.

python

# SAI: Góc hình vuông nằm ngoài hình tròn
def find_nearby(center, radius):
    rect = Rect(center.x, center.y, radius, radius)
    return tree.query(rect)  # Trả về cả points ở 4 góc!

Tại sao sai: Hình vuông có cạnh = 2r bao quanh hình tròn bán kính r. Góc vuông nằm ngoài hình tròn → kết quả sai.

python

# ĐÚNG: Rectangular query + circular filter
def find_nearby(center, radius):
    rect = Rect(center.x, center.y, radius, radius)
    candidates = tree.query(rect)
    return [p for p in candidates
            if distance(p, center) <= radius]

❌ Sai lầm 3: Không rebuild khi data thay đổi

Vấn đề: Tài xế di chuyển nhưng Quadtree không cập nhật.

python

# SAI: Tài xế di chuyển nhưng vẫn nằm ở vị trí cũ trong tree
driver.x = new_x
driver.y = new_y
# Quadtree vẫn lưu vị trí cũ!

Tại sao sai: Quadtree không tự cập nhật khi point di chuyển. Kết quả query sẽ trả về vị trí cũ.

python

# ĐÚNG: Rebuild periodic hoặc remove + re-insert
# Cách 1: Rebuild toàn bộ mỗi N giây
tree = Quadtree(bounds)
for driver in active_drivers:
    tree.insert(Point(driver.x, driver.y, data=driver))

# Cách 2: Remove cũ + insert mới (cần Quadtree hỗ trợ delete)

Under the Hood

Hiệu năng

Thao tác	Average	Worst Case	Ghi chú
Insert	O(log N)	O(N)	Worst khi data tập trung một góc
Range Query	O(log N + K)	O(N)	K = số kết quả
Radius Query	O(log N + K)	O(N)	= Range + circular filter
Build	O(N log N)	O(N²)	Insert N points

Approach	Query (1M points)	Memory	Dynamic?
Brute-force	O(N) = 1M ops	O(N)	Có
Quadtree	O(log N + K) ≈ 20 + K	O(N)	Có
K-D Tree	O(√N + K) ≈ 1000 + K	O(N)	Khó
Grid Hash	O(1 + K)	O(grid × N)	Có

Nội bộ triển khai

Memory overhead: Mỗi internal node cần 4 pointers (NW, NE, SW, SE) + boundary coordinates. Với N points và capacity = 4, số nodes ≈ N/4 → overhead ≈ 25%.

Degenerate cases: Nếu tất cả points nằm trên một đường thẳng hoặc một điểm, tree suy biến thành linked list → O(N). MAX_DEPTH ngăn chặn worst case nhưng giảm resolution.

Dynamic updates: Quadtree tiêu chuẩn không hỗ trợ delete hiệu quả. Trong production (game, ride-sharing), thường rebuild toàn bộ tree mỗi frame/interval — với N = 10K-100K, rebuild vẫn đủ nhanh (< 10ms).

Trade-offs

Khi NÊN dùng	Khi KHÔNG NÊN dùng
Data 2D thay đổi liên tục	Data tĩnh (K-D Tree tốt hơn)
Nearest-neighbor, range query	Exact point lookup (Hash Map)
Game collision detection	Data 1D (Binary Search Tree)
Moderate N (10K-1M)	N > 10M (cần R-Tree hoặc Grid)
Cần code đơn giản	Cần worst-case guarantee (R-Tree)

Checklist ghi nhớ

✅ Checklist triển khai

Thiết kế

[ ] Xác định boundary chứa toàn bộ data points
[ ] Chọn CAPACITY (thường 4-8) và MAX_DEPTH (thường 10-15)
[ ] Quyết định strategy cho dynamic updates: rebuild vs remove/re-insert

Triển khai

[ ] MAX_DEPTH để ngăn infinite recursion với duplicate coordinates
[ ] Circular query = rectangular query + distance filter
[ ] Re-insert existing points khi subdivide

Production

[ ] Benchmark với data distribution thực tế (không chỉ random)
[ ] Monitor tree depth và balance — degenerate tree cần điều chỉnh
[ ] Coordinate conversion chính xác (lat/lng → meters cho distance)
[ ] Rebuild tree khi data distribution thay đổi đáng kể

Bài tập luyện tập

Bài 1: Insert và Query — Foundation

Đề bài: Tạo Quadtree cho bản đồ 100×100. Insert 8 points, thực hiện range query cho rectangle (20,20) đến (40,40).

🧠 Quiz

Câu hỏi: Quadtree với CAPACITY=4 và 8 points sẽ subdivide bao nhiêu lần (minimum)?

[ ] A. 0 lần
[x] B. 1 lần (root chia thành 4 children)
[ ] C. 2 lần
[ ] D. Phụ thuộc vào phân bố points Giải thích: Root chứa 4 points, khi insert point thứ 5, root subdivide thành 4 children. Nếu không child nào chứa > 4 points thì chỉ cần 1 lần subdivide. Nhưng đáp án chính xác nhất là D — phụ thuộc phân bố.

✅ Lời giải

python

tree = Quadtree(Rect(50, 50, 50, 50))
points = [Point(10,10), Point(20,20), Point(30,30), Point(40,40),
          Point(60,60), Point(70,70), Point(80,80), Point(90,90)]
for p in points:
    tree.insert(p)

results = tree.query(Rect(30, 30, 10, 10))  # center(30,30), half-size=10
print(f"Points in (20-40, 20-40): {len(results)}")
for p in results:
    print(f"  ({p.x}, {p.y})")

Bài 2: K-Nearest Neighbors — Intermediate

Đề bài: Triển khai find_k_nearest(center, k) trả về k points gần nhất. Hint: bắt đầu với radius nhỏ, tăng dần nếu chưa đủ k results.

🧠 Quiz

Câu hỏi: Cách nào hiệu quả nhất để tìm K-nearest với Quadtree?

[ ] A. Query toàn bộ tree, sort by distance, lấy top-K
[x] B. Bắt đầu radius nhỏ, tăng dần cho đến khi có >= K results
[ ] C. DFS toàn bộ tree từ gốc
[ ] D. Quadtree không hỗ trợ K-nearest Giải thích: Approach B (expanding radius) tận dụng pruning — bắt đầu nhỏ thì ít nodes cần xét. A đúng nhưng O(N log N). C không tận dụng spatial locality.

✅ Lời giải

python

def find_k_nearest(tree: Quadtree, center: Point, k: int) -> list[tuple[Point, float]]:
    radius = 1.0  # Bắt đầu nhỏ
    results = []
    while len(results) < k and radius < tree.boundary.hw * 2:
        results = tree.query_radius(center, radius)
        radius *= 2  # Double radius mỗi iteration
    return results[:k]

Phân tích: Mỗi iteration double radius → tối đa O(log(max_dim)) iterations. Mỗi query là O(log N + K). Tổng: O(log(max_dim) × (log N + K)).

Liên kết học tiếp

Từ khóa glossary: Quadtree, spatial indexing, nearest neighbor, range query, collision detection, K-D Tree, Region Quadtree, Point Quadtree

Tìm kiếm liên quan: quadtree là gì, tìm điểm gần nhất, spatial indexing, collision detection game, Uber driver matching

Quadtree — Spatial Indexing Engine ​

Bức tranh tư duy ​

Cốt lõi kỹ thuật ​

Point Quadtree vs Region Quadtree ​

Cơ chế Insert ​

Cơ chế Range Query ​

Triển khai đầy đủ ​

So sánh Quadtree với K-D Tree ​

Thực chiến ​

Tình huống: Nearest Driver Matching ​

Tình huống: Game Collision Detection ​

Sai lầm điển hình ​

❌ Sai lầm 1: Không giới hạn MAX_DEPTH ​

❌ Sai lầm 2: Rectangular query cho circular search ​

❌ Sai lầm 3: Không rebuild khi data thay đổi ​

Under the Hood ​

Hiệu năng ​

Nội bộ triển khai ​

Trade-offs ​

Checklist ghi nhớ ​

Bài tập luyện tập ​

Bài 1: Insert và Query — Foundation ​

Bài 2: K-Nearest Neighbors — Intermediate ​

Liên kết học tiếp ​

Quadtree — Spatial Indexing Engine

Bức tranh tư duy

Cốt lõi kỹ thuật

Point Quadtree vs Region Quadtree

Cơ chế Insert

Cơ chế Range Query

Triển khai đầy đủ

So sánh Quadtree với K-D Tree

Thực chiến

Tình huống: Nearest Driver Matching

Tình huống: Game Collision Detection

Sai lầm điển hình

❌ Sai lầm 1: Không giới hạn MAX_DEPTH

❌ Sai lầm 2: Rectangular query cho circular search

❌ Sai lầm 3: Không rebuild khi data thay đổi

Under the Hood

Hiệu năng

Nội bộ triển khai

Trade-offs

Checklist ghi nhớ

Bài tập luyện tập

Bài 1: Insert và Query — Foundation

Bài 2: K-Nearest Neighbors — Intermediate

Liên kết học tiếp