Cấu trúc dữ liệu và Giải thuật Bài 67: Hình học tính toán nâng cao (Computational Geometry) - Thuật toán Line Sweep và kiểm tra giao nhau.

Bước sang mảng Hình học tính toán (Computational Geometry), chúng ta đối mặt với một nhóm bài toán đòi hỏi sự kết hợp tinh tế giữa đại số tuyến tính và cấu trúc dữ liệu.

Hãy tưởng tượng bạn đang xây dựng một tính năng bản đồ số hoặc hệ thống quản lý quy hoạch đô thị (GIS) tại Hasaki hoặc hệ thống hạ tầng: Khi người dùng vẽ hàng chục ngàn đoạn thẳng đại diện cho các tuyến đường, hệ thống cần ngay lập tức phát hiện xem có bất kỳ hai đoạn đường nào cắt nhau hay không để cảnh báo xung đột thiết kế.

Phản xạ đầu tiên của lập trình viên là sử dụng phương pháp vét cạn (Brute-force): Lấy từng đoạn thẳng đem so sánh giao điểm với tất cả các đoạn thẳng còn lại. Độ phức tạp thời gian sẽ là $O(N^2)$. Khi số lượng đoạn thẳng lên tới $10^5$, thuật toán sẽ tiêu tốn hàng nghìn tỷ phép tính và làm tê liệt hệ thống. Để giảm thời gian xuống mức $O(N \log N)$, các nhà khoa học máy tính đã phát minh ra một trong những chiến thuật quét thông minh nhất: Thuật toán Line Sweep (Quét đường thẳng).

1. Tư duy cốt lõi của Thuật toán Line Sweep

Thay vì nhìn toàn bộ mặt phẳng 2D cùng một lúc, thuật toán Line Sweep hoạt động giống hệt như một chiếc máy quét Radar (hoặc tia laser) di chuyển từ trái sang phải dọc theo trục $x$.

• Đường quét dừng lại tại các Sự kiện (Events) quan trọng — chính là các điểm đầu (Start Point) và điểm cuối (End Point) của các đoạn thẳng.

• Khi đường quét di chuyển, nó duy trì một Cấu trúc dữ liệu trạng thái (Active Set / Sweep-line Status) lưu trữ tất cả các đoạn thẳng mà đường quét đang cắt qua tại thời điểm $x$ hiện tại.

• Bí quyết tối ưu: Thay vì kiểm tra tất cả các cặp đoạn thẳng trên bản đồ, thuật toán chứng minh được rằng hai đoạn thẳng cắt nhau thì chúng nhất định phải nằm kề nhau trong cấu trúc trạng thái của đường quét dọc theo trục $y$. Do đó, ta chỉ cần kiểm tra giao nhau giữa các đoạn thẳng láng giềng trực tiếp ngay khi chúng xuất hiện hoặc rời đi.

2. Tiền đề Hình học: Xác định hướng (Orientation / Cross Product)

Trước khi thực hiện Line Sweep, chúng ta cần một công cụ toán học cơ bản để xác định xem ba điểm $P, Q, R$ quay theo chiều kim đồng hồ (Clockwise) hay ngược chiều kim đồng hồ (Counter-clockwise). Công thức tích có hướng (Cross Product) của hai véc-tơ $\vec{PQ}$ và $\vec{PR}$ được sử dụng để kiểm tra nhanh vị trí tương đối và hiện tượng cắt nhau giữa hai đoạn thẳng mà không cần tính toán số thực phức tạp:

$$\text{Orientation}(P, Q, R) = (Q.x - P.x) \cdot (R.y - Q.y) - (Q.y - P.y) \cdot (R.x - Q.x)$$

• Nếu kết quả $> 0$: Quay theo chiều kim đồng hồ.

• Nếu kết quả $< 0$: Quay ngược chiều kim đồng hồ.

• Nếu kết quả $= 0$: Ba điểm thẳng hàng (Collinear).

3. Triển khai Cấu trúc Hướng và Kiểm tra Giao nhau bằng Golang

Dưới đây là mã nguồn Golang chuẩn mực thực hiện các phép toán hình học cơ bản để kiểm tra hai đoạn thẳng có giao nhau hay không — khối xây dựng nền tảng cho các thuật toán Line Sweep nâng cao:

Go

package main

import "fmt"

type Point struct {
	X, Y int64
}

type Segment struct {
	P1, P2 Point
}

