지도 내비게이션 프로젝트, 도로 데이터는 일반적으로 어떻게 저장되고 표현됩니까?

Question

Garmin과 TomTom 같은 탐색 시스템은 항상 나를 매료 시켰습니다. 난 다양한 경로 알고리즘을 시도하고 그들에 대한 지식을 확대하는 작은지도/탐색 응용 프로그램을 구현 싶었어요.

1) 어떻게지도 데이터가

을 저장됩니다

이 두 부분의 질문은? - 도로 네트워크가있는 경우이 데이터는 일반적으로 어떻게 저장됩니까? 나중에지도를 재현하기 위해 어떤 부분의 데이터가 계속 유지됩니까? 각 도로가 방향을 변경하는 일련의 점으로 저장되어 있습니까? 이 데이터는 어떤 종류의 파일 형식으로 저장됩니까? 이러한 파일을 쉽게 파싱 할 수 있도록 대중적으로 사용할 수있는 라이브러리가 있습니까? 누구나지도/도로 데이터가 저장/표시되는 방법에 대한 세부 정보가 있으면 도움이 될 것입니다.

2.) 내비게이션/경로 지정 -이지도 데이터 (a la Garmin)에 대한 기본 경로 지정을 수행 할 때 이것이 유향 그래프로 변환된다고 올바르게 가정합니까? 각 도로 교차점은 꼭지점 사이의 거리에 가장자리가있는 꼭지점이 있습니까? 이것이 내가하는 일에 대해 생각해 봤던 것이므로 잘 알려진 몇 가지 기본 경로 지정 알고리즘을 시도하고 내가 얻은 것을 볼 수 있습니다.

미국에서 공개적으로 사용할 수있는지도 데이터는 this입니다.하지만 표현 방법과지도 된 그래프를 작성할 수있을 정도로 자세한 내용이 확실하지 않습니다.

누구든지 정보를 가지고 있으면 감사하겠습니다. 당신은 더 상세한 지식을 가지고 있습니다.

Answer 1

네비게이션 시스템 유닛에 대한 구체적인 내용은 모르지만 표준 GIS 세계에서지도 데이터는 기본적으로 다각형, 선 및 점의 모음으로 저장되며 각 좌표는 좌표 (및 사용 된 프로젝션 및 기타 매개 변수). 예를 들어 가장 일반적인 형식 인 쉐이프 파일 중 하나는 here,이고 데이터베이스 기반 형식 표준은 here입니다.

, PostGIS 및 PGRouting을 사용하여 도로 표시 및 경로 계산에이 저장소 모델을 성공적으로 사용했습니다. 계산은 일반적인 그래프 알고리즘을 사용하여 수행되며 일반 형식으로 저장된 데이터는 그래프로도 저장되어 응용 프로그램을 사용할 수 있습니다. 임베디드 디바이스에 제한된 컴퓨팅 용량을 제공 할 가능성이 매우 높기 때문에 그러한 경험을 임베디드 디바이스로 추정 할 수는 없습니다. 그들은 아마 많은 것들을 사전에 계산합니다. 스토리지 상당히 다른 방식 용

더 저장 제한된 해상도의 비용으로 개선 된 드로잉 속도를 들어 OpenStreetMap

Answer 2

를 확인 많은 애플리케이션은 GeoTiff 같은 지리 래스터 포맷을 사용할 것이다. 그

아래 Zich에 의해 오히려 집요 주석을 감안할 때

"데이터는 예외없이 모든 탐색 시스템에서 벡터에있다!"

위의 내용을 조금 더 추가 할 것으로 생각했습니다. 첫째, 네비게이션 시스템을 현재 위치에 따라 원하는 위치로 이동하는 방법을 지원하는 시스템으로 정의 할 수 있습니다. 일반적으로 가능한 대체 경로의 수를 계산하고 최저 비용을 추천합니다. 가능한 경로는 교통 수단에 의해 지시 될 수 있고, 예를 들어 자동차는 도로에 머물러 있지만 언덕 위 사람은 그렇지 않습니다. 노선의 원가 계산은 운송 수단 및 사용자 요구 사항에 따라 다를 수 있습니다.자동차는 도로 속도에 따라 가장 빠른 경로를 택할 수 있고 트럭은 연료 효율이 가장 좋은 경로를 원하고 힐 보행자는 가장 안전한 직접 경로를 원할 수 있습니다. 보트 또는 항공기는 연료 비용과 소요 시간을 최소화하면서 위험한 날씨 시스템을 피할 수있는 경로를 원할 수 있습니다. .

가장 간단한 수준에서지도와 나침반은 네비게이션 시스템입니다. 지도를 작은 화면, 확장 가능한 래스터지도 및 GPS로 바꾸십시오. 그래도 탐색 시스템이 있습니다. 대부분의 저급에서 중형까지의 해상 항법 시스템은 여전히 ​​해안선과 해저를 나타내는 차트와 위치를 제공하는 GPS 및 깊이에 울리는 에코 방식으로 작동합니다.

더 진보 된 스펙트럼의 경우, Mars Rover navigation system과 같은 자율 로봇 네비게이션 시스템은 단거리 네비게이션의 기초로 즉석에서 DTM 모델을 생성하고 더 긴 범위 네비게이션을위한 위성 수집 DEM을 생성합니다.

모든 탐색 시스템이 소비자 Garmin 또는 Tom Tom 장치처럼 작동하는 것을 제안하는 것은 다소 순진한 추측입니다. FWIW, 많은 현대 Garmin 장치도 raster based DEM data 저렴한 비용으로 GPS 높이는 격렬하게 부정확 수 있습니다 포함됩니다.

