컨테이너 박스에 최대로 배관 스풀 적재하기

앞선 글에 이어지는 글입니다.
컨테이너 박스에 최대로 들어갈 수 있는 스풀을 제작했다면 이제는 스풀들을 최대로 많이 컨테이너 박스에 쌓는 문제입니다.
문제를 풀기에 앞서 스풀은 아래와 같이 생겼습니다.

사람이 직접한다면 경험으로 잘 싣을 수 있겠지만 컴퓨를 이용해 문제를 푸는 입장에서는 복잡합니다.

넣을 공간을 찾는 것도 문제지만 넣는 순간도 중요합니다.

안쪽에 빈 공간이 있다고 해도 미리 쌓은 스풀이 장애물이 된다면 안쪽에 넣을 수가 없습니다.

이러한 문제를 좀더 간단히 하기 위해 스풀 패키지 단위로 컨테이너에 적재하는 것으로 문제를 축소하겠습니다.

그럼 하나의 패키지에 최대한 많은 스풀을 배치(X,Y)하면 됩니다.
패키지에는 층으로 스풀을 쌓지 않습니다.
컨테이너 밖에서 패키지에 최대한 스풀을 많이 배치하고 패키지를 컨테이너 박스에 쌓으면 됩니다.(패키지의 폭과 깊이는 컨테이너와 동일)

이제 패키지에 최대로 스풀을 많이 쌓는 방법에 대해서 고민하면 됩니다.
이러한 유사한 문제를 푸는 NESTING 알고리즘이라는게 있습니다. 정확히는 2D NESTING

NESTING 알고리즘은 쉽게 말해 주어진 영역에 다각형을 최대한 많이 넣을 수 있도록 배치하는 알고리즘입니다.
스풀은 3D이므로 NESTING 알고리즘을 이용하기 위해 스풀을 2D(다각형)로 변환시킵니다.

이제 NESTING 알고리즘을 이용하여 2D 다각형을 최대한 많이 배치하도록 합니다.

거~의 끝났습니다.(아직 끝난게 아닙다.)
2D NESTING을 이용하여 배치했기 때문에 높이(Z) 방향으로 빈 공간이 생길 수 있습니다.
높이 방향으로 존재하는 빈 공간을 찾기 위해 Cell Decomposition을 이용하도록 하겠습니다.

패키지를 Cell로 구축합니다.

Cell에서 스풀이 차지하는 공간을 제거합니다.

스풀이 차지하는 공간 제거

남은 Cell들이 빈 공간이므로 스풀의 Bounding Box를 이용하여 스풀이 들어갈 수 있는지 확인하여 빈 공간에 스풀을 채워 넣습니다.(???) -> 좀더 세밀한 생각이 필요합니다.