두 폴리 라인 사이의 최소 면적을 가진 메쉬

Question

두 폴리 라인 v 및 u은 각각 n 및 m 개의 정점을 3D에 가지고 있습니다. v[0]을 u[0], v[n-1] to u[m-1]에 연결하고 내부 정점을 어떻게 든 최소 표면적으로 삼각형 메쉬 스트립을 얻고 싶습니다.

내 간단한 해결책은 가장 작은 대각선을 후속 추가하여 거의 최적의 초기 메쉬를 얻은 다음 더 이상 가능하지 않을 때까지 더 작은 영역을 생성하면 모든 사변형에서 대각선으로 전환하는 것입니다.

는하지만 난이 지역의 최소 및 글로벌 없습니다에서 끝낼 수 두렵다. 최소한의 메쉬를 달성하기위한 더 나은 옵션은 무엇입니까?

Answer 1

이것은 동적 프로그램으로 해결할 수 있습니다.

는 이제 열을 제 폴리 라인의 정점을 나타내고, 행 번째 다중 선의 정점을 나타내는 테이블로서 문제를 시각화하자

0 1 2 3 ... n-1 -> v 
0 
1 
2 
... 
m-1 

모든 세포는 폴리 라인 사이의 경계를 나타낸다. (0, 0)에서 시작하여 (+1, 0) 또는 (0, +1) 단계를 취하여 (n-1, m-1)의 경로를 찾고 싶습니다. 당신이 만드는 모든 단계는 비용 (결과 삼각형의 면적)을 가지며 최소한의 비용을 초래하는 경로를 찾고자합니다.

따라서 동적 계산 방식으로 반복적으로 모든 셀에 도달하는 데 필요한 비용을 계산할 수 있습니다 (가능한 두 가지 도착 방향의 결과 비용을 비교). 당신이 선택한 방향을 기억하고 결국 최소 비용의 완벽한 경로를 갖게됩니다. 전체 런타임은 O(n * m)입니다.

정점이 어느 정도 잘 분산되어 있다는 것을 알고 있다면 테이블 계산을 대각선 근처의 몇 가지 항목으로 제한 할 수 있습니다. 그러면 실행 시간이 O(k * max(n, m))으로 줄어들 수 있습니다. 여기에서 k은 대각선 주위의 가변 반경입니다. 그러나 좋은 버텍스 분포 가정이 성립되지 않으면 최적 해를 놓칠 수 있습니다.

또한 셀을 최소 경로에 속할 수 있다고 생각할 때만 (일부 추론을 사용하여) 셀을 계산하는 A *와 같은 전략을 사용할 수도 있습니다.