Answer 3

정확히 저장되는 방식은 형식에 따라 다릅니다. 다른 GIS 형식의 힙이 있습니다. GDAL은 (거의) 모두를 읽을 수있는 뛰어난 무료 라이브러리입니다.

일반적으로 도로는 파일에 "선 레이어"로 저장됩니다. 즉, 첨부 된 메타 데이터가있는 폴리 라인 세트입니다. 각 도로마다 일련의 정점이 있습니다. 데이터의 품질에 따라 일방 통행인지 아닌지, 속도 추정치 및 일종의 연결 ID와 같은 정보가있을 것입니다.

예, 정상적으로 해결을 위해 유향 그래프로 변환됩니다. 모서리 가중치는 거리이거나, 더 유용하게는 모서리를 이동하는 데 걸리는 시간 일 수 있습니다.

신속한 해결은 사전 계산과 저장 공간 간의 균형입니다 (임베디드 장치는 PC에 다른 선택을해야 할 수도 있음). 거기에 몇 가지 매우 흥미로운 알고리즘이 있습니다.

Answer 4

모하메드 : 원래 질문이 그 측면에서 꽤 편안해 보였으므로 좋았습니다. 그래프 이론에 익숙하지 않다면 지금 약간의 독서를하는 것이 좋습니다. Wikipedia을 사용해도 좋습니다.

일반적으로 GIS 데이터에서 도로는 메타 데이터가 첨부 된 폴리선으로 저장됩니다. 화면에 표시하는 것은 괜찮지 만 탐색 할 수 있으려면 어느 것이 서로 연결되어 있는지 알아야합니다. 따라서 메타 데이터에는 일반적으로 도로의 각 끝에 대한 노드 ID가 있으므로 "이것은 도로 구간 457, 노드 332에서 노드 667로 이동합니다"라고 말할 수 있습니다. 따라서 GIS 데이터를 읽을 때 호 (arcs)로 연결된 노드 세트 (즉, 그래프)로 그 표현을 만듭니다.

해당 메타 데이터를 사용할 수 없다면 어떤 도로에서 시작/끝 좌표가 동일한 지 추측 할 수 있습니다 (이는 그리 좋지 않은 GIS 데이터의 경우입니다). "지시 된"조금은 도로가 방향을 가지고 있다는 것을 다만 의미한다 - 그 중 몇몇은 어느 방향 으로든지 여행 될 수있다, 그러나 다른 사람은 단지 일방 통행이다.

다이 그래프를 통해 경로를 찾는 일반적인 알고리즘은 Dijkstra의 알고리즘입니다. 다양한 파생 상품이 실제로 사용됩니다. 기본적으로 그래프의 호를 따라 노드에서 노드로 이동해야하므로이를 지원하기 위해 적절한 데이터 구조가 필요합니다.

도움이 되길 ...

Answer 5

이전 응답은 모두 GIS 시스템을 참조했습니다.이것은 PND (Portable Navigation Devices)가 작동하는 방식이 아닙니다. 데스크톱/워크 스테이션 수준의 GIS 소프트웨어를 실행하기에는 너무 간단합니다.

대신 PUNs는 Simucal이 추정 한 정보를 저장합니다. 도로는 세그먼트로 나뉩니다. 이것은 모델을 훨씬 더 간단하게 유지합니다. 세그먼트 내에서 최대 속도와 같은 속성은 변경되지 않습니다.

도로 계획은 도로 세그먼트를 그래프의 가장자리로 사용합니다. 각 노드에 대해 들어오고 나가는 노드가 모두 저장됩니다. 계획은 수정 된 A * 알고리즘을 사용하여 수행됩니다. 가장자리 무게는 일반적으로 거리가 아니라 예상 이동 시간 (또는 TomTom 경우 실제, 측정 된 시간)입니다.

도로 네트워크는 일반적으로 고차원 적이지만 정상적인 A *는 저속 시동기입니다. 한 마을에서 다른 마을로 여행 할 때, A *는 출발 도시를 크롤링하는 데 과도한 시간을 할애합니다. 그러나 우리는 더 먼 거리를 여행 할 때 고속도로를 이용하는 것이 가장 좋습니다. 그것이 그들이 구축 한 것입니다. PND는 마찬가지로 고속도로를 선호합니다. 고속도로가 훨씬 희귀하기 때문에 많은 메모리를 절약 할 수 있습니다.

또 다른 최적화는 순방향 및 역방향 검색입니다. 당신은 중간 지점을 향해 양쪽에서 계획하고 있습니다. 이것의 가장 큰 장점은 잘못된 순서로 돌아 가면 새로운 시작점에서 다시 검색 할 수 있다는 것입니다. 목적지가 이동하지 않았으므로 역방향 검색 트리는 변경되지 않습니다.

Answer 6

라우팅 응용 프로그램 작동 방식에 대한 일부 코드를 살펴 보려면 openstreetmap.org wiki에서 연결된 일부 라우팅 응용 프로그램을 살펴보십시오. Navit과 Gosmore는 공개 소스이며 특히 설치하기가 쉽습니다.

Gosmore 응용 프로그램 개발자 Nic Roets은 interesting post을 작성하여 자신이 관심있어 할만한 도로 - 벡터 데이터를 나타내는 방법을 선택했습니다.

Gosmore를 실제로보고 싶다면 openstreetmap 데이터를 기반으로 한 yournavigation.org 라우팅 웹 사이트의 백엔드입니다.