2
격자 기반 엔진에 A * 길 찾기 알고리즘을 구현하고 있지만 격자 점을 사용하는 대신 다각형 영역에 노드를 만들고 싶습니다.대 면적을 볼록 다각형으로 분할하는 방법에 대한 알고리즘
이 지역에는 장애물이있어 이동해서는 안됩니다.
가능한 가장 작은 수의 볼록 다각형이있는 그래프에 장애물이있는 큰 영역을 나눌 수있는 알고리즘이 있는지 궁금합니다.
A
답변
1
많은 것들이 있습니다. 일반적으로 삼각 측량 알고리즘을 다루고 있습니다. 장애물을 통과하는 선을 제거하고 최단 경로 알고리즘을 수행합니다. 왜 가장 작은 수의 연결 볼록 다각형이 필요한지 잘 모르겠지만 똑같이 할 수 있습니다. 대답은 간단히 포인트의 볼록한 선체입니다. 하나의 다각형은 정의상 가장 작은 숫자입니다.
관련 문제
- 1. Cuda의 볼록 다각형 알고리즘?
- 2. 볼록 다각형, 그래픽 알고리즘
- 3. 배낭 알고리즘 및 볼록 선체
- 4. 그레이엄 스캔 알고리즘 볼록 선체의 알고리즘
- 5. 효율적으로 json을 분할하는 방법에 대한 지침을 찾으려고합니다.
- 6. 삼각형 스트립의 꼭지점을 다각형으로 변환하는 알고리즘
- 7. 볼록 다각형의 최대 및 최소 대각선에 대한 알고리즘?
- 8. 사각형 격자에서 영역의 면적을 계산하기위한 알고리즘
- 9. 이미지를 토큰으로 분할하는 알고리즘
- 10. 알고리즘/방법에 대한 간단한 대수 단순화
- 11. 점 집합으로부터 볼록 레이어를 생성하기위한 효율적인 알고리즘
- 12. 모양을 다각형으로 변환
- 13. 여러 다각형의 면적을 계산하는 방법은 무엇입니까?
- 14. 2D 사각형 그리드를 작은 그리드로 분할하는 알고리즘
- 15. 1 차원 공간을 분할하는 알고리즘
- 16. asp.net-mvc 한 뷰를 여러 뷰로 분할하는 방법에 대한 조언
- 17. TSQL - JOIN에서 OR 조건을 분할하는 방법에 대한 조언
- 18. 수백만 개의 다각형으로 수천 개의 점을 찾는 빠른 알고리즘?
- 19. 삼각 측량을 줄이기위한 알고리즘
- 20. .NET의 볼록 선체 생성
- 21. 알고리즘 대 OOP
- 22. 부드러운 볼록 선체
- 23. 재귀 대 반복 알고리즘
- 24. 날짜 대 요일 알고리즘?
- 25. 분류 방법에 대한 이상적인 커널/알고리즘 인수를 찾는 방법은 무엇입니까?
- 26. 정의 된 XML 형식을 기반으로 XML을 정의하는 방법에 대한 알고리즘
- 27. Jacobi 방법에 대한 두 가지 알고리즘 : 시간이 왜 바뀌 었습니까?
- 28. 삼각형 메쉬를 볼록 폴리곤으로 만들려면 어떻게해야합니까?
- 29. 가장 빠른 수평선 <-> 볼록 다각형 교차 알고리즘?
- 30. '로컬 볼록 헐 (convex convex hulls)'의 합집합을위한 빠른 알고리즘
각 다각형은 연결된 그래프의 꼭짓점이 될 것입니다.이 그래프를 탐색 할 때 사용합니다. 가장 작은 수의 정점을 사용하는 것이 최적화에 가장 적합 할 것이라고 생각했습니다. 삼각형으로 영역을 분할하면 노드 수가 가장 적어지지 않습니다. 중간 지점에 장애물이있을 수 있으므로 포인트의 볼록 선체는 작동하지 않습니다. –
노드 연결 수가 가장 적은 것이 도움이된다고 생각하지 않습니다. 그러나 대부분의 상황에서 당신은 그들을 모두 찾을 수있을 것입니다. 그런 다음에 물건이나 같은 것의 기준에 따라 멀리 떨어 뜨리십시오. – Tatarize