Quad tree

Chào các bạn, đã có khi nào bạn đi hội họp xong, anh em bỗng có ý tưởng đi ăn, rồi bạn lên google map tìm kiếm quán ăn trong khu vực gần hiện tại hay chưa. Bạn có thắc mắc google làm cách nào có thể nhanh chóng tìm ra được quán ăn gần nhất không. Hôm nay mình muốn chia sẻ một trong những thuật toán tìm điểm trong 1 khu vực cho trước, đó chính là QuadTree.

Định nghĩa

Quad tree là một cấu trúc dữ liệu dạng cây được sử dụng để phân chia không gian hai chiều thành các vùng con nhỏ hơn. Mỗi nút trong cây có thể có tối đa bốn nút con và n điểm (capacity = n). Quad tree thường được sử dụng trong các ứng dụng như tìm kiếm phạm vi (range searching), nén ảnh, và các thuật toán liên quan đến không gian 2D. Bài hôm nay mình tập trung tìm hiểu cách Quadtree tìm kiếm các điểm trong 1 không gian cho trước.

QuadTree

Ý tưởng

• Quadtree chia 1 không gian 2 chiều làm 4: Đông Bắc (NE), Tây Bắc (NW), Đông nam (SE) và Tây nam (SW). Mỗi không gian chỉ chứa tối đa n điểm cho trước. Nếu 1 không gian có nhiều hơn n điểm, nó sẽ phải chia tiếp thành 4 không gian con.

• Khi tìm kiếm các điểm trong 1 không gian, chỉ cần tìm các điểm trong không gian mà nó có đè lên phạm vi cần tìm, qua đó giảm thời gian tìm kiếm.

Cách thực hiện

• Trước hết là xây dựng quadtree: cần xử lí khi thêm mới một điểm vào, và thủ tục chia không gian thành 4 không gian nhỏ hơn nếu số điểm vượt quá capacity.

• Đến bước query, ta cần kiểm tra không gian cần tìm với không gian cho trước có đè nhau không, nếu có thì cần kiểm tra các điểm xem thuộc không gian tìm kiếm hay không, và nếu không gian đó có không gian nhỏ hơn, thì cần tìm tiếp trên các không gian nhỏ hơn bằng đệ quy.

• Thời gian tạo cây là O(nlog(n)) và thời gian tìm kiếm là O(log(n) + k) với n là tổng số điểm và k là số điểm được kiểm tra.

Implement thuật toán

• Class khai báo điểm: Point

• Class khai báo không gian Rectangle gồm các phương thức Contains(Point) kiểm tra 1 điểm có tồn tại trong không gian đang xét hay không và Intersects(Rectangle) kiểm tra 2 không gian có đè lên nhau hay không.

• Class QuadTree chứa các thông tin về không gian, số điểm, sức chứa, các không gian con nếu có (class Quadtree).

• Subdivide() thủ tục chia quadtree làm 4.

• Insert(Point) để thêm 1 điểm vào quadtree

• Query(Range) trả về các điểm trong khu vực tìm kiếm.

Tham khảo

• https://www.youtube.com/watch?v=M4lR_Va97cQ