De tempos em tempos eu tenho que produzir um livro de mapas para mostrar pontos de interesse. Primeiro passo para criar páginas, usando malha regular:
Não gosto da solução porque: a) há algumas páginas com pontos únicos (por exemplo, página 25) na borda eb) muitas páginas.
É fácil corrigir o primeiro problema usando o código, - mova o retângulo da extensão da página para o centro da extensão dos pontos relevantes:
Ainda não gosto, parece muito lotado porque o número de páginas permanece o mesmo. Lembre-se, todos eles acabam sendo páginas em papel A3 reais em várias cópias do relatório!
Então, eu criei um código que reduz o número de páginas. Neste exemplo, de 45 a 34.
Não tenho certeza se esse é o melhor resultado que pode ser alcançado,
Qual é a melhor estratégia (pseudo-código, publicação, biblioteca Python) para embaralhar os pontos, a fim de minimizar o número de retângulos de determinado tamanho e capturar todos os pontos? Certamente, alguém o descobriu na teoria dos jogos, arte militar ou indústria pesqueira
Esta é a atualização para a pergunta original:
Isso mostra a extensão real e o tamanho da página necessários:
Zoom mais próximo mostrando 10 de 164 páginas:
Classe de recurso de ponto de amostra
O tamanho do retângulo pode mudar assim que permanecer dentro dos limites, ou seja, menor é bom.
Respostas:
Esta não é a resposta, eu apenas pensei em postar uma solução Python para quem se interessasse:
aplicou-o recentemente para o planejamento de pesquisas:
ATUALIZAR:
Parece que, para alguns padrões, lidar primeiro com pontos "perdidos" é o caminho a percorrer. Eu usei a casca 'casco convexo' para identificá-los, ideia de whuber, não consigo encontrar post, desculpe.
fonte
Parece uma versão geométrica do problema de cobertura máxima, que está intimamente relacionada ao problema de cobertura de conjunto , e esses dois são NP-Complete.
Então, para resolvê-lo, pode-se usar aproximação. Eu tentaria o seguinte algoritmo e parece funcionar perfeitamente. Embora, devido à complexidade do problema, não possamos encontrar a melhor resposta.
uma implementação desse algoritmo, apenas para circle, está aqui: http://jsfiddle.net/nwvao72r/3/
fonte