부스를 나타내는 많은 d3.js 폴리곤 객체가있는 평면도가 있습니다. 가장 좋은 방법은 다른 객체와 겹치지 않는 두 객체 사이의 경로를 찾는 것입니다. 여기서 유스 케이스는 우리가 부스를 가지고 있고 가장 효율적으로 포인트 a에서 b로 이동하는 방법을 사용자에게 보여주고 자하는 것입니다. 경로는 90도 또는 45도 회전 만 포함해야한다고 가정 할 수 있습니다.두 객체 간의 최단 경로를 찾는 알고리즘
우리는 Dijkstra를 사용하여 촬영했지만 그 크기는 우리에게서 멀어지고있는 것처럼 보입니다.
우리의 시스템의 예를 스냅 샷 :
우리의 제약이 브라우저에서 실행할 필요가 있습니다. d3.js와 잘 작동하면 좋을 것입니다.
레이아웃이 행렬 (또는 중첩 행렬)이기 때문에 이것이 다이 st 스트라 문제가 아니기 때문에 간단합니다. 문제의 기술적 이름은 "Manhatten routing"입니다. 코드 알고리즘을 제공하기보다는 다음 다이어그램에서 최적 경로 (파란색 선)의 예를 보여 드리겠습니다. 여기에서 알고리즘이 무엇인지 분명히해야합니다 : 
여기 미묘한 뉘앙스가 있습니다. 즉, 전체 모양이 매트릭스이기는하지만 각 모서리에서 사람은 실제로 대각선으로 걷습니다 (4 방향 교차로를 가로 질러 대각선으로 자르는 사람을 생각해보십시오). 따라서 단순히 북쪽으로 가고 서쪽은 잘못되었으므로 한 모서리 만 자르기 때문에 표시되는 경로에서 5 개의 모서리를 자릅니다.
굉장한 남자. 이것에 대해 정말 간단하게 보았습니다. 도움을 주셔서 감사합니다. – Quotient
이것은 잘못된 대답이며, 최적의 벙어리 방법을 얻을 수는 있지만 가장 좋은 방법은 아니며 직선 경로를 가질 필요가 없습니다. counter 예제는 그리기 쉽지만 설명하기 쉽지 않습니다 (적어도 하나의 카운터 예제를 상상할 수 있다고 생각합니다). 내 대답에서 언급 한이 문제는 매우 유명하며 당신이 쓴 것처럼 쉽지 않습니다. 어쨌든 Dijkstra를 사용하여 그래프를 그리는 데는 시간이 많이 걸리지 않습니다. –
이 문제는 다각형 장애물이있는 두 점 사이의 최단 경로를 찾는 것으로 알려져 있으며 문헌에서 많이 연구되었습니다. 한 예는 here을 참조하십시오. 이를위한 모든 알고리즘은 문제를 Dijkstra를 실행하는 그래프 이론 문제로 변환하는 것입니다. 이렇게하려면 :
이제 최단 경로 알고리즘을 실행할 준비가되었습니다. 어려운 부분은 삼각 측량이고, 나는 triangle 라이브러리가 요구 사항에 맞다고 생각합니다. 또한 쉬운 방법은 구현을 찾으려면 첫 번째 줄에서 말한 키워드로 웹을 검색하는 것입니다. 나는 미래의 독자들에게 유용한 알고리즘 방식으로 그것을 말하는 것이 더 낫다는 것을 알기 때문에 어떤 구현과도 링크하지 않았다.
Dijkstra가 정확히 여기 어떻게 작동하지 않았습니까? Dijkstra에게 어떤 문제가 생기는 것을 나는 알 수 없다. 만약 당신이 의미하는 바가 너무 느리다면, 비효율적 인 구현이 있어야합니다. Dijkstra는 수백 개의 노드가 포함 된 그래프에서도 훌륭한 성능을 제공합니다. –
사람들이 부스에서 등반 할 수 있습니까? –