Dự án Bản đồ Điều hướng, Dữ liệu đường được lưu trữ/đại diện như thế nào?

Question

Các hệ thống định vị như Garmin và TomTom luôn thu hút tôi. Tôi đã muốn triển khai các ứng dụng bản đồ/điều hướng nhỏ để thử các thuật toán đường dẫn khác nhau và mở rộng kiến ​​thức về chúng.

Đây là một câu hỏi hai phần:

1.) Làm thế nào là dữ liệu được lưu trữ đồ? - Khi bạn có mạng lưới đường, dữ liệu này thường được lưu trữ như thế nào? Phần nào của dữ liệu được giữ lại để tạo lại bản đồ sau này? Mỗi con đường được lưu trữ như một loạt các điểm mà nó thay đổi hướng? Những loại định dạng tệp nào được lưu trữ trong dữ liệu này? Có các thư viện công khai có sẵn để dễ dàng phân tích cú pháp các tệp này không? Có ai có chi tiết cụ thể về cách dữ liệu bản đồ/đường được lưu trữ/đại diện hay không sẽ rất hữu ích.

2.) Navigation/pathing - Khi làm pathing cơ bản về dữ liệu bản đồ này (a la Garmin) là giả định của tôi đúng rằng nó được chuyển đổi sang một đồ thị có hướng? Mỗi đường có giao nhau với một đỉnh có cạnh có trọng số khoảng cách giữa các đỉnh không? Đây là những gì tôi đã suy nghĩ về làm như vậy tôi có thể thử một số thuật toán đường dẫn cơ bản nổi tiếng và xem những gì tôi nhận được.

Tôi đã xem this dữ liệu bản đồ công khai có sẵn ở Hoa Kỳ nhưng tôi không chắc chắn nó được thể hiện như thế nào và liệu nó có đủ chi tiết để tôi có thể xây dựng đồ thị trực tiếp của tôi không.

Nếu có bất kỳ thông tin nào tôi đánh giá cao nó. Kiến thức chi tiết hơn bạn có tốt hơn.

Answer 1

Tôi không biết chi tiết về đơn vị hệ thống điều hướng, nhưng trong thế giới GIS tiêu chuẩn, dữ liệu bản đồ được lưu trữ cơ bản như một tập hợp các đa giác, đường thẳng và điểm, được mô tả bởi tọa độ của nó (và chiếu được sử dụng và một số khác thông số). Ví dụ: một trong các định dạng phổ biến nhất, shapefiles, được mô tả here, và tiêu chuẩn định dạng dựa trên cơ sở dữ liệu là here.

Tôi đã sử dụng thành công mô hình lưu trữ này để hiển thị đường và tính toán tuyến đường, sử dụng PostgreSQL, PostGIS và PGRouting. Tính toán được thực hiện bằng cách sử dụng các thuật toán đồ thị thông thường và dữ liệu được lưu trữ trong định dạng phổ biến cũng được lưu trữ dưới dạng biểu đồ để cho phép ứng dụng của chúng. Tôi không thể ngoại suy trải nghiệm đó với một thiết bị nhúng vì chúng có khả năng làm điều đó rất khác nhau với khả năng tính toán hạn chế của họ. Họ rất có thể tính toán trước rất nhiều thứ.

Đối với một cách tiếp cận hơi khác nhau để lưu trữ, kiểm tra OpenStreetMap

Answer 2

Đối với tốc độ vẽ được cải tiến với chi phí dung lượng lưu trữ nhiều hơn và độ phân giải hạn chế, nhiều ứng dụng sẽ sử dụng một định dạng raster tham chiếu hình học như GeoTiff.

Với những nhận xét khá dai dẳng bởi Zich thấp hơn

"Số liệu theo vector trong tất cả các hệ thống Navigation không có ngoại lệ!"

