Coloque retângulos evitando colisões (ajuda de algoritmo)

9

Eu tenho uma exibição de rolagem horizontal (grande) e um monte de retângulos que gostaria de posicionar nela. Cada retângulo tem uma posição horizontal desejada, mas pode variar de uma posição até uma certa quantidade (uma constante, K), se necessário. Os retângulos não devem se sobrepor. A posição vertical dos retângulos é arbitrária (limitada à altura da vista, é claro).

Idealmente, eu gostaria que o tamanho dos retângulos fosse variável ... Eu acho que, se isso não for possível, eu posso fazer o tamanho variar em apenas uma dimensão.

Agora, haverá impossibilidades neste layout: uma vez que há apenas uma certa quantidade de espaço vertical, e eles podem mover K pixels de seu ideal horizontalmente, provavelmente nem todos os retângulos poderão ser desenhados. Para lidar com isso, cada retângulo tem uma prioridade (P), e os de menor prioridade devem ser omitidos primeiro. (Você pode assumir que isso não é ambíguo, e que você sempre pode dizer qual dos dois retângulos tem a prioridade mais alta.)

Eu estou atrás do algoritmo conceitual, mas se você precisar de detalhes específicos, isso será executado em um iPad, e haverá alguns milhares (> 1000, mas < 10.000) retângulos a serem considerados. O ideal é que eu goste de algo rápido o suficiente para voltar a ser executado toda vez que o usuário alterar o nível de zoom, mas se isso não for fácil, então posso armazenar as posições em cache. Os objetos são fotos em uma linha do tempo, e eu quero aproximá-los aproximadamente quando o evento aconteceu - eu estou indo para aproximar para obter mais deles lá.

Eu já vi algoritmos como este , que faz o truque sem interseção, mas não tem a mesma ideia de que cada item só pode ser movido até certo valor. Obviamente, sem a última restrição, você pode exibir todos os itens, então também vou precisar de algum modo de saber em que ponto não mais retângulos podem ser exibidos.

Se resolver o problema como descrito é muito difícil, eu gostaria de receber uma sugestão de uma ideia mais pragmática. Se tudo mais falhar, sempre poderei fazer algo em ordem de prioridade, renderizar cada item no lugar desejado, se possível, se não, então, tentar deslocá-lo verticalmente, se ainda não for, movê-lo horizontalmente até o limite permitido, antes de passar para o próximo. A ordem de prioridade significaria que provavelmente seria encontrada uma solução sub-ótima, mas seria ponderada em relação aos itens mais importantes.

    
por Amy Worrall 30.08.2011 в 13:52
fonte

1 resposta

5

Esta é uma maneira que eu acho que isso poderia ser feito.

O passo 1 é descobrir todos os locais onde o novo retângulo amarelo pode ser colocado. Sem perda de generalidade, podemos armazenar isso como uma lista de todas as possíveis posições X-Y do canto superior esquerdo do retângulo. Naturalmente, para uma área inicial tão grande, essa lista conterá milhões de entradas, portanto, para economizar espaço, vamos armazenar essa lista na forma de um conjunto de áreas retangulares.

Por exemplo, se a tela tiver pixels de X = 0 a X = 2999 inclusive, e de Y = 0 a Y = 999 inclusive, e nosso novo retângulo tiver largura de 300 pixels e altura de 150 pixels, o canto superior esquerdo de nosso novo retângulo pode aparecer em qualquer posição de (X, Y) = (0, 0) a (2699, 849) inclusive. Vamos armazenar isso como um quadrigêmeo, [0, 0, 2699, 849].

Agora, quando colocamos cada retângulo (vermelho) existente na tela, algumas dessas possibilidades são descartadas, uma vez que resultariam no novo retângulo (amarelo) sobreposto a elas. Por exemplo, se houver um retângulo vermelho [1100, 200, 1199, 299], nosso retângulo amarelo não poderá ter seu canto superior esquerdo em qualquer posição de (X, Y) = (801, 51) a (1199, 299) inclusive.

Portanto, substitua [0, 0, 2699, 849] por quatro zonas retangulares que cobrem a mesma área, mas deixam a lacuna. Há muitas maneiras de fazer isso, mas aqui está uma: [0, 0, 1199, 50], [1200, 0, 299, 2699], [0, 51, 800, 849], [801, 300, 2699, 849 ].

Continue adicionando mais retângulos vermelhos à tela. Cada vez que um é adicionado, subtraia mais possibilidades da lista (isso geralmente resultará na lista contendo mais "zonas seguras" menores). (Isso pode consumir muito tempo para sua tela cheia com mais de 1000 retângulos; se, ao invés disso, você começar com apenas o espaço [XK, 0, X + K, H] que você mencionou, então relativamente poucos dos 1000 + irá se sobrepor e o cálculo será muito mais rápido.) Este código deve ser escrito com muito cuidado e uma pilha de testes unitários, porque os erros do fencepost serão abundantes.

O resultado final é uma lista completa de possíveis locais na tela onde o canto superior esquerdo do seu novo retângulo amarelo pode ser colocado, expresso na forma de uma lista de zonas retangulares.

Passo 2: olhe através desta lista e selecione o local mais desejável. Qualquer zona retangular que realmente cruze sua linha vertical ideal terá prioridade. Mas é possível que não haja nenhum. Neste caso, cabe a você escolher a opção mais preferível das zonas que caem à esquerda e das zonas que ficam à direita da linha ideal. Como uma dica: apenas um canto de cada zona precisa ser considerado em cada caso (o canto superior esquerdo das zonas à direita, o canto superior direito das zonas à esquerda).

    
por qntm 30.08.2011 / 17:24
fonte