TỔNG QUAN CÁC HƯỚNG TIẾP CẬN XÂY DỰNG BẢN ĐỒ
Đặt Vấn đề
Ngày nay, bản đồ số đóng vai trò quan trọng trong giao thông vận tải, dần thay thế bản đồ giấy nhờ vào tính năng lưu trữ gọn nhẹ và khả năng truy vấn thông tin về đường đi, khoảng cách và vị trí một cách nhanh chóng qua GPS Nhiều nhóm tác giả đã đề xuất các phương pháp xây dựng bản đồ giao thông sử dụng GPS, nhằm tạo ra một bản đồ với dữ liệu và tính toán chính xác, giúp con người tham gia giao thông hiệu quả hơn.
Sơ lƣợc về hệ thống định vị toàn cầu GPS
Hệ thống GPS (Global Positioning System) được đưa vào sử dụng từ những năm
1960 bởi bộ quốc phòng Mỹ cho mục đích quân sự Ngày nay, hệ thống này đã được mở rộng cho phép dùng vào các mục đích dân sự
Hệ thống GPS có thể chia làm ba phân đoạn:
Hệ thống phân đoạn không gian hiện có 24 vệ tinh, trong đó 21 vệ tinh đang hoạt động và 3 vệ tinh dự phòng Những vệ tinh này bay quanh quỹ đạo trái đất ở độ cao khoảng 20.200 km, với chu kỳ bay ổn định.
Hình 1: Ảnh 24 vệ tinh bay quanh quỹ đạo của trái đất
Phân đoạn điều khiển bao gồm các thiết bị mặt đất cho phép giám sát và điều khiển vệ tinh, hiện có 5 trạm điều khiển Trạm chính nằm tại Colorado Springs, Mỹ, trong khi bốn trạm khác được đặt tại Hawaii, Ascencio, Diego Garcia và Kwajalein ở khu vực xích đạo Các trạm này có nhiệm vụ giám sát hoạt động của vệ tinh và gửi tín hiệu điều khiển để hiệu chỉnh quỹ đạo của chúng.
- Phân đoạn người dùng: bao gồm toàn bộ các thiết bị cho phép thu tín hiệu GPS để định vị tọa độ
Các thông tin có thể thu được từ thiết bị thu GPS phổ biến là:
- Mã C/A (C/A code): đây là mã thô, độ chính xác thấp
- Mã P (P-code): đây là mã có độ chính xác cao
Các mã C/A được trộn với thông báo hàng hải và truyền trong sóng mang L1 Mã
P được trộn với các thông báo hàng hải và truyền qua sóng mang L2 Các máy thu GPS có hai loại:
- Một tần số (single frequency): chỉ thu được sóng L1
Hệ thống GPS hoạt động với hai tần số (Dual frequency), cho phép thu nhận sóng L1 và L2, mang lại độ chính xác cao hơn so với thiết bị một tần số Cụ thể, thiết bị một tần số (mã C/A) có độ chính xác sai lệch khoảng 3m, trong khi thiết bị hai tần số (mã P) đạt độ chính xác vào khoảng 0,3m Tuy nhiên, độ chính xác này còn bị ảnh hưởng bởi các yếu tố như thời tiết và địa hình, chẳng hạn như núi hoặc nhà cao tầng Hệ thống GPS cung cấp tọa độ không gian ba chiều, bao gồm vĩ độ, kinh độ và cao độ.
Vị trí của một điểm trên mặt đất được xác định dựa trên khoảng cách đến các vệ tinh và trung tâm tín hiệu mặt đất Khoảng cách này được tính bằng công thức Quãng đường = Vận Tốc × Thời Gian, trong đó vận tốc là tốc độ truyền tín hiệu và thời gian được đo bằng đồng hồ nguyên tử chính xác Khi nhận tín hiệu từ vệ tinh, thiết bị tự động tính toán khoảng cách giữa nó và vệ tinh Theo lý thuyết, chỉ cần 3 vệ tinh để xác định vị trí (tọa độ x, y, z), nhưng do sai số, cần thêm 1 vệ tinh nữa để có độ chính xác cao hơn, tổng cộng là 4 vệ tinh Hệ thống có thể xử lý tín hiệu từ nhiều hơn 4 vệ tinh, giúp tăng cường độ chính xác trong việc xác định vị trí.
Hình 2: Xác định vị trí một điểm trên mặt đất
GPS cung cấp vị trí rất chính xác, tuy nhiên vẫn tồn tại sai số có thể từ vài mét đến vài trăm mét Sai số hiển thị trên thiết bị phản ánh khả năng sai lệch dựa trên phân tích tín hiệu thu nhận Điều này xảy ra do sự chuyển động liên tục của các vệ tinh, trái đất và con người trong thời gian thực.
- Công nghệ Assisted-GPS (A-GPS)
A-GPS (Assisted-GPS) là công nghệ nâng cao cho hệ thống GPS, sử dụng các trạm trung gian trên mặt đất, chủ yếu là cột phát sóng của nhà mạng trong khu vực Hệ thống A-GPS hoạt động thông qua một máy chủ, nơi tính toán và xử lý các tín hiệu cùng thông số nhận được Để nhận tín hiệu từ máy chủ, thiết bị sử dụng A-GPS cần kết nối qua internet, bao gồm các kết nối 3G, GPRS hoặc wifi.
Hệ thống GPS nhận tín hiệu từ ba vệ tinh và một trạm mặt đất, giúp cải thiện tốc độ và độ ổn định của tín hiệu Trạm mặt đất gần hơn và có sóng mạnh hơn, đồng thời là một điểm cố định, từ đó nâng cao hiệu suất của hệ thống định vị.
A-GPS hoạt động nhanh và ổn định hơn so với GPS truyền thống Tuy nhiên, A-GPS không hoàn toàn thay thế GPS mà chỉ hỗ trợ thêm Trong trường hợp không có sóng di động hoặc không có kết nối với máy chủ hay trạm BTS, thiết bị vẫn có khả năng định vị thông qua GPS như bình thường.
Hình 3: Trạm trung gian hỗ trợ hệ thống GPS
Trong luận văn này, tôi áp dụng công nghệ A-GPS để hỗ trợ xác định tọa độ trong quá trình thu thập dữ liệu Công nghệ A-GPS cho phép tính toán tọa độ một cách nhanh chóng và chính xác, do đó giảm thiểu sai số trong quá trình thu thập thông tin.
Các hướng tiếp cận xây dựng bản đồ giao thông sử dụng GPS tracks
Năm 2009, Cao, Lili và John Krumm đã đề xuất một phương pháp phân cụm để xây dựng bản đồ giao thông Nhóm tác giả đã trình bày cách chuyển đổi dữ liệu GPS thô thành một mạng lưới đường bộ có khả năng định tuyến Phương pháp này bao gồm việc làm mịn và xử lý dấu vết GPS để cải thiện độ chính xác của bản đồ.
Nhóm tác giả đã phát triển 10 con đường dựa trên dữ liệu GPS thô ban đầu bằng cách sử dụng thuật toán phân cụm để xây dựng một đồ thị mô tả các nút và cạnh, từ đó hình thành mạng lưới đường bộ định tuyến Để giải quyết những thách thức liên quan đến độ chính xác của các con đường do dữ liệu GPS bị lỗi hoặc nhiễu tín hiệu, nhóm đã đề xuất một cách tiếp cận gồm hai bước nhằm cải thiện độ tin cậy của thông tin đường đi.
Bước đầu tiên trong việc xử lý dữ liệu GPS là làm rõ các con đường được hình thành từ các dấu vết GPS lỗi bằng cách nhóm các dấu vết và điểm thuộc cùng một con đường lại với nhau.
Dựa trên kết quả từ Bước 1, nhóm tác giả áp dụng thuật toán để tạo ra một biểu đồ chỉ dẫn, mô tả sự kết nối hình học của mạng lưới đường bộ.
Kết quả thực nghiệm cho thấy đồ thị tạo ra giữ được các kết nối quan trọng và đặc tính hình học của mạng lưới đường bộ trong khu vực thử nghiệm So với bản đồ Microsoft Bing, hầu hết các tuyến đường đều trùng khớp, tuy nhiên vẫn có một số tuyến đường không khớp do hai nguyên nhân chính.
Con đường mới xây dựng vẫn chưa được cập nhật trên bản đồ Microsoft Bing, trong khi những con đường đã bị phá bỏ để xây dựng vẫn còn tồn tại trên nền tảng này.
Dữ liệu thu thập trên các đoạn đường cao tốc có hạn chế dẫn đến việc tạo ra những phân đoạn không đáng tin cậy, do đó chúng đã bị loại bỏ và không được hiển thị trong đồ thị.
Nhóm tác giả đã phát triển một phương pháp mới để tạo ra bản đồ đường định tuyến từ dữ liệu GPS thu thập trên các phương tiện giao thông Phương pháp này giúp thay thế quy trình truyền thống tốn kém chi phí và công sức khi sử dụng thiết bị GPS chuyên dụng để tạo bản đồ.
1.3.2 Thuật toán ƣớc lƣợng mật độ hạt nhân
Năm 2012, Xuemei Liu, James Biagioni, Yin Wang và Yanmin Zhu đã đề xuất việc sử dụng thuật toán ước lượng mật độ hạt nhân nhằm xây dựng bản đồ suy luận với độ chính xác cao.
Liu và các cộng sự đã áp dụng thuật toán ước lượng mật độ hạt nhân (KDE) để xử lý và khôi phục dữ liệu GPS có mật độ thấp, từ đó cập nhật và suy luận ra bản đồ đường bộ với độ chính xác cao.
Liu đang giải quyết bài toán sử dụng thuật toán KDE để cải thiện dữ liệu GPS có mật độ thấp và nhiễu Thuật toán này được thực hiện qua các bước cụ thể nhằm nâng cao độ chính xác của dữ liệu GPS.
B1: bắt đầu bằng cách đếm xem có bao nhiêu đoạn đi qua mỗi điểm
B2: sau đó tìm ra những đoạn đường đồng mức dựa trên ngưỡng mật độ của các điểm nhất định (ngưỡng trên 80 được coi là đường giao thông)
B3: dựa vào sơ đồ Voronoi trích xuất đường trung tâm
B4: loại bỏ những đường viền bên ngoài của đường trung tâm và những đoạn có ngưỡng thấp
B5: so sánh và cập nhật với bản đồ thật mặt đất
Kết quả thử nghiệm thuật toán với dữ liệu mật độ thấp từ Chicago và dữ liệu taxi tại Thượng Hải đã xác định ngưỡng khoảng cách giữa các đường viền là 20m Thuật toán KDE không chỉ đảm bảo tính chính xác cao mà còn loại bỏ các đường viền và đoạn đường ảo, từ đó tạo ra đường trung tâm phù hợp và giảm thiểu nhiễu từ dữ liệu GPS.
Qua thử nghiệm bằng thực tế nhóm tác giả thấy thuật toán KDE thời gian xử lý nhanh và phù hợp trong xử lý bộ dữ liệu lớn
1.3.3 Thuật toán xử lý đường cong tại các nút giao nhau
Năm 2010, Chen, Daniel và các cộng sự đã đề xuất giải pháp tái tạo mạng lưới đường bộ từ tập hợp dấu vết GPS của các con đường, đảm bảo độ chính xác cao.
Nhóm tác giả đã đề xuất một thuật toán nhằm xử lý tập hợp các con đường trong mặt phẳng đa giác, đặc biệt chú trọng đến các đường cong tại các nút giao nhau Thuật toán này được xây dựng dựa trên 12 xác định hợp lý trong việc xây dựng bản đồ.
Thuật toán bắt đầu bằng việc tạo ra một b-net từ tập hợp các điểm mẫu, trong đó b-net bao gồm các điểm S được chọn từ đầu vào sao cho tất cả các điểm trên các con đường đầu vào nằm trong khoảng cách b = 2 + 6 và có ít nhất một điểm trong S Tiếp theo, sơ đồ Voronoi được tính toán, trong đó mỗi điểm Voronoi tương ứng với một ô Voronoi, bao gồm tất cả các điểm gần hơn tới điểm đó so với các điểm Voronoi khác Các cạnh của sơ đồ Voronoi là những điểm có khoảng cách bằng nhau tới hai điểm Voronoi gần nhất, trong khi các đỉnh là những điểm có khoảng cách bằng nhau tới ít nhất ba điểm Voronoi gần nhất Cuối cùng, từ một đồ thị con của hai đồ thị Delaunay, thuật toán xây dựng cấu trúc đồ thị để tái tổ chức các con đường ban đầu, tạo nền tảng cho việc xây dựng một đồ thị đại diện cho biểu đồ mạng lưới đường cơ bản.
1 Tìm một b-net của những đường đầu vào trong đó b = 2 + 6 và là một tham số đầu vào biểu thị chiều rộng đường
2 Tính toán sơ đồ Voronoi V (S)
3 Đánh dấu các phần tử trên sơ đồ Voronoi, tính toán đồ thị và các chuỗi ban đầu
4 Tính toán một đường cong đa giác đại diện cho mỗi loại của liên kết và xây dựng đồ thị cấu trúc
5 Đánh dấu liên kết và tìm chuỗi thứ hai
Mục tiêu của luận văn
Nghiên cứu hiện tại tập trung vào việc xây dựng bản đồ giao thông từ dữ liệu GPS tracks thu thập từ các phương tiện Tuy nhiên, các phương pháp này vẫn chưa ghi nhận được các thuộc tính quan trọng khác của tuyến đường như tên và loại đường.
Trong luận văn này, chúng tôi trình bày một quy trình nhằm thu thập và xử lý dữ liệu từ các bản theo dõi GPS, từ đó xây dựng các tuyến đường giao thông với các thuộc tính đi kèm như tên và lộ trình.
ĐỀ XUẤT QUY TRÌNH XÂY DỰNG BẢN ĐỒ GIAO THÔNG SỬ DỤNG GPS TRACKS
Mục tiêu
Mục tiêu của bài viết là đề xuất và triển khai quy trình thu thập dữ liệu GPS tracks, nhằm xây dựng bản đồ giao thông một cách nhanh chóng với thông tin chi tiết về tên các tuyến đường.
Quy trình xây dựng một bản đồ giao thông hoàn thiện
- Xây dựng ứng dụng thu thập dữ liệu GPS chạy trên smartphone
- Cài đặt ứng dụng thu thập dữ liệu GPS trên smartphone
- Thu thập dữ liệu GPS bằng smartphone trên các tuyến đường
- Xử lý dữ liệu GPS thu được bằng thuật toán xấp xỉ đoạn thẳng
- Xây dựng chương trình tạo ra bản đồ mới có độ chính xác cao từ dữ liệu GPS đã được xử lý.
Xây dựng ứng dụng thu thập dữ liệu GPS trên smartphone
Chương trình thu thập dữ liệu GPS trên smartphone chạy hệ điều hành Android, sử dụng công nghệ định vị GPS qua mạng 3G (A-GPS) để xác định tọa độ (kinh độ, vĩ độ) tại từng điểm trên đường đi Mỗi thời điểm, chương trình ghi lại tọa độ, tạo thành một tập hợp các điểm Những điểm này sẽ được nối lại, hình thành một đường dấu vết do GPS tạo ra.
Sơ Đồ Khối Của Chương Trình:
Hình 4: Sơ đồ khối chương trình thu thập dữ liệu GPS
Thuật toán xấp xỉ chuỗi dữ liệu GPS
Sau khi thu thập dữ liệu bằng thiết bị di động, mỗi tuyến đường sẽ tương ứng với một chuỗi các điểm Tuy nhiên, việc giữ nguyên dữ liệu này sẽ làm tăng kích thước dữ liệu bản đồ và kéo dài thời gian xử lý Các thuật toán như tìm đường đi ngắn nhất chỉ cần các điểm đặc trưng, ví dụ, chỉ cần điểm đầu và điểm cuối của một đoạn thẳng Do đó, cần rút gọn dữ liệu, chỉ giữ lại những điểm đặc trưng nhất trên con đường Chúng tôi đề xuất thuật toán xấp xỉ chuỗi điểm GPS để giảm kích thước dữ liệu Thuật toán này sẽ được mô tả chi tiết trong phần tiếp theo.
- Giả sử có chuỗi các điểm GPS là : A1, A2, ,A7 và ngưỡng đặt ra là esp
- khoảng cách từ A2, A3, A4, A5, A6 tới đường nối A1A7 lần lượt là: h2, h3, h4, h5, h6
- Điều kiện để dữ lại điểm đặc trưng là những điểm có h ≥ esp, những điểm không thỏa mãn được loại bỏ
- Theo dữ liệu ở trên thì ta sẽ thu được chuỗi các điểm GPS mới là: A1, A2,A5, A7
- Trường hợp không có điểm nào thỏa mãn điều kiện esp thì đoạn thẳng đó là điểm đầu và điểm cuối của chuỗi dữ liệu GPS
Mô tả thuật toán bằng code giả sau:
Function reduce(L) Đầu vào (Input) : Một danh sách L các điểm trên một tuyến đường
19 Đầu ra (Output) : Một danh sách L‟ các điểm đặc trưng của tuyến đường đó Begin
P= điểm thuộc L có khoảng cách đến đoạn [p1,p2] là lớn nhất ;
Phần cài đặt được trình bày ở phần Phụ lục
20 Hình 5a Đường Bà Triệu trước khi lấy sấp xỉ Hình 5b: Đường Bà Triệu sau khi lấy sấp xỉ
Tổng hợp dữ liệu
Sau khi xử lý dữ liệu GPS bằng thuật toán xấp xỉ đoạn thẳng, chúng ta thu được tập dữ liệu các con đường mới Dựa trên dữ liệu đã được xử lý, chúng tôi tiến hành tổng hợp và ghép lại để tạo ra một bản đồ hoàn chỉnh.
Hình 6: ảnh bản đồ được tạo ra từ dữ liệu GPS tại khu vực quận hoàn kiếm hà nội
Module tính điểm giao cắt giữa các đường trên bản đồ
Dựa trên tính chất của đường thẳng trong hình học, chúng tôi phát triển module tính toán các điểm giao nhau giữa các con đường trên bản đồ Đầu vào là một tập hợp các đường thẳng, và đầu ra là tập hợp các đường thẳng có điểm giao cắt tại những vị trí giao nhau.
Xét hai đường thẳng có phương trình lần lượt là: x + y + =0 và x + y + =0
Mô tả bằng mã giả:
If nếu c1/b1b2 return thì trả vể kết quả hai đường thẳng trùng nhau
Nếu hai đường thẳng song song, hàm sẽ trả về kết quả tương ứng Nếu b1 bằng 0 và c1/a1a2, hàm sẽ trả về hai đường thẳng trùng nhau Trong trường hợp khác, hàm sẽ trả về hai đường thẳng song song.
23 return trả về hai đường thẳng trùng nhau Else return trả về hai đường thẳng song song
Else y = (a2*c1-a1*c2)/(a1*b2-a2*b1); x = (b1*c2-c1*b2)/(a1*b2-a2*b1); return trả về kết quả hai đường thẳng giao nhau tại điểm có tọa độ (x,y) end
Cài đặt thuật toán tìm đường đi ngắn nhất trên bản đồ đã xây dựng
Trong luận văn này, chúng tôi triển khai thuật toán tìm đường đi ngắn nhất để đánh giá độ chính xác của bản đồ xây dựng so với các bản đồ hiện có Chúng tôi đã sử dụng thuật toán Dijkstra, được đặt theo tên nhà khoa học máy tính Edsger Dijkstra, để giải quyết bài toán đường đi ngắn nhất trong đồ thị có hướng hoặc vô hướng mà không có cạnh trọng số âm.
Bài toán đặt ra là tìm khoảng cách d(u0,v) từ một đỉnh u0 đã cho đến một đỉnh v bất kỳ trong đồ thị liên thông có trọng số G=(V,E), đồng thời xác định đường đi ngắn nhất từ u0 đến v Thuật toán Dijkstra thực hiện bằng cách xác định tuần tự các đỉnh có khoảng cách đến u0 từ nhỏ đến lớn Đỉnh đầu tiên có khoảng cách nhỏ nhất chính là u0 với d(u0,u0) = 0 Tiếp theo, trong số các đỉnh khác không phải là u0, thuật toán tìm đỉnh có khoảng cách k1 đến u0 nhỏ nhất, và đỉnh này phải là một trong các đỉnh kề với u0.
24 và v ≠ u1, tìm đỉnh có khoảng cách k2 đến u0 là nhỏ nhất Đỉnh này phải là một trong các đỉnh kề với u0 hoặc với u1 Giả sử đó là u2: d(u0,u2) = k2
Tiếp tục như trên, cho đến bao giờ tìm được khoảng cách từ u0 đến mọi đỉnh v của G Nếu V={u0, u1, , un} thì:
Procedure Dijkstra ( G=(V,E) là đơn đồ thị liên thông, có trọng số với trọng số dương)
{G có các đỉnh a=u0, u1, , un=z và trọng số m(ui,uj), với m(ui,uj) = ∞ nếu (ui,uj) không là một cạnh trong G} for i= 1 to n
S= V // a u= a while S ≠ ỉ begin for tất cả các đỉnh v thuộc S if L(u) +m(u,v) < L(v) then L(v) = L(u)+m(u,v) u= đỉnh thuộc S có nhãn L(u) nhỏ nhất
// L(u): độ dài đường đi ngắn nhất từ a đến u }
- Minh họa thuật toán bằng đồ thị vô hướng G như hình vẽ dưới
Hình 7: Mô tả thuật toán Dijkstra bằng đồ thị vô hướng Đường đi ngắn nhất từ đỉnh s=1 tới các đỉnh còn lại trên đồ thị G
Bảng mô tả các bước trong thuật toán
Xét lần lượt các đỉnh N
Chiều dài của đường đi ngắn nhất từ đỉnh s=1 đến các đỉnh khác
Một số ảnh bản đồ đƣợc xây dựng và so sánh với các bản đồ khác
2.8.1 Ảnh bản đồ hoàn chỉnh khu vực Hoàn Kiếm, Hà Nội
Hình 8: Ảnh bản đồ khu vực Hoàn Kiếm
2.8.2 Hình ảnh bản đồ khu vực hoàn kiếm so sánh trên nền bản đồ open Street Map
Hình 9: So sánh bản đồ xây dựng được với open Street Map
2.8.3 Hình ảnh bản đồ khu vực hoàn kiếm so sánh trên nền bản đồ Google Map
Hình 10: So sánh bản đồ xây dựng được với Google Map
2.8.4 Hình ảnh tìm đường đi ngắn nhất từ điểm A tới B Điểm A có tọa độ (21.01918,105.85851), điểm B có tọa độ (21.01751,105.84166) đường đi ngắn nhất đi từ A đến B trên bản đồ xây dựng được của khu vực hoàn kiếm là 2,06 km
Hình 11: Tìm đường đi ngắn nhất từ điềm A tới điểm B trên bản đồ xây dựng được
2.8.5 Hình ảnh tìm đường đi ngắn nhất từ điểm A đến điểm B trên GoogleMaps Điểm A có tọa độ (21.01918,105.85851), điểm B có tọa độ (21.01751,105.84166) trên bản đồ Google Map khu vực hoàn kiếm đường đi ngắn nhất từ A đến B là 2,1 km
Hình 12: Tìm đường đi ngắn nhất từ điểm A tới điểm B trên google map
KẾT QUẢ THỰC NGHIỆM ĐẠT ĐƯỢC
Kết quả đạt đƣợc
Nghiên cứu của chúng tôi đã dẫn đến việc phát triển thành công bộ công cụ và phần mềm tạo bản đồ giao thông với độ chính xác cao, được áp dụng thực tế.
Chúng tôi đã phát triển phần mềm để xây dựng bản đồ khu vực Hà Nội, cung cấp thông tin cần thiết về vị trí và lộ trình đi ngắn nhất Phần mềm giúp người tham gia giao thông tiết kiệm thời gian và chi phí Ngoài ra, người dùng có thể dễ dàng cập nhật các con đường mới trên bản đồ Bất kỳ ai có kiến thức cơ bản về công nghệ thông tin đều có thể tham gia xây dựng bản đồ giao thông tại khu vực mình sinh sống Bộ công cụ này được phát triển trên nền tảng Java và sử dụng công nghệ GPS, đảm bảo các chức năng của một bản đồ giao thông hoàn chỉnh.
Đánh giá
Một trong những thách thức trên bản đồ giao thông là xác định đường đi ngắn nhất giữa hai điểm Để đánh giá độ chính xác của bản đồ, chúng tôi đã so sánh đường đi ngắn nhất trên bản đồ của mình với đường đi ngắn nhất trên Google Maps, sử dụng một tập hợp ngẫu nhiên các cặp đỉnh nguồn-đích.
Chọn ngẫu nhiên 30 cặp điểm nguồn-đích, xây dựng bảng so sánh
STT Điểm nguồn Điểm đích Khoảng cách trên bản đồ đƣợc xây dựng (km)
Khoảng cách trên google maps (km)
Google Maps hiện nay là ứng dụng bản đồ hàng đầu, và trong nghiên cứu này, tôi đã sử dụng Google Maps để đánh giá độ chính xác của bản đồ xây dựng Từ 30 cặp điểm ngẫu nhiên, có 19 cặp cho thấy bản đồ xây dựng cung cấp kết quả tìm đường ngắn nhất tương đương hoặc tốt hơn so với Google Maps Cụ thể, khoảng 63% kết quả trên bản đồ xây dựng đạt chất lượng tốt, trong khi 37% còn lại bị ảnh hưởng bởi sai số hoặc tín hiệu GPS kém, dẫn đến sự khác biệt về khoảng cách so với Google Maps.
Các điểm đã đạt đƣợc
- Xây dựng được chương trình lấy dữ liệu GPS chạy trên hệ điều hành android
- Xây dựng được các modul chương trình tạo ra bản đồ hoàn chỉnh có độ chính xác cao:
+ Modul xử lý dữ liệu GPS thu thập được, bằng phương pháp xấp xỉ đoạn thẳng
+ Modul tổng hợp dữ liệu tạo ra một bản đồ hoàn chỉnh từ dữ liệu GPS đã được xử lý
+ Modul phát hiện các nút giao nhau giữa các con đường trên bản đồ
- Cài đặt thuật toán tìm đường đi ngắn nhấn trên bản đồ
3.4 Các điểm chưa đạt được, hướng phát chiển
Chương trình được phát triển chủ yếu nhằm chứng minh các đề xuất về thuật toán trong luận văn, tuy nhiên chưa xem xét nhiều yếu tố khác như hướng di chuyển và các đường một chiều.
Chương trình này sử dụng dữ liệu GPS với tọa độ kinh độ và vĩ độ để xác định lộ trình ngắn nhất mà không cần ánh xạ tìm kiếm theo tên đường Đây cũng là hướng phát triển chính của luận văn trong thời gian tới.
