가변 크기의 평면에 다양한 크기의 사각형을 무작위로 배포합니다 (밀도를 고려하여)

Question

컨테이너 내부에 임의의 사각형 (폭과 높이로 정의 됨)을 무작위로 배포하는 알고리즘을 찾고 있습니다. 구형. 나중에는 크기에 의해 정의되는 것이 아니라 가로 세로 비율에 의해 정의됩니다. 결과의 밀도를 결정하는 또 다른 변수가 있어야합니다. 즉, 두 개의 직사각형의 평균 거리. 컨테이너의 크기가 제한되어 있지 않기 때문에 가능한 모든 사각형을 배치해야합니다. 그리고 어떤 직사각형도 겹치지 않아야합니다.

최종 결과는 각 사각형의 결정된 위치와 사용 된 평면 자체의 크기 여야합니다.

불행히도, 지금까지이 알고리즘이나 그 일부를 수행하는 알고리즘을 찾을 수 없었습니다. 나는 어떤 제안, 코멘트 또는 참고 사항을 주시면 감사하겠습니다! 주된 문제는 "여유 공간"의 목록을 추적하는 것이고 각 공간 배치 후에 그에 따라 업데이트된다는 것이 밝혀졌습니다.

내가 필요한 경우, 주어진 사각형은 완전히 랜덤하게 형성되지 않습니다. 그것들은 거의 같은 높이를 가지고 있으며, 높이보다 훨씬 더 넓어지는 경향이 있습니다. 이것은 비행기를 통해 "구름"으로 배포되어야하는 텍스트에서 나온 단어입니다.

Answer 1

여기 알고리즘을 설계하는 방법에 대한 몇 가지 생각입니다 : 행에 당신이 할 수있는 아마 그룹을,

• 실제 사각형 비슷한 크기를 가지고 있기 때문에하고 최종 레이아웃
• 사용을 얻기 위해 여러 행을 스택 사실 rowCount * colCount == totalCount 및 colCount/rowCount == aspectRatio은 각 행과 열의 사각형 수를 대략적으로 나타냅니다.
• 사각형을 배치 한 후에 남은 여유 공간을 결정하려면 모든 사각형의 경계 상자 영역을 계산하고 개별 사각형 영역의 합계를 뺍니다 . 직사각형이 겹치지 않기 때문에이 방법이 효과적입니다.
• 아마도 totalFreeSpace에서 boundingBoxArea의 비율은 원하는 밀도를 제공합니다. 그렇지 않다면 O(n^2) 알고리즘은 문제 설명 당 밀도를 계산하는 데 도움이됩니다 (총 사각형 수가 너무 크지 않다고 가정).
• 위 작업을 완료하면 문제를 수정하여 구름 모양을 개선 할 수 있습니다. 예를 들어, 각 행을 정렬하여 가운데에서 가장 큰 직사각형을 갖습니다.

Answer 2

저는 그래프 기반의 시각화와 같이 강제 기반 레이아웃을 찾고 있다고 생각합니다. 단어 사이에 관계를 모델링 할 수 있다면 힘이 필요한 매개 변수입니다.