Preenchimento de espaço entre linhas 2D aleatórias

23

Considere uma região (2D) preenchida com linhas aleatoriamente (figura a seguir). Estamos interessados ​​em preencher os espaços vazios entre as linhas, incluindo quatro arestas de contorno de uma maneira:

0- maximizar o tamanho das parcelas;
1- a forma das parcelas de enchimento é alinhada quadrada horizontal ou verticalmente;
2- a forma das parcelas de enchimento é quadrada, ou seja, alinhamento relaxado ;
3- forma de encomendas de enchimento é qualquer quadrângulo. nossa pergunta original

Então, por enquanto, existem três cenários diferentes.
Observe que as linhas são do [x1,y1,x2,y2]conjunto de pontos do formulário , números reais.

[* * *] Ideias de possíveis soluções / algoritmos / trechos de código / etc são bem-vindas.

insira a descrição da imagem aqui


Atualização 1: Poderíamos gerenciar uma solução para o primeiro caso: As
insira a descrição da imagem aqui
etapas são:
1 - linhas
2 - rasterizar linhas em um bitmap
3 - pesquisar nas células próximas por cada célula da cor desejada (ou seja, a mesma cor) com uma função objetiva para maximizar a área, ou seja, o número de células.

Funciona bem, mas abrange apenas o primeiro cenário e também é lento.


Atualização 2:
Assumimos que o leitor esteja familiarizado com o conceito de preenchimento de espaço em mosaico. Você pode seguir o link para obter inspiração. No entanto, observe que nosso problema é diferente. Como não preenchemos o espaço vazio aleatoriamente e não escolhemos o tamanho aleatoriamente. A solução deve ser iterativa. Para todos os casos, não há limite para o número de parcelas sendo montadas. De fato, cabe ao usuário limitar o número da iteração, escolhendo uma área mínima para parcelas, por exemplo. Isso é óbvio no exemplo dado acima, no qual discretizamos as linhas em pixels com tamanho especificado. Ou seja, o procedimento deve ser executado até que toda a área vazia seja preenchida, respeitando o critério, por exemplo, a área máxima de parcelas.


Atualização 3:
resumo:
Uma aplicação é descobrir a distribuição de blocos de 'rocha' intactáveis ​​extraíveis em uma 'mina' fortemente fraturada. Isso pode ser muito útil para muitos aspectos, incluindo projeto de perfuração, avaliação financeira etc.
descrição:
Para uma mina de rocha decorativa (pedra), os produtos que são blocos de rochas intactas cortam como cubos retangulares, o preço depende intimamente do tamanho da rocha. quadra. A extração de um bloco de uma área adequada, ou seja, sem fraturas graves, será desejada se a quantidade de peças restantes for a menor possível. Geralmente, os pequenos pedaços de rochas não têm valor econômico relativamente e são considerados resíduos.
A pergunta neste post investiga soluções para esse tipo de problema.

Uma visão matemática do problema pode ser definida da seguinte forma:
2D: encontre todos os retângulos que podem ser extraídos de uma determinada região 2D com algumas linhas otimizadas para um tamanho maior de retângulo possível.
3D: encontre todos os cubos retangulares que podem ser extraídos de uma determinada região 3D com alguns subplanos (melhor: polígonos) otimizados para o maior tamanho de bloco possível.


Como isso faz parte de uma pesquisa em andamento, algumas das perguntas feitas nos comentários abaixo não têm certas respostas que podemos fornecer. Acreditamos que as informações fornecidas aqui até agora são realmente suficientes para obter uma visão geral do problema. No entanto, fornecemos alguns detalhes para benefícios da comunidade.
Você pode colocar algumas restrições na solução da pergunta final, embora acreditemos que seja sempre possível adicionar mais tarde. Por exemplo, siga estes itens: {2D case}
O melhor tamanho de um bloco (retângulo economicamente ideal) a ser extraído nas condições mencionadas acima é 1x1 mfornecido 10x10 mpara a região no exemplo. Essa é uma restrição definida com base no valor econômico. O tamanho mínimo praticável para cortar etc, seja0.15x0.15 m; então esse é o segundo limite de tamanho.
insira a descrição da imagem aqui
A figura acima mostra a função de valor econômico, dependendo do tamanho do bloco. Portanto, neste caso em particular, cada pedaço de pedra menor que 0.15x0.15 mé apenas desperdício. Não haverá tamanho de bloco maior do que 1.7x1.7 mdevido aos limites de operação.

