Thuật toán Haversine: Cách lập trình tính "Đường chim bay" chuẩn xác như Google Maps

Trong thế giới của những tọa độ, khoảng cách ngắn nhất giữa hai trái tim có thể là một ánh mắt, nhưng khoảng cách ngắn nhất giữa hai điểm trên bản đồ lại là một bài toán hình học hóc búa. Với một Backend Engineer, chúng ta không nhìn Trái Đất như một tấm bản đồ phẳng trên màn hình Monitor; chúng ta nhìn nó như một khối cầu lồi lõm đầy rẫy những phép tính lượng giác. Nếu bạn vẫn đang dùng Pythagoras để tính khoảng cách giữa hai vị trí GPS, có lẽ bạn đang vô tình khiến Shipper của mình phải 'bay' xuyên lòng đất thay vì lướt trên mặt cầu. Hôm nay, hãy cùng mình giải mã Haversine – thuật toán đứng sau những đường kẻ 'chim bay' đầy mê hoặc trên các ứng dụng Map hiện đại.

1. Bài toán: khi đường thẳng không thực sự "thẳng"

Hãy tưởng tượng bạn đang xây dựng một ứng dụng giao hàng. Bạn có tọa độ GPS của shipper $(lat_1, lon_1)$ và khách hàng $(lat_2, lon_2)$. Nhiệm vụ của bạn là tính khoảng cách ngắn nhất giữa hai điểm này.

Nếu áp dụng định lý Pythagoras $c = \sqrt{a^2 + b^2}$ trên mặt phẳng 2D, bạn sẽ sai số rất lớn. Tại sao? Vì Trái Đất của chúng ta không phẳng, nó là một hình cầu (gần đúng). Khoảng cách ngắn nhất giữa hai điểm trên mặt cầu là một cung tròn, hay còn gọi là Đường chim bay (Great-circle distance).

2. Giải pháp: Công thức Haversine

Để tính toán khoảng cách này, các kỹ sư thường dùng công thức Haversine. Nó cho phép tính toán khoảng cách giữa 2 điểm trên mặt cầu dựa trên vĩ độ (latitude) và kinh độ (longitude).

Công thức toán học:

$$d = 2r \arcsin\left(\sqrt{\sin^2\left(\frac{\Delta \phi}{2}\right) + \cos(\phi_1)\cos(\phi_2)\sin^2\left(\frac{\Delta \lambda}{2}\right)}\right)$$

Trong đó:

• $\phi_1, \phi_2$: Vĩ độ của hai điểm (tính bằng radian).
• $\Delta \phi, \Delta \lambda$: Độ chênh lệch vĩ độ và kinh độ.
• $r$: Bán kính trung bình của Trái Đất (khoảng 6,371 km).

3. Hiện thực hóa bằng Code (Golang style)

Là một Gopher, mình sẽ minh họa bằng Go để bạn thấy sự tối ưu và rõ ràng. Lưu ý quan trọng nhất: Các hàm lượng giác trong lập trình luôn nhận giá trị Radian, không phải Degree (độ).

package main

import (
	"fmt"
	"math"
)

const earthRadius = 6371 // Bán kính Trái Đất đơn vị km

// Độ sang Radian
func degreesToRadians(d float64) float64 {
	return d * math.Pi / 180
}

// Hàm tính khoảng cách đường chim bay
func Haversine(lat1, lon1, lat2, lon2 float64) float64 {
	phi1 := degreesToRadians(lat1)
	phi2 := degreesToRadians(lat2)
	deltaPhi := degreesToRadians(lat2 - lat1)
	deltaLambda := degreesToRadians(lon2 - lon1)

	a := math.Sin(deltaPhi/2)*math.Sin(deltaPhi/2) +
		math.Cos(phi1)*math.Cos(phi2)*
			math.Sin(deltaLambda/2)*math.Sin(deltaLambda/2)

	c := 2 * math.Atan2(math.Sqrt(a), math.Sqrt(1-a))

	return earthRadius * c
}

func main() {
	// Ví dụ: Từ Landmark 81 đến Bitexco (TP.HCM)
	dist := Haversine(10.7947, 106.7218, 10.7717, 106.7044)
	fmt.Printf("Khoảng cách đường chim bay: %.2f km\n", dist)
}

4. Những lưu ý cho Senior khi triển khai thực tế

Race Condition & Performance

Nếu hệ thống của bạn cần tính khoảng cách cho hàng triệu cặp tọa độ mỗi giây (ví dụ: tìm Shipper gần nhất):

• Bounding Box: Trước khi dùng Haversine (tốn tài nguyên CPU cho lượng giác), hãy dùng một "cái hộp" tọa độ đơn giản (min/max Lat/Lon) để loại biên các điểm quá xa.
• Spatial Index: Sử dụng Redis Geo hoặc PostGIS. Các công cụ này đã được tối ưu hóa cực tốt các thuật toán không gian bên dưới lớp C/C++.

Độ chính xác

Trái Đất không phải hình cầu hoàn hảo mà hơi dẹt ở hai cực (hình Ellipsoid). Haversine có sai số khoảng 0.5%. Nếu dự án của bạn làm về tên lửa hành trình hay đo đạc địa chất chính xác cao, hãy tìm hiểu thuật toán Vincenty – phức tạp hơn nhưng chính xác đến milimet.

Lời kết

Thuật toán Haversine là "vũ khí" cơ bản nhưng cực kỳ mạnh mẽ trong túi đồ nghề của một Backend Engineer. Hiểu rõ bản chất của nó giúp bạn không chỉ viết code đúng, mà còn biết cách tối ưu hệ thống khi dữ liệu phình to.

Chúc bạn có những trải nghiệm thú vị khi "bay" cùng các tọa độ!