알고리즘 내가 레이아웃 사각형 창문 알고리즘을 추구하고있어 2D 디스플레이

Question

에 사각형 창을 배치하기 위해서, 요구 사항은 다음과 같다 :

1. 모든 창은 레이아웃이 작은 사각형을 볼 수 있습니다로.
2. 모든 창은 직사각형 2D 디스플레이의 레이아웃이어야하며 디스플레이 너비와 높이가 지정되어야합니다.
3. 레이아웃 할 수십 개의 창이 있습니다. 각 창은 초기 위치 (x, y)와 크기 (너비, 높이)가 있습니다.
4. 레이아웃 알고리즘은 창을 겹치지 않으므로 모든 창을 볼 수 있습니다.

abs(new_x - x) <= max_x_offset and abs(new_y - y) <= max_y_offset 

5. 글로벌 제약 하드 제약이 의미 : 각 윈도우 (new_x, new_y)의 재배치 새로운 위치가 제약 조건을 만족하도록

6. 글로벌 제약 (max_x_offset, max_y_offset)가 주어진다 이 있다면 그러한 레이아웃은 4 과 5를 모두 만족시킬 수 없습니다. st는 글로벌 제약 조건을 만족시키고 일부 창 이 겹치도록합니다.

7. 알고리즘이 최상의 결과를 얻을 수는 없지만 가능한 결과가 있지만 을 실행해야합니다. 우리는 응용 프로그램

내가 구글과 위키 피 디아 일부 연구 논문을 검색 렌더링 실시간으로이 알고리즘을 사용하려고하지만, 여전히이 작업에 적합한 알고리즘을 찾는데 실패하고 있습니다. 어떤 제안? 감사!

업데이트 : 예 2-D 배낭 문제이며 NP 하드입니다. 내가 원했던 것은 좋은 결과를 얻기위한 빠른 알고리즘입니다.

Answer 1

창과 물체 사이의 거리에 따라 힘을가하면서 창을 서로 물리 칠 수있는 물리학적인 모델을 만들 수 있습니다. 각 시간 단계에서 절대 위치 제약 조건을 시행하십시오. 일정 시간 단계 내에서 중첩없는 솔루션을 찾지 못하면 알고리즘을 중단하고 현재 찾은 후보 솔루션을 제공하십시오.

물론 이것은 해결책이있는 경우 항상 해결책을 찾지는 못합니다. 그러나 나는 일반적으로 그것을 효율적으로하는 것은 매우 어렵거나 심지어 불가능하다고 생각합니다.