Desenvolvedor
fonte
3
@RK - eu discordo. Ele já declarou o que estava procurando com muita clareza. Claro que existem várias soluções possíveis, mas não há nada para impedir que todas sejam úteis e votadas.
GIS-Jonathan
1
Como esta é uma pergunta de algoritmo que pode ser bastante complicada em
GIS-Jonathan
1
Intimamente relacionado: gis.stackexchange.com/questions/27303 . A presente pergunta, como observa o @RK, não tem resposta definitiva porque não é suficientemente bem colocada. Quantos retângulos são permitidos? O que significa "maximizar tamanho"? Note também que este não é um problema de "colocação aleatória": as linhas meramente determinam, através de seu complemento, as áreas que podem ser ocupadas; as soluções definitivamente não serão aleatórias. Observe também que uma simplificação fácil está imediatamente disponível: o problema pode ser resolvido separadamente em cada componente do complemento.
whuber
1
@whuber: Bem, uma aplicação em que estamos interessados ​​é descobrir a distribuição de blocos de 'rocha' extraíveis intactos em uma 'mina' fortemente fraturada. Bem, o SIG parece promissor para esse problema, pensamos. Também adicionamos isso à pergunta. Nós achamos que a comunidade GIS pode se beneficiar da ideia por outros problemas específicos relacionados. Enfim, depende de você se você migrá-lo;)
Desenvolvedor
4
Como o @whuber sugere, essa não é realmente uma pergunta de GIS (embora não me ofenda que ela seja feita aqui.) Você terá muito mais sorte em obter uma resposta em um fórum de geometria ou otimização computacional.
Llaves

Respostas:

2

Eu tenho uma ideia de como você trabalha iterativamente de blocos grandes para blocos menores usando o FME (da Safe Software). Para o registro, eu não trabalho para eles, mas pareço elogiar sua ferramenta o suficiente ...

  1. Use "BoundingBoxReplacer" na área de interesse.
  2. Reprojete-o em um sistema de coordenadas local (para mais tarde, quando você precisar "ladrilhar" em pés / metros).
  3. Faça o buffer das linhas com o transformador "Bufferer". Você só precisa de um tamanho arbitrário, por exemplo, 0,01 ft / metros. O que estamos procurando aqui é um polígono da linha para o próximo passo.
  4. Adicione um transformador "Ladrilhador". Especifique um tamanho de telha grande (estimado ou não) em pés ou metros. O que estamos fazendo aqui é agrupar a área de interesse em blocos quadrados. Dependendo do conjunto de dados, comece grande para realmente obter os valores discrepantes maiores.
  5. Adicione um transformador "Clipper". O que estamos fazendo aqui é essencialmente dividir o conjunto de dados para ver quais blocos são bons / ruins. Na saída, os blocos "Internos" são muito grandes. No entanto, os ladrilhos "Externos" são grandes o suficiente e estão prontos para o corte ...
  6. Aqui é onde fica complexo, mas não difícil ... Vamos fazer o loop do transformador para reutilizar a BoundingBox original, mas recortar áreas que já estão prontas para o corte. Portanto, adicione um clipper e direcione o Clipper como os blocos "Saída" na saída anterior do clipper. Agora, temos um único polígono que está pronto para funcionar novamente.
  7. Use o ladrilhador novamente, desta vez especificando um bloco menor. Por exemplo, se você usou ladrilhos de 100 metros anteriormente, tente 90 metros.
  8. Adicione outro cortador, com o cortador de entrada sendo as linhas em buffer e o cortador de entrada sendo os blocos menores como entrada.

Enxágue e repita quantas vezes forem necessárias, usando peças menores a cada vez. Anexei o início de uma bancada de trabalho que usaria como uma abordagem.

Com base na sua descrição (bem detalhada), ele funcionará apenas com a sua opção 1 por enquanto. Sem dedicar muito tempo ainda.

De qualquer forma, essa é apenas uma abordagem com a qual eu começaria a filtrar o joio pelo menos.

Exemplo de bloco FME

Matthew Brucker
fonte