격자를 임의의 크기의 사각형으로 분할

Question

나는 100px 격자가있는 500 x 400px 사각형을 가지고 있습니다. 이제 그 사각형에 채울 작은 무작위 크기의 정사각형으로 그 정사각형을 채우고 싶습니다. 즉, 작은 사각형은 100, 200, 300 또는 400 픽셀 크기 일 수 있습니다. 크기와 위치는 임의적이어야하므로 출력은 실행될 때마다 달라 보일 것입니다.

이 이미지는 큰 사각형, 격자 및 내가 생성하려고하는 작은 사각형으로 가능한 출력을 보여줍니다.

나는 DIV의와 루비 /시나이 발생하고있어,하지만 문제는 실제 알고리즘을 사용하는쪽으로 더 일반적인 것 같다.

최소한의 코드로이를 수행하는 방법에 대한 제안 사항이 있으십니까?

Answer 1

이 방법은 많은 코드의를 취할 것입니다,하지만 난 사각형의 모든 가능한 조치를 찾을 도널드 크 누스의 춤 링크 알고리즘 (DLX) (또는 다른 알고리즘)을 사용하고 무엇을 할 것이라고 생각합니다. 당신은 미리 준비를 계산할 수 있으며, 필요할 때 신속하게/임의로 선택할 수 있습니다.

는 여기에서 알고리즘 (문제와 매우 유사하다) pentominoes에의 응용에 대한 자신의 논문을 읽을 수 있습니다

http://www-cs-faculty.stanford.edu/~uno/papers/dancing-color.ps.gz 사각형을 감안할 때

http://en.wikipedia.org/wiki/Dancing_Links

Answer 2

당신이 취할 수있는 간단한 재귀 적 접근은 상당히 좋은 무작위 배분을 생성합니다 : 기본 경우로서, 100x100 인 격자는 100x100 사각형으로 채워 져야합니다. 그렇지 않으면 격자가 사각형을 담을만큼 작은 일부 n에 대해 n x n 인 경우 그 크기의 사각형으로 타일을 지정할 수 있습니다. 그렇지 않으면 크기가 100이 아닌 직사각형의 한면을 선택하고 100의 배수 인 임의의 위치를 ​​선택한 다음 반으로 나누고 재귀 적으로 두 반쪽을 모두 타일링합니다.

이 접근법의 가장 큰 장점은 이전 구형을 배치 한 위치를 추적하지 않아도된다는 것입니다. 항상 빈 사각형을 사용하고 영역이 겹치지 않도록 반복적으로 문제를 세분화합니다.

이것은 항상 좋은 결과를 줄 수는 없지만 코드 작성이 매우 쉽습니다 (코드 총 수는 15-25 라인이라고 가정 할 수 있음). 출력을 변경하기 위해 쉽게 조정할 수 있습니다.

희망이 도움이됩니다.