Tôi nghĩ tôi sẽ thêm một chút vào phần trên. Thứ nhất, tôi sẽ xác định hệ thống điều hướng như một hệ thống hỗ trợ bạn đến nơi bạn muốn đi dựa trên vị trí hiện tại của bạn, thường bằng cách chi phí một số tuyến đường thay thế có thể và giới thiệu chi phí thấp nhất. Các tuyến đường có thể có thể được quyết định theo phương thức vận chuyển, xe ô tô vẫn ở trên các con đường, ví dụ như những người đi bộ trên đồi thì không. Chi phí của các tuyến đường có thể thay đổi theo phương thức vận chuyển cũng như các yêu cầu của người dùng.Ô tô có thể muốn tuyến đường nhanh nhất dựa trên tốc độ đường, xe tải có thể muốn tuyến đường tiết kiệm nhiên liệu nhất, người đi bộ trên đồi có thể muốn tuyến đường trực tiếp an toàn nhất, thuyền hoặc máy bay có thể muốn tuyến đường tránh hệ thống thời tiết nguy hiểm, đồng thời giảm thiểu chi phí nhiên liệu và thời gian .

Ở mức đơn giản nhất, bản đồ và la bàn là hệ thống điều hướng. Thay thế bản đồ bằng một màn hình nhỏ, một bản đồ raster có thể mở rộng và GPS và bạn vẫn có một hệ thống định vị. Hầu hết các hệ thống định vị hàng hải từ thấp đến trung bình vẫn hoạt động theo cách này, với các biểu đồ đại diện cho đường bờ biển và đáy biển và GPS để cung cấp cho bạn vị trí và tiếng vọng cho âm thanh sâu.

Khi kết thúc tiên tiến hơn, các hệ thống điều hướng robot tự động chẳng hạn như Mars Rover navigation system tạo mô hình DTM trên cơ sở để điều hướng phạm vi ngắn và vệ tinh thu thập DEM cho điều hướng phạm vi dài hơn.

Để đề xuất rằng tất cả các hệ thống điều hướng hoạt động giống như thiết bị Garmin hoặc Tom Tom của người tiêu dùng là một giả định khá ngây thơ. FWIW, nhiều thiết bị Garmin hiện đại cũng bao gồm raster based DEM data, nơi mà giá cao GPS chi phí thấp có thể cực kỳ không chính xác.

Answer 3

Cách chính xác được lưu trữ tùy thuộc vào định dạng; có rất nhiều định dạng GIS khác nhau. GDAL là một thư viện miễn phí tuyệt vời để đọc (gần như) tất cả chúng.

Đường thông thường sẽ được lưu trữ trong tệp dưới dạng "lớp đường", đó là tập hợp các ô vuông có siêu dữ liệu được đính kèm. Vì vậy, mỗi con đường sẽ có một loạt các đỉnh và tùy thuộc vào chất lượng dữ liệu của bạn, hy vọng sẽ có thông tin như chúng là một chiều hay không, ước tính tốc độ và một số loại kết nối id.

Có, chúng thường được chuyển đổi thành đồ thị được hướng dẫn để giải quyết. Cạnh trọng lượng có thể là khoảng cách hoặc, hữu ích hơn, thời gian để đi du lịch cạnh đó.

Giải quyết nhanh chóng là sự cân bằng giữa tiền xử lý và dung lượng lưu trữ (thiết bị được nhúng có thể đòi hỏi sự lựa chọn khác ở đây đối với PC). Có một số thuật toán rất thú vị để làm điều đó.

Answer 4

Mohammed: Được rồi, tôi không đi sâu vào chi tiết ở đây vì câu hỏi ban đầu có vẻ khá thoải mái ở khía cạnh đó. Nếu bạn không quen thuộc với lý thuyết đồ thị, có thể là một ý tưởng hay để thực hiện một chút đọc ngay bây giờ - Wikipedia là tốt cho phần giới thiệu.

