Cấu trúc dữ liệu và Giải thuật Bài 107: Hình học tính toán (Computational Geometry) - Xử lý tọa độ, đoạn thẳng và bao lồi (Convex Hull).

Trong hành trình giải quyết các bài toán kỹ thuật thực tế, thỉnh thoảng chúng ta phải rời khỏi thế giới của những con số thuần túy để bước vào không gian vật lý của tọa độ, mặt phẳng và hình học. Hình học tính toán (Computational Geometry) đóng vai trò cốt lõi trong nhiều hệ thống hiện đại như:

• Hệ thống thông tin địa lý (GIS) & Giao vận (Logistics): Tính toán vùng phủ sóng giao hàng, tối ưu hóa tuyến đường hoặc xác định xem xe tải có nằm trong vùng địa lý cho phép hay không (Geofencing).

• Hệ thống điều hướng & Robot tự hành (AGV): Phát hiện va chạm trong không gian nhà kho thông minh hoặc các hệ thống tín hiệu tự động.

• Đồ họa máy tính & Game Engine: Xử lý va chạm vật lý (Collision Detection) giữa các đối tượng đa giác.

Một trong những bài toán kinh điển và nền tảng nhất của hình học tính toán chính là Tìm bao lồi (Convex Hull).

1. Bao lồi (Convex Hull) là gì?

Cho một tập hợp gồm $N$ điểm trên mặt phẳng tọa độ 2D. Bao lồi của tập hợp điểm này được định nghĩa là đa giác lồi nhỏ nhất sao cho tất cả $N$ điểm đều nằm bên trong hoặc nằm trên cạnh của đa giác đó.

Hình dung một cách trực quan: Giống như bạn đóng các chiếc đinh lên một tấm gỗ phẳng, sau đó dùng một sợi dây thun co giãn kéo căng bao trọn toàn bộ các chiếc đinh rồi thả ra. Vòng dây thun ôm sát các điểm ngoài cùng sẽ tạo thành hình dạng của Convex Hull.

2. Công cụ toán học cốt lõi: Tích có hướng của Vectơ (Cross Product)

Để xác định xem một điểm nằm bên trái hay bên phải của một đoạn thẳng (từ đó quyết định xem nó có thuộc bao lồi hay không), chúng ta sử dụng Tích có hướng (Cross Product) của hai vectơ.

Cho ba điểm $P_1(x_1, y_1)$, $P_2(x_2, y_2)$ và $P_3(x_3, y_3)$. Vectơ $\vec{P_1P_2}$ và $\vec{P_1P_3}$ có tích có hướng tính bằng công thức:

$$\text{cross} = (x_2 - x_1)(y_3 - y_1) - (y_2 - y_1)(x_3 - x_1)$$

• Nếu $\text{cross} > 0$: Điểm $P_3$ nằm ở bên trái đường thẳng đi qua $P_1$ và $P_2$ (quay theo chiều dương / ngược chiều kim đồng hồ).

• Nếu $\text{cross} < 0$: Điểm $P_3$ nằm ở bên phải (quay theo chiều âm / cùng chiều kim đồng hồ).

• Nếu $\text{cross} = 0$: Ba điểm thẳng hàng.

3. Thuật toán Andrew's Monotone Chain (Tính bao lồi $O(N \log N)$)

Một trong những thuật toán hiệu quả và dễ cài đặt nhất để tìm Convex Hull là Andrew's Monotone Chain. Ý tưởng chính:

1. Sắp xếp tất cả các điểm theo tọa độ $X$ tăng dần (nếu trùng $X$ thì sắp xếp theo $Y$).

2. Xây dựng Nửa bao dưới (Lower Hull) bằng cách duyệt từ trái qua phải và loại bỏ các điểm tạo thành góc lõm (quay phải).

3. Xây dựng Nửa bao trên (Upper Hull) bằng cách duyệt từ phải qua trái với logic tương tự.

4. Ghép nối hai nửa lại để tạo thành đa giác bao lồi hoàn chỉnh.

Độ phức tạp thời gian bị chi phối bởi bước sắp xếp ban đầu: $O(N \log N)$.

4. Hiện thực hóa Convex Hull bằng Golang

Đoạn code Golang dưới đây cài đặt thuật toán Andrew's Monotone Chain để tìm tập hợp các điểm tạo thành bao lồi:

Go

package main

import (
	"fmt"
	"math"
	"sort"
)

type Point struct {
	X, Y float64
}

// Tính tích có hướng của vector OA và OB tính từ điểm O
// Dương: rẽ trái, Âm: rẽ phải, 0: thẳng hàng
func crossProduct(o, a, b Point) float64 {
	return (a.X-o.X)*(b.Y-o.Y) - (a.Y-o.Y)*(b.X-o.X)
}

// Xây dựng Convex Hull bằng thuật toán Andrew's Monotone Chain
func ConvexHull(points []Point) []Point {
	n := len(points)
	if n <= 3 {
		return points
	}

	// Sắp xếp các điểm theo tọa độ X, nếu X bằng nhau thì theo Y
	sort.Slice(points, func(i, j int) bool {
		if points[i].X == points[j].X {
			return points[i].Y < points[j].Y
		}
		return points[i].X < points[j].X
	})

	var lower []Point
	// Xây dựng Lower Hull
	for i := 0; i < n; i++ {
		for len(lower) >= 2 && crossProduct(lower[len(lower)-2], lower[len(lower)-1], points[i]) <= 0 {
			lower = lower[:len(lower)-1]
		}
		lower = append(lower, points[i])
	}

	var upper []Point
	// Xây dựng Upper Hull
	for i := n - 1; i >= 0; i-- {
		for len(upper) >= 2 && crossProduct(upper[len(upper)-2], upper[len(upper)-1], points[i]) <= 0 {
			upper = upper[:len(upper)-1]
		}
		upper = append(upper, points[i])
	}

	// Loại bỏ điểm trùng lặp ở cuối mỗi nửa
	lower = lower[:len(lower)-1]
	upper = upper[:len(upper)-1]

	// Ghép nối Lower và Upper thành Convex Hull hoàn chỉnh
	hull := append(lower, upper...)
	return hull
}

func main() {
	// Danh sách các điểm ngẫu nhiên trên mặt phẳng 2D
	points := []Point{
		{0, 0}, {1, 1}, {2, 2}, {3, 1}, {3, 3},
		{1, 3}, {3, 0}, {0, 3}, {1.5, 1.5},
	}

	hull := ConvexHull(points)

	fmt.Println("Các điểm tạo thành Bao lồi (Convex Hull):")
	for _, p := range hull {
		fmt.Printf("(%.1f, %.1f)\n", p.X, p.Y)
	}
}

5. Ứng dụng thực tế

• Kiểm tra Geofencing: Khi một tài xế hoặc phương tiện di chuyển, hệ thống cần kiểm tra nhanh xem tọa độ GPS hiện tại có nằm trong vùng bao lồi của khu vực dịch vụ hay không.

• Tối ưu hóa đường đi cho Robot trong nhà kho: Giúp robot tự hành xác định đường biên của các chướng ngại vật để lập quỹ đạo di chuyển an toàn mà không va đập.

Hình học tính toán đòi hỏi sự cẩn trọng tuyệt đối với các sai số dấu phẩy động (Floating-point precision) — một chủ đề mà các kỹ sư phần cứng và hệ thống nhúng rất quen thuộc.