쇼핑몰이나 공항과 같은 실내 장소에서 기본적으로 Google지도 인 애플리케이션을 만들고 싶습니다. 나는 floorplan에서 그래프를 만들고 최단 경로 찾기 알고리즘을 사용하여 한 위치에서 다른 위치로 최단 경로를 그려야한다는 것을 알고 있습니다. 쇼핑몰이나 공항을 그래프로 나타내려면 어떻게해야합니까? 각 상점이나 게이트 또는 무언가를 노드로, 산책로를 가장자리로 만드나요? 아니면 5 ~ 10 피트마다 노드를 만드는 등 훨씬 더 구체적이어야합니까? 노드와 에지를 어떻게 구체적으로 만들어야합니까?iPhone지도 응용 프로그램의 경우 어떻게 그래프를 만들 수 있습니까?
각 평면이 x 평방 미터를 나타내는 격자로 인식하는 것이 좋습니다. 액세스 가능 영역 내에있는 각 셀에 노드를 배치하십시오. 가장자리는 각 neigbouring 셀 사이에 있으며 모두 x의 비용이 있습니다.
이 접근법의 장점은 효과적으로 이것을 메모리에 배치 할 수 있다는 것입니다 (이를 adiecency 목록 등을 사용하지 않아도 매트릭스에 넣을 수 있습니다). 길 찾기의 경우 두 점 사이의 유클리드 거리를 경험적 방식으로 사용하는 간단한 A * 구현을 사용할 수 있습니다.
여기서 해결할 몇 가지 문제가 있습니다. 첫째, 두 장소 사이에는 구조적 관계가 있으며, 두 번째에는 기하학적 관계가 있습니다. 최단 경로는 부분적으로 기하학에 의존하고 부분적으로 구조에 의존합니다. 예 : 통로가 직선 일 필요는 없습니다. 구조의 경우 쇼핑몰 상점과 게이트를 노드로 표현하고 통로는 가장자리로 표현할 수 있습니다. 노드 사이의 실제 거리를 모서리의 "무게"로두고 가장 짧은 경로를 찾으려면 Dijstra's algorihtm을 사용하십시오.
"A로 이동 한 다음 B로 이동"또는 지하철 (지중) 스타일 위상 맵에서 결과를 텍스트로 표시하기 만하면됩니다. 그러나 바닥을 기하학적으로 정확하게 표현하기 위해 결과를 표시하려면 구조와 지오메트리 사이의 연결을 더 강하게 만들어야합니다. 위에서 설명한 구조는 노드가 경로를 따라가는 모든 추가 노드와 x, y 좌표가있는 노드뿐만 아니라 중간 노드인지 아닌지를 나타내는 bool로 표시하는 것이 좋습니다. 소스 및 대상으로 true 노드 만 선택 가능하지만 Dijkstra에는 전체 그래프를 사용하십시오. 결과를 화면에 그리는 경우 최단 경로의 노드를 반복하고 좌표를 사용하여 소스에서 대상까지 구분 된 직선을 그립니다.
"A로 가셔서 x 미터를 계속하고, 좌회전하고 y 미터를 B로 진행"과 같은 텍스트 결과에서 이러한 증강 노드를 사용할 수도 있습니다. –
지도를 어떻게 표시합니까? PDF, SVG, 이미지 또는 직접 프로그래밍 방식으로 그릴 수 있습니까? 그리고 그래프를 어떻게 적용하여 맵에 꼭지점과 가장자리를 결정합니까? – Aft3rmath