Điều thường xảy ra là trong dữ liệu GIS, các con đường được lưu trữ dưới dạng các polylines có siêu dữ liệu đính kèm. Đó là tốt để hiển thị chúng trên màn hình vv, nhưng để có thể điều hướng chúng, bạn cần phải biết cái nào được kết nối với nhau. Vì vậy, trong siêu dữ liệu thường có một id nút cho mỗi đầu của con đường, vì vậy bạn có thể nói "đây là đoạn đường 457, nó đi từ nút 332 đến nút 667". Vì vậy, khi bạn đọc dữ liệu GIS, bạn xây dựng một biểu diễn của nó như là một tập hợp các nút được kết nối bởi vòng cung (ví dụ: biểu đồ).

Nếu siêu dữ liệu đó không khả dụng, bạn có thể phỏng đoán từ đó đường có cùng tọa độ bắt đầu/kết thúc (đây là trường hợp với một số dữ liệu GIS không tuyệt vời). Bit "hướng" chỉ có nghĩa là các con đường có hướng - một số có thể được di chuyển dọc theo hai hướng, nhưng một số khác chỉ là một chiều.

Thuật toán điển hình để tìm đường dẫn thông qua thuật toán là thuật toán Dijkstra; các dẫn xuất khác nhau được sử dụng trong thực tế. Về cơ bản có liên quan đến việc di chuyển từ nút này sang nút khác dọc theo vòng cung của biểu đồ, vì vậy bạn cần cấu trúc dữ liệu thích hợp để hỗ trợ điều đó.

Hy vọng rằng sẽ giúp ...

Answer 5

Các câu trả lời trước đây đều đề cập đến hệ thống GIS.Đây không phải là cách PND (Thiết bị Điều hướng Di động) hoạt động. Chúng quá đơn giản để chạy phần mềm GIS cấp cho máy tính để bàn/workstattion.

Thay vào đó, PND lưu trữ thông tin khá nhiều như Simucal được giả định. Đường được chia thành các đoạn. Điều này giúp mô hình đơn giản hơn rất nhiều. Trong một phân đoạn, các thuộc tính như tốc độ tối đa không thay đổi.

Vì mục đích lập kế hoạch, đoạn đường hoạt động như các cạnh trong biểu đồ. Đối với mỗi nút, các nút đến và đi đều được lưu trữ. Lập kế hoạch sau đó được thực hiện bằng cách sử dụng thuật toán A * đã sửa đổi. Trọng lượng cạnh thường không phải là khoảng cách, nhưng thời gian di chuyển ước tính (hoặc trong trường hợp TomTom s, thực tế, thời gian đo). Tuy nhiên,

Mạng đường thường rất kỳ lạ và A * bình thường là khởi động chậm. Khi di chuyển từ thị trấn này sang thị trấn khác, A * sẽ dành quá nhiều thời gian thu thập thông tin qua thị trấn bắt đầu. Tuy nhiên, con người chúng ta biết cách tốt nhất là sử dụng đường cao tốc khi đi xa hơn. Đó là những gì họ đang xây dựng cho. PND cũng thích đường cao tốc. Và như đường cao tốc là rất hiếm, điều này tiết kiệm rất nhiều bộ nhớ.

Tối ưu hóa khác là tìm kiếm tiến và lùi; bạn có kế hoạch từ cả hai phía hướng tới một số điểm giữa. Lợi thế lớn của việc này là nếu bạn rẽ sai, bạn có thể tìm kiếm lại từ một điểm bắt đầu mới. Cây tìm kiếm ngược không thay đổi vì đích đến của bạn không di chuyển.

Answer 6

Nếu bạn muốn một số mã để xem xét để biết một số ý tưởng về cách các ứng dụng định tuyến hoạt động, hãy thử xem một số ứng dụng định tuyến được liên kết từ openstreetmap.org wiki. Navit và Gosmore là cả hai nguồn mở và khá dễ dàng để thiết lập đặc biệt.

Nic Roets, nhà phát triển ứng dụng Gosmore đã viết interesting post về các lựa chọn của mình để đại diện cho dữ liệu đường-vectơ mà bạn cũng có thể quan tâm.

Nếu bạn muốn xem Gosmore đang hoạt động, đó là phần phụ trợ của trang web định tuyến yournavigation.org dựa trên dữ liệu openstreetmap.