나는 당신이 올바른 길을 가고 있다고 말하지만, 최적의 및 / 또는 효율적인 알고리즘을 생각해내는 것이 또 다른 문제입니다. 어려운 문제입니다. 그러나 귀하의 관심이 학업이 아니라면 충분한 해결책이 충분할 수 있습니다.

먼저, 자신의 솔루션을 제안 하지 않으려면 CGAL 에 이미 볼록 다면체 분해 알고리즘이 포함되어 있습니다. http://doc.cgal.org/latest/Convex_decomposition_3/index.html

이제 방법에 대해; 3D의 많은 문제와 마찬가지로 이해하기 쉬운 2D 문제를 고려하는 것이 종종 도움이됩니다. 2D의 경우 작업은 반사 정점을 식별하고 해당 반사 정점에서 새 모서리 (및 가능한 정점)를 생성하고 반사 정점이없는 상태 (따라서 모든 볼록 다각형)가 될 때까지 계속하여 다각형을 2 개로 분할하는 것입니다. ).

J. Mark Keil의 다각형 분해 에는 다음 알고리즘이 포함되어 있습니다 (최적화되지 않은 형태).

diags = decomp(poly)
    min, tmp : EdgeList
    ndiags : Integer
    for each reflex vertex i
        for every other vertex j
            if i can see j
                left = the polygon given by vertices i to j
                right = the polygon given by vertices j to i
                tmp = decomp(left) + decomp(right)
                if(tmp.size < ndiags)
                    min = tmp
                    ndiags = tmp.size
                    min += the diagonal i to j
    return min

기본적으로 가능한 모든 파티션을 철저하게 비교하고 생성 된 대각선이 가장 적은 파티션을 반환합니다. 이런 의미에서 그것은 다소 무차별 적이며 최적입니다.

“더욱보기 좋게”분해, 즉 길쭉한 형태가 아닌보다 작은 형태를 생성하는 분해를 원한다면, Mark Bayazit에 의해 생성 된 것을 고려할 수 있습니다 . 기본적으로 반사 정점을 반대 정점, 일반적으로 다른 반사 정점에 연결하여 작동합니다.

단점 중 하나는 Steiner 점 (기존 가장자리에 존재하지 않는 점)을 만들어서 “더 나은”분해를 무시한다는 것입니다 .

3D의 문제는 비슷할 수 있습니다. 반사 정점 대신 “노치 모서리”를 식별합니다. 순진한 구현은 노치 가장자리를 식별하고 모든 다면체가 볼록해질 때까지 다면체에서 반복적으로 평면 절단을 수행하는 것입니다. 확인 버나드 채즐에 의해 “최악의 경우 최적의 알고리즘의 하한과 볼록 다면체 파티션을” 자세한 내용은.

이 접근 방식은 최악의 경우 다면체 수의 지수를 생성 할 수 있습니다. 이것은 다음과 같은 경우를 퇴화시킬 수 있기 때문입니다.

그러나 사소하지 않은 메쉬 (비정형 표면을 생각하면)는 어쨌든 결과가 좋지 않습니다. 복잡한 메시에 이것을 사용해야하는 경우 사전에 많은 단순화를 원할 가능성이 큽니다.

답변