GPS가 인접한 도로를 찾음

Question

그래서 GPS 응용 프로그램을 구축 중입니다. 각 Road 객체에는 시작점과 끝점 (도로 곡선이있는 다른 중간 지점 포함)이 포함되어 있습니다. 저는 dijkstra의 알고리즘을 구현하여 최단 경로 (그래프에서 노드가있는 노드)를 찾았지만 실행할 수 있기 전에 에지를 생성하기 위해 어떤 이웃 노드 (연결)를 결정해야합니다.

쉬운 (?) 방법은 각 도로를 반복하고 중첩 된 루프에서 같은 지점에서 다른 도로가 시작/끝나는 지 확인합니다. 그러나 이것은 O (N^2)라는 비효율적 인 것으로 보인다. 한 가지 아이디어는 도로를 지역 (예 : 영국의 경우 NW, NE, E, SE, SW 등)으로 미리 구분 한 다음 동일한 지역의 이웃을 검색 공간을 줄이는 것입니다.

경험이 많은 프로그래머로부터 조언을 구하는 방법은 무엇입니까?

이것은 숙제가 아니며 최근에 졸업 한 경험이 있습니다. 실용적인 경험을 얻고 이력서를 약간 덧씌우기 위해 애 쓰고 있습니다.

편집 : 나는 Y에 의해 처음으로 다음 x로, 도로는 오직 당신은 당신이 가진 지적 모든 (x, y)를 정렬 할 수

Answer 1

시작/끝 지점에서 연결 추가해야합니다. n 점의 경우, 이것은 기수 정렬을 사용하는 경우 O (nlogn)이거나 심지어 선형이어야합니다. 그런 다음 목록을 검토하면됩니다. 두 개의 인접 항목이 같을 때마다 해당 도로가 교차합니다.