Coloque rectângulos que não se sobrepõem ao acaso num painel

Question

Eu tenho um painel de tamanho X por Y. Eu quero colocar até retângulos N, dimensionados de forma aleatória, em cima deste painel, mas eu não quero qualquer um deles a se sobrepor. Eu preciso saber o X, Y posições para estes retângulos.

Algoritmo, alguém?

Editar : Todos os retângulos N são conhecidos no início e podem ser selecionados em qualquer ordem. Será que a mudança do procedimento?

Answer 1

Você pode modelar este por um conjunto de retângulos "livres", começando com um single com coordenadas de 0,0, tamanho (x, y). Cada vez que você precisa adicionar mais um retângulo, escolha uma das restantes rectângulos "livres", gerar novo retângulo (com superior esquerdo coordenada e um tamanho tal que ele será totalmente contido), e dividir esse retângulo, bem como qualquer outra sobreposição " livre" retângulo, de tal forma que as crianças expressam espaço livre restante. Isso resultará em 0 a 4 novos retângulos (0 se novo retângulo foi exatamente o tamanho de idade retângulo livre; 4 se é no meio e assim por diante). Com o tempo você vai ficar mais e mais áreas livres cada vez menores, de modo retângulos que você criar será menor também.

Ok, não é uma explicação muito elaborado, é mais fácil mostrar no whiteboard. Mas o modelo é que eu usei para encontrar local de partida para componentes gui recém cut'n coladas; é fácil manter o controle de pedaços disponíveis de tela, e escolha (por exemplo) para a esquerda ou superior dessas áreas.

Answer 2

Aqui está um artigo decente em algoritmos de embalagem 2d: http://www.devx.com/ dotnet / Article / 36005

Você geralmente querem algum tipo de algoritmo usando heurísticas para alcançar bons resultados. Um simples (mas não ideal) solução seria o primeiro algoritmo de ajuste.

Answer 3

Eu usei esse Retângulo algoritmo Packing em uma das minhas aplicações, disponível como arquivos # origem C.

O algoritmo é inicializado com o tamanho do painel, então você percorrer todos retângulos e obter a sua posição. A ordem dos retângulos podem influenciar o resultado, dependendo do packer.

Answer 4

Eu aconselharia você usa StaxMans sugestão.

Aqui está o meu 2c:

Adicionar um monte de retângulos aleatoriamente (sobrepostos uns aos outros). excluir retângulos sobrepostos:

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

para encontrar todos os retângulos tocando um retângulo particular, você pode usar uma árvore quad ou desigualdades com base em x1, x2 y1, valores Y2.

Edit: Na verdade, a maioria dos motores de jogo, como pygame etc incluem detecção de colisão de retângulos que é um problema comum

.

Answer 5

Ou manter uma lista de retângulos já adicionadas e criar um algoritmo que descobre onde colocar o novo retângulo com base nessa lista. Você pode criar uma classe básica do retângulo para conter as informações sobre seus retângulos.

não deve ser tão duro para criar um algoritmo personalizado.