Cấu trúc dữ liệu và Giải thuật Bài 113: Thuật toán quét mặt phẳng (Sweep-Line Algorithm) - Giải quyết bài toán giao cắt đoạn thẳng và xử lý không gian.

Trong các bài toán hình học tính toán và xử lý không gian 2D, một trong những thách thức tính toán nặng nề nhất là Xác định giao cắt giữa các đoạn thẳng (Line Segment Intersection).

Giả sử bạn có $10,000$ đoạn thẳng trên một bản đồ GIS hoặc hệ thống CAD thiết kế vi mạch (VLSI). Nếu sử dụng phương pháp vét cạn (brute-force) kiểm tra từng cặp đoạn thẳng giao nhau, độ phức tạp sẽ là $O(N^2)$, dẫn đến việc cạn kiệt tài nguyên tính toán khi quy mô dữ liệu lớn.

Để tối ưu hóa bài toán này xuống mức $O((N + K) \log N)$ (với $K$ là số lượng điểm giao nhau thực tế), các nhà khoa học máy tính đã phát triển một kỹ thuật tư duy không gian cực kỳ tinh tế: Thuật toán quét mặt phẳng (Sweep-Line Algorithm), hay còn gọi là Thuật toán Bentley-Ottmann.

1. Trực giác đằng sau Thuật toán Quét mặt phẳng

Thay vì cố gắng nhìn toàn bộ mặt phẳng 2D cùng một lúc, hãy tưởng tượng bạn dùng một đường thẳng đứng (Sweep-Line) đặt ở biên bên trái nhất của không gian và quét (sweep) từ trái sang phải giống như một tia quét của radar hoặc máy quét tài liệu.

Khi đường quét di chuyển, nó chỉ quan tâm đến các sự kiện xảy ra tại các tọa độ $X$ cụ thể:

1. Điểm đầu mút bên trái của một đoạn thẳng: Đoạn thẳng này bắt đầu tham gia vào không gian quan sát. Ta cần kiểm tra xem nó có cắt các đoạn thẳng đang nằm liền kề với nó theo chiều dọc hay không.

2. Điểm đầu mút bên phải của một đoạn thẳng: Đoạn thẳng này kết thúc hành trình và rời khỏi không gian quan sát. Ta loại bỏ nó khỏi hệ thống và kiểm tra các đoạn thẳng trước đó nay trở thành liền kề nhau.

3. Điểm giao nhau giữa hai đoạn thẳng: Khi đường quét chạm tới một điểm cắt, thứ tự sắp xếp theo chiều dọc của hai đoạn thẳng đó đổi chỗ cho nhau, kích hoạt việc kiểm tra các giao cắt tiềm năng mới.

2. Hai cấu trúc dữ liệu cốt lõi

Để thuật toán Sweep-Line vận hành mượt mà, ta cần duy trì hai cấu trúc dữ liệu quan trọng:

1. Hàng đợi sự kiện (Event Queue - $Q$):

   • Thường được cài đặt bằng một Min-Priority Queue (Hàng đợi ưu tiên / Heap) sắp xếp các điểm sự kiện theo tọa độ $X$ tăng dần (nếu trùng $X$ thì xét theo $Y$).

   • Lưu trữ các điểm đầu mút của đoạn thẳng và các điểm giao nhau phát sinh trong quá trình quét.

2. Cấu trúc trạng thái (Status Structure - $T$):

   • Thường được cài đặt bằng một Cây tìm kiếm nhị phân tự cân bằng (Balanced BST).

   • Lưu trữ tập hợp các đoạn thẳng đang cắt ngang đường thẳng đứng (Sweep-Line) tại tọa độ $X$ hiện tại, được sắp xếp theo thứ tự tọa độ $Y$ từ dưới lên trên. Cấu trúc này giúp ta tìm nhanh chóng các đoạn thẳng nằm ngay phía trên hoặc phía dưới một đoạn thẳng khác trong thời gian $O(\log N)$.

3. Hiện thực hóa cấu trúc quản lý sự kiện Sweep-Line bằng Golang

Đoạn code Golang dưới đây cài đặt phần khung cốt lõi của một hệ thống xử lý sự kiện quét mặt phẳng, định nghĩa các loại sự kiện (Điểm đầu, Điểm cuối) và cơ chế xử lý theo thứ tự tọa độ không gian:

