Trilateration: định vị giao điểm

Ở bài trước, mèo con đã đo được khoảng cách tới từng vệ tinh. Nhưng biết “cách vệ tinh số 7 đúng 20.000 km” thì bạn vẫn ở vô số chỗ: tất cả các điểm cách vệ tinh đó đúng 20.000 km nằm trên một mặt cầu bao quanh nó.

Một mặt cầu thì rộng mênh mông. Nhưng nếu biết khoảng cách tới nhiều vệ tinh, mỗi cái cho một mặt cầu, thì các mặt cầu giao nhau sẽ khoá dần vị trí lại. Kỹ thuật tìm vị trí từ nhiều khoảng cách như vậy gọi là trilateration. Để dễ nhìn, ta xét trong mặt phẳng - mặt cầu thành vòng tròn.

Kéo thử các 🛰️ vệ tinh và 🐱 máy thu bên dưới, và bấm đổi số vệ tinh để thấy vị trí bị khoá lại ra sao:

• ▸1 vệ tinh: bạn ở đâu đó trên một vòng tròn - vô số khả năng.
• ▸2 vệ tinh: hai vòng giao nhau còn 2 điểm (một là bạn, một là “điểm ma”).
• ▸3 vệ tinh: vòng thứ ba loại điểm ma, chốt lại đúng một điểm.

Không cần phép màu - chỉ là hình học. Lấy đúng ba vệ tinh trong mô phỏng: A ở (0,0), B ở (3,9), C ở (7,1), mỗi cái đo được khoảng cách 5. Giao hai vòng A và B trước, rồi để vòng C chọn ra điểm đúng:

import math

def giao_hai_duong_tron(c1, c2):
    (x1, y1, r1), (x2, y2, r2) = c1, c2
    dx, dy = x2 - x1, y2 - y1
    d = math.hypot(dx, dy)
    a = (r1**2 - r2**2 + d**2) / (2 * d)
    h = math.sqrt(r1**2 - a**2)
    xm, ym = x1 + a * dx / d, y1 + a * dy / d
    return [(xm + h * dy / d, ym - h * dx / d), (xm - h * dy / d, ym + h * dx / d)]

A = (0, 0, 5)
B = (3, 9, 5)
C = (7, 1, 5)

print("2 ve tinh -> 2 diem kha di:")
for p in giao_hai_duong_tron(A, B):
    tren_C = abs(math.dist(p, (C[0], C[1])) - C[2]) < 1e-9
    print(f"  ({p[0]:.0f}, {p[1]:.0f})  ->  nam tren vong tron C? {'co' if tren_C else 'khong'}")
print("=> Ve tinh thu 3 chot lai mot diem: (3, 4)")

2 ve tinh -> 2 diem kha di:
  (3, 4)  ->  nam tren vong tron C? co
  (0, 5)  ->  nam tren vong tron C? khong
=> Ve tinh thu 3 chot lai mot diem: (3, 4)

Đúng như mô phỏng: hai vệ tinh cho hai điểm (3,4) và (0,5); vệ tinh thứ ba giữ lại đúng điểm nằm trên cả ba vòng - vị trí thật của mèo con.

Đời thực là không gian 3 chiều, nên mỗi khoảng cách là một mặt cầu chứ không phải vòng tròn. Hai mặt cầu giao nhau thành một vòng tròn; mặt cầu thứ ba cắt vòng tròn đó tại 2 điểm. Một điểm nằm ngay trên mặt đất, điểm kia văng tít ngoài không gian - máy thu loại ngay điểm vô lý đó.

Nhớ “khoảng cách giả” (pseudorange) ở bài trước chứ? Đồng hồ máy thu lệch khiến cả ba khoảng cách đều sai một lượng chung. Tức là ngoài ba ẩn vị trí x, y, z, còn một ẩn thứ tư: Δt - độ lệch đồng hồ máy thu. Bốn ẩn thì cần bốn phương trình, nên phải có bốn vệ tinh.

• ▸Ẩn cần tìm: x, y, z (vị trí) và Δt (sai lệch đồng hồ máy thu) - tổng 4 ẩn.
• ▸Mỗi vệ tinh cho một phương trình; cần tối thiểu 4 vệ tinh.
• ▸Vệ tinh thứ tư vừa định vị, vừa “sửa” luôn đồng hồ rẻ tiền của máy thu.

Giải xong, máy thu có toạ độ x, y, z trong hệ gắn với tâm Trái Đất. Bước cuối là đổi sang kinh độ, vĩ độ, độ cao dựa trên mô hình hình dạng Trái Đất gọi là ellipsoid WGS84 - rồi mới chấm được lên bản đồ thành cái chấm xanh quen thuộc.