Tenho uma visão (grande) de rolagem horizontal e vários retângulos que gostaria de posicionar nela. Cada retângulo tem uma posição horizontal desejada, mas pode variar dessa posição em 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 (restrita à altura da vista, é claro).

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

Agora, haverá impossibilidades nesse layout: como existe apenas uma certa quantidade de espaço vertical e eles podem apenas afastar K pixels do 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 maior prioridade.)

Estou procurando coisas conceituais sobre algoritmos, mas se você precisar de detalhes, isso será executado em um iPad e haverá alguns milhares (> 1000, mas <10.000) retângulos a serem considerados. Idealmente, eu gostaria de algo rápido o suficiente para executar novamente toda vez que o usuário alterar o nível de zoom, mas se isso não for fácil, posso armazenar em cache as posições. Os objetos são fotos em uma linha do tempo, e eu quero aproximá-los quando o evento aconteceu - vou aproximar para obter mais fotos por l

Vi algoritmos comoest, que fazem o truque sem interseção, mas não têm a mesma idéia de que cada item só pode ser movido até um determinado valor. Obviamente, sem a última restrição, você pode exibir todos os itens; portanto, também precisarei de uma maneira de saber em que ponto não serão exibidos mais retângulo

Se a solução do problema descrito for muito difícil, gostaria de sugerir uma idéia mais pragmática. Se tudo mais falhar, eu sempre poderia fazer algo pelo qual ele passa por ordem de prioridade, renderizar cada item no local desejado, se puder; se não, tentar mudá-lo verticalmente, se ainda não o fizer, mude-o horizontalmente até o limite permitido, antes de passar para a próxima. A ordem de prioridade significaria que provavelmente seria encontrada uma solução subótima, mas seria ponderada nos itens mais importantes.