Existe um algoritmo eficiente para gerar um casco côncavo 2D?
https://stackoverflow.com/questions/83593
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Ter um conjunto de pontos (2D) de um arquivo GIS (um mapa da cidade), eu preciso gerar o polígono que define a 'contorno' para que o mapa (o seu limite). Seus parâmetros de entrada seriam os pontos definidos e um 'comprimento máximo edge'. Seria, então, a saída (provavelmente não-convexo) polígono correspondente.
A melhor solução que foi encontrada até agora para gerar os triângulos Delaunay e, em seguida, remover as arestas externas que são mais longos do que o comprimento máximo da borda. Depois de todas as bordas externas são mais curtos do que isso, eu simplesmente remover as bordas internas e obter o polígono que eu quero. O problema é, isso é muito demorado e eu estou querendo saber se há uma maneira melhor.
Solução
Este artigo discute o Geração eficiente de polígonos simples para caracterizar a forma de um conjunto de pontos no plano e fornece o algoritmo. Há também um applet Java utilizando o mesmo algoritmo aqui .
Outras dicas
Um dos ex-alunos em nosso laboratório usado algumas técnicas aplicáveis ??para a sua tese de doutoramento. Creio que um deles é chamado de "formas alfa" e é referenciado no seguinte documento:
http://www.cis.rit.edu/ pessoas / faculdade / Kerekes / pdfs / AIPR_2007_Gurram.pdf
Esse documento dá algumas outras referências que você pode seguir.
Os caras reivindicação aqui ter desenvolvido ak vizinhos mais próximos abordagem para determinar o casco côncavo de um conjunto de pontos que se comporta "quase linearmente sobre o número de pontos". Infelizmente o seu papel parece ser muito bem guardado e você terá que perguntar -los para ele.
Aqui está um bom conjunto de referências que inclui o exposto, e pode levá-lo a encontrar uma abordagem melhor.
A resposta ainda pode ser interessante para alguém: Pode-se aplicar um variação do algoritmo quadrado marchando , aplicada (1) dentro do casco côncavo, e (2), em seguida, em (por exemplo, 3) diferentes escalas que meu depender da densidade média de pontos. As escalas precisam ser múltiplos int um do outro, como você construir uma grade que você pode usar para a amostragem eficiente. Isso permite encontrar rapidamente amostras vazias = quadrados, amostras que estão completamente dentro de um "cluster / nuvem" de pontos, e aqueles, que estão no meio. A última categoria, em seguida, pode ser utilizado para determinar facilmente a-linha poli que representa uma parte do casco côncava.
Tudo é linear nesta abordagem, não há necessidade de triangulação, ele não usa alfa formas e é diferente da oferta comercial / patenteado como descrito aqui ( http://www.concavehull.com/ )
Uma solução simples é caminhar ao redor da borda do polígono. Dada a margem atual om a fronteira conectando pontos P0 e P1, o próximo ponto na P2 limite será o ponto com o menor Um possível, onde
H01 = bearing from P0 to P1
H12 = bearing from P1 to P2
A = fmod( H12-H01+360, 360 )
|P2-P1| <= MaxEdgeLength
Em seguida, você configurar
P0 <- P1
P1 <- P2
e repita até chegar de volta onde você começou.
Este ainda é O (n ^ 2), de modo que você vai querer classificar sua pointList um pouco. Você pode limitar o conjunto de pontos que você precisa considerar em cada iteração se você aponta espécie, digamos, o seu rolamento do baricentro da cidade.
Boa pergunta! Eu não tentei isso em tudo, mas o meu primeiro tiro seria este método iterativo:
- Criar um conjunto N ( "não continha"), e adicionar todos os pontos em seu conjunto para N.
- Escolha 3 pontos da N aleatoriamente para formar um polígono inicial P. Retire-os de N.
- algum ponto no polígono algoritmo olhada pontos em N. Para cada ponto em N, se ele está agora contido por P, remova-a N. assim que você encontrar um ponto em N que ainda não está contido em P, vá para a etapa 4. Se N fica vazia, você está feito.
- Chame o ponto que você encontrou A. Encontre a linha em P mais próximo de A, e adicionar um no meio dela.
- Volte para a etapa 3
Eu acho que ele iria trabalhar enquanto ele executa bem o suficiente -. Uma boa heurística para as suas iniciais 3 pontos pode ajudar
Boa sorte!
Você pode fazê-lo em QGIS com este plug-in; https://github.com/detlevn/QGIS-ConcaveHull-Plugin
Dependendo de como você precisa para interagir com os seus dados, provavelmente vale a pena conferir como foi feito aqui.
O SDK interativo Bing Maps V8 tem uma opção de casco côncavo dentro das operações de forma avançada.
Dentro ArcGIS 10.5.1, a extensão 3D Analyst tem uma ferramenta Volume delimitadora mínima com os tipos de geometria de casco côncavo, esfera, envelope ou casca convexa. Ele pode ser usado em qualquer nível de licença.
Há um algoritmo casco côncavo aqui: https://github.com/mapbox/concaveman
A solução aproximada rápida (também útil para cascos convexos) é encontrar o norte e sul limites para cada pequeno elemento leste-oeste.
Com base na quantidade de detalhes que você quiser, criar uma matriz de tamanho fixo de superiores limites / inferiores. Para cada ponto que calcule coluna E-W é em seguida e actualizar os limites superior / inferior para a coluna. Depois de processados ??todos os pontos que você pode interpolar os superiores / pontos mais baixos para as colunas que perdidas.
Ele também vale a pena fazer uma verificação rápida de antemão para formas muito finas e decidir wether para bin NS ou Ew.
Como referência descontroladamente adotado, PostGIS começa com uma envoltória convexa e depois cavernas-lo, você pode vê-lo aqui.