// Hàm tính hướng (Orientation) của 3 điểm P, Q, R
func orientation(p, q, r Point) int {
	val := (q.X-p.X)*(r.Y-q.Y) - (q.Y-p.Y)*(r.X-q.X)
	if val == 0 {
		return 0 // Thẳng hàng
	}
	if val > 0 {
		return 1 // Theo chiều kim đồng hồ
	}
	return 2 // Ngược chiều kim đồng hồ
}

// Kiểm tra điểm q có nằm trên đoạn thẳng pr hay không (dùng khi thẳng hàng)
func onSegment(p, q, r Point) bool {
	return q.X <= max(p.X, r.X) && q.X >= min(p.X, r.X) &&
		q.Y <= max(p.Y, r.Y) && q.Y >= min(p.Y, r.Y)
}

// Kiểm tra xem đoạn thẳng p1q1 có giao nhau với p2q2 hay không
func DoIntersect(p1, q1, p2, q2 Point) bool {
	o1 := orientation(p1, q1, p2)
	o2 := orientation(p1, q1, q2)
	o3 := orientation(p2, q2, p1)
	o4 := orientation(p2, q2, q1)

	// Trường hợp tổng quát: Cắt nhau thông thường
	if o1 != o2 && o3 != o4 {
		return true
	}

	// Các trường hợp đặc biệt khi các điểm thẳng hàng (Collinear)
	if o1 == 0 && onSegment(p1, p2, q1) { return true }
	if o2 == 0 && onSegment(p1, q2, q1) { return true }
	if o3 == 0 && onSegment(p2, p1, q2) { return true }
	if o4 == 0 && onSegment(p2, q1, q2) { return true }

	return false
}

func max(a, b int64) int64 {
	if a > b { return a }
	return b
}

func min(a, b int64) int64 {
	if a < b { return a }
	return b
}

func main() {
	s1 := Segment{P1: Point{0, 0}, P2: Point{4, 4}}
	s2 := Segment{P1: Point{0, 4}, P2: Point{4, 0}}

	intersect := DoIntersect(s1.P1, s1.P2, s2.P1, s2.P2)
	if intersect {
		fmt.Println("Hai đoạn thẳng CẮT NHAU!")
	} else {
		fmt.Println("Hai đoạn thẳng KHÔNG CẮT NHAU!")
	}
}

4. Phân tích Hiệu năng (Big-O)

• Thuật toán Vét cạn (Brute-force): Kiểm tra mọi cặp đoạn thẳng tốn $O(N^2)$.

• Thuật toán Line Sweep (Bentley-Ottmann Algorithm): Sử dụng Hàng đợi ưu tiên (Priority Queue) để quản lý các sự kiện điểm và Cây tìm kiếm cân bằng (Balanced BST) để quản lý tập hợp trạng thái đoạn thẳng active, đạt độ phức tạp tối ưu $O(N \log N)$.

• Không gian (Space Complexity): $O(N)$ để lưu trữ các sự kiện và trạng thái trên đường quét.

5. Ứng dụng Thực tế trong Kỹ thuật Phần mềm

Hình học tính toán và Line Sweep không chỉ là lý thuyết hàn lâm mà vận hành ngầm trong nhiều hệ thống lõi:

• Hệ thống Bản đồ & GIS (Geographic Information Systems): Google Maps, OpenStreetMap sử dụng các biến thể của Line Sweep để xử lý các lớp bản đồ không gian, phát hiện điểm giao nhau giữa các tuyến đường, hoặc tính toán vùng chồng lấp giữa các đa giác (Polygon Overlays).

• Phần mềm Đồ họa CAD & Thiết kế Vi mạch (PCB Routing): Các công cụ thiết kế bo mạch điện tử kiểm tra các đường mạch đồng có bị vô tình cắt nhau (short circuit) hay không bằng thuật toán kiểm tra giao đoạn thẳng tốc độ cao.

• Mô phỏng Trò chơi & Phát hiện Va chạm (Collision Detection): Trong lập trình game 2D/3D, việc tối ưu hóa kiểm tra va chạm giữa hàng loạt vật thể chuyển động được xử lý thông qua các thuật toán quét không gian.

Hình học tính toán khép lại một mảng kiến thức chuyên sâu. Trong bài học tiếp theo, chúng ta sẽ chuyển sang lĩnh vực toán học hệ thống và đại số cấu trúc để giải quyết các bài toán lũy thừa cực lớn với tốc độ chớp nhoáng.