중복을 최소화하면서 더 큰 사각형 내에 다른 크기의 사각형을 배포하는 데 도움이되는 알고리즘을 찾고 있습니다.다른 사각형 내에서 균일하게 사각형을 분포시키는 데 필요한 알고리즘
빈 포장 알고리즘을 살펴 봤지만 사각형 사이의 공간을 최소화하는 것처럼 보입니다. (제 경우에는 포장되는 모든 항목이 사각형이됩니다).
나는 모든 사각형과 외부 사각형의 경계 사이의 거리를 최대화하고 싶습니다.
이것은 Knapsack Problem의 일반화 될 것으로 보인다 : 여기
는 내가 뭘하려고 오전의 예입니다.동적 프로그래밍은 다항식 시간 가까이에서이를 해결합니다.
게시하기 전에 배낭 문제를 살펴 봤는데 문제 해결과 관련된 알고리즘 중 일부는 효과가 있다고 생각합니다. 외부 직사각형 내에서 사각형을 고르게 분배하는 주요 요구 사항에 대해 최적화 할 변수가 무엇인지 알지 못합니다 (내 문제를 설명하는 데있어 제 용어에 대해 사과드립니다). – howardr
the one described here과 같은 알고리즘을 사용하여 최대한 긴밀하게 포장 한 다음 대상을 둘러싸는 직사각형과 일치하도록 균등하게 확장하면 어떻습니까?
예를 들어 위의 3 개의 직사각형을 3x2 상자에 포장하고 외장 상자를 7x5이라고 할 수 있습니다. 그런 다음 상자 중심에서 각 사각형의 가운데까지 벡터를 가져 와서 x 구성 요소에 (7/3)을 곱하고 y 구성 요소에 (5/2을 곱하면 새 가운데에 제공됩니다.
"겹침 최소화"는 겹칠 수 있음을 의미합니까? – Nanne
사각형과 외곽 사각형의 경계 사이의 최소 거리 *를 최대화하고 싶습니다. – vitaut
@ Nanne 일부 겹치는 부분이 있으면 크게 걱정하지 않습니다. 나는 작동하지만 가변 크기의 사각형을 처리 할 수없는 알고리즘이 있다고 가정했다. 어떤 경우에는 평균 또는 평균 크기를 최적화 할 것입니다. – howardr