연결된 볼록 다각형의 그래프 생성

Question

나는 this과 같은 점들의 조밀 한 그래프를 가져 와서 연결된 볼록 다각형의 그래프로 바꾸려고합니다. 연결 상태를 유지하면서 다각형은 최대한 크고 단순해야합니다. 결과 그래프가 길 찾기에 사용됩니다. 누구든지 올바른 방향으로 나를 가리킬 수 있습니까?

Answer 1

. loorker가되기가 어렵습니다. & 가끔 참여하는 사람.

다음 기술을 사용하여 마무리했습니다.

먼저 거리 변환을 만듭니다. 여기에 설명 된 [링크 할 수없는] 알고리즘을 사용하여 [링크 할 수 없음]과 같은 이미지가 생성되었습니다. 그런 다음 DT의 유역 변환을 만들어이를 영역으로 분할하십시오. 이 작업에는 약간의 작업이 필요하지만 현재는 이와 유사합니다. [연결할 수 없습니다] 그런 다음 각 영역 쌍을 연결하는 폴리 라인의 중간 점을 사용하여 웨이 포인트 그래프를 만듭니다.

Result

유역 분할은 밴딩을 일으키는 앨리어싱주의, 아직 완벽하지하지만 난 181 개 지역이 128 * 128 맵 281 개 중간 점으로 끝낼.

Answer 2

이 당신을 위해 무엇을 요구하지 않지만 여기 2D 경로 계획 문제를 해결하기위한 몇 가지 다른 아이디어입니다

• 사용 A *는. 이렇게하면 가장 짧은 충돌없는 경로가 생성됩니다. 비트 맵을 단순화하지 않아도 성능은 괜찮을 수 있습니다.

• sampling-based roadmap을 사용하십시오. 이것은 다각형보다 다른 이산 표현입니다. 검색 공간이 작기 때문에 전체 비트 맵을 탐색하여 모든 지점을 로드맵에 연결할 수 있는지 확인할 수 있습니다. 소형로드 로드맵이 중요하지만 짧은 경로는 중요하지 않은 경우 visibility roadmap 기술을 사용할 수 있습니다.

어쨌든 그래프 표현과 그래프 검색을 처리해야하기 때문에 이러한 기법은 다각형 추출보다 훨씬 쉬워 보입니다.

• Convert Bitmap to Polygon
• 공간이 다각형 (가능성이 도구를 사용)에 의해 매핑 된 How can i convert simple shape bitmap to vector

, 그것은 볼록 다각형 또는으로 나눌 수 있습니다 : 그 문제에 대한 몇 가지 SO 질문에 발굴 검색 할 수있는 다른 표현. 이것은 또한 라발에 의해 설명되어 있습니다 : 내가 링크를 게시 할 수 없습니다 매우 성가신

• Vertical (trapezoidal) Cell Decomposition
• Shortest-Path Roadmaps