Go

package main

import (
	"container/heap"
	"fmt"
	"sort"
)

type Point struct {
	X, Y float64
}

type Segment struct {
	P1, P2 Point
	ID     int
}

// Loại sự kiện trong Sweep-Line
type EventType int

const (
	Start EventType = iota
	End
)

type Event struct {
	X       float64
	Y       float64
	Type    EventType
	Segment Segment
}

// Priority Queue cho Event Queue sắp xếp theo X tăng dần
type PriorityQueue []Event

func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool {
	if pq[i].X == pq[j].X {
		return pq[i].Y < pq[j].Y
	}
	return pq[i].X < pq[j].X
}
func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }

func (pq *PriorityQueue) Push(x interface{}) {
	*pq = append(*pq, x.(Event))
}

func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	*pq = old[0 : n-1]
	return item
}

// Kiểm tra giao cắt cơ bản giữa hai đoạn thẳng
func DoIntersect(s1, s2 Segment) bool {
	// Hàm kiểm tra định hướng (Orientation / Cross Product) thu gọn
	// Trả về true nếu hai đoạn thẳng s1 và s2 cắt nhau
	// (Phần cài đặt chi tiết hình học tính toán định hướng vector)
	return true // Placeholder mô phỏng logic
}

func main() {
	// Khởi tạo các đoạn thẳng mẫu trong không gian 2D
	segments := []Segment{
		{P1: Point{0, 0}, P2: Point{4, 4}, ID: 1},
		{P1: Point{0, 4}, P2: Point{4, 0}, ID: 2},
	}

	pq := &PriorityQueue{}
	heap.Init(pq)

	// Đẩy các sự kiện đầu mút vào Event Queue
	for _, s := range segments {
		// Đảm bảo P1 có X nhỏ hơn P2
		p1, p2 := s.P1, s.P2
		if p1.X > p2.X || (p1.X == p2.X && p1.Y > p2.Y) {
			p1, p2 = p2, p1
		}

		heap.Push(pq, Event{X: p1.X, Y: p1.Y, Type: Start, Segment: s})
		heap.Push(pq, Event{X: p2.X, Y: p2.Y, Type: End, Segment: s})
	}

	fmt.Println("Đã khởi tạo Event Queue thành công cho thuật toán Sweep-Line.")
	fmt.Printf("Tổng số sự kiện đầu mút cần quét: %d\n", pq.Len())

	// Mô phỏng vòng lặp quét mặt phẳng
	for pq.Len() > 0 {
		event := heap.Pop(pq).(Event)
		if event.Type == Start {
			fmt.Printf("Đường quét chạm ĐIỂM BẮT ĐẦU đoạn thẳng %d tại tọa độ (%.1f, %.1f)\n", event.Segment.ID, event.X, event.Y)
			// Thêm vào Status Structure, kiểm tra giao cắt với lân cận
		} else {
			fmt.Printf("Đường quét chạm ĐIỂM KẾT THÚC đoạn thẳng %d tại tọa độ (%.1f, %.1f)\n", event.Segment.ID, event.X, event.Y)
			// Xóa khỏi Status Structure, kiểm tra giao cắt giữa các lân cận mới kề nhau
		}
	}
}

4. Ứng dụng thực tế của Thuật toán Quét mặt phẳng

• Hệ thống CAD & Thiết kế vi mạch (PCB Design Rules Checking): Kiểm tra nhanh xem các đường mạch đồng trên bo mạch có bị giao cắt hoặc vi phạm khoảng cách tối thiểu (Clearance) hay không.

• Hệ thống thông tin địa lý (GIS): Chồng lớp bản đồ (Polygon Overlay) để tính toán diện tích giao nhau giữa các vùng đất quy hoạch, bản đồ thời tiết hoặc bản đồ giao thông.

• Đồ họa máy tính & Xử lý đa giác: Xác định vùng hiển thị hoặc thuật toán tô màu vùng khép kín (Polygon Filling).

Thuật toán quét mặt phẳng chứng minh rằng việc biến đổi một bài toán hình học 2D phức tạp thành một chuỗi các sự kiện tuyến tính theo trục thời gian/không gian ($X$-axis) sẽ mở ra cánh cửa giải quyết các bài toán lớn với hiệu năng tối ưu.