무작위로 겹치지 않는 사각형을 패널에 놓습니다

StackOverflow https://stackoverflow.com/questions/716558

  •  23-08-2019
  •  | 
  •  

문제

나는 Y의 크기 X 패널을 가지고 있습니다.이 패널에 무작위로 크기의 N 직사각형을 배치하고 싶지만 겹치는 것을 원하지 않습니다. 이 사각형의 x, y 위치를 알아야합니다.

알고리즘, 누구?

편집하다: 모든 n 직사각형은 처음에 알려져 있으며 어떤 순서로든 선택할 수 있습니다. 그것이 절차를 바꾸나요?

도움이 되었습니까?

해결책

0,0, 크기 (x, y)의 좌표가있는 단일로 시작하여 "무료"사각형 세트로 이것을 모델링 할 수 있습니다. 사각형을 하나 더 추가해야 할 때마다 나머지 "무료"사각형 중 하나를 선택하고 새 사각형 (왼쪽 좌표와 크기가 완전히 포함되어 있음)을 생성하고 그 사각형과 다른 겹치는 다른 겹치는 것을 분할하십시오. " 아이들이 남아있는 여유 공간을 표현하도록 무료 "사각형. 이로 인해 0 ~ 4 개의 새로운 사각형이 발생합니다 (새로운 사각형이 정확히 오래된 자유 사각형의 크기 인 경우 0; 중간에있는 경우 4). 시간이 지남에 따라 점점 더 작고 작은 자유 공간을 얻을 수 있으므로 생성 된 사각형도 더 작을 것입니다.

좋아, 매우 정교한 설명은 아니지만 화이트 보드에서 보여주는 것이 더 쉽습니다. 그러나이 모델은 새로 컷이있는 GUI 구성 요소의 시작 위치를 찾는 데 사용 된 모델입니다. 사용 가능한 화면 덩어리를 추적하고 그러한 영역을 가장 왼쪽 또는 상단으로 선택할 수 있습니다.

다른 팁

다음은 2D 포장 알고리즘에 대한 괜찮은 기사입니다. http://www.devx.com/dotnet/article/36005

일반적으로 휴리스틱을 사용하여 일종의 알고리즘을 원하면 괜찮은 결과를 얻을 수 있습니다. 간단한 (그러나 최적이 아닌) 솔루션은 첫 번째 적합 알고리즘입니다.

나는 이것을 사용했다 사각형 포장 알고리즘 내 응용 프로그램 중 하나에서 C# 소스 파일로 사용할 수 있습니다.

알고리즘은 패널의 크기로 초기화 된 다음 모든 직사각형을 반복하여 위치를 얻습니다. 사각형의 순서는 패커에 따라 결과에 영향을 줄 수 있습니다.

Staxmans 제안을 사용하는 것이 좋습니다.

여기 내 2C가 있습니다.

많은 직사각형을 무작위로 추가하십시오 (서로 겹치십시오). 겹치는 사각형 삭제 :

for rectangle in list of rectangles:
    if rectangle not deleted:
        delete all rectangles touching rectangle.

특정 사각형에 닿는 모든 사각형을 찾으려면 x1, y1 x2, y2 값을 기반으로 쿼드 트리 또는 불평등을 사용할 수 있습니다.

편집 : 실제로 Pygame 등과 같은 대부분의 게임 엔진에는 일반적인 문제인 사각형의 충돌 감지가 포함됩니다.

또는 이미 추가 된 사각형 목록을 유지하고 해당 목록을 기반으로 새 사각형을 어디에 배치 할 위치를 파악하는 알고리즘을 만듭니다. 기본 사각형 클래스를 만들어 직사각형에 대한 정보를 보유 할 수 있습니다.

사용자 정의 알고리즘을 만들기가 어렵지 않아야합니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top