Em matemática, o casco convexo ou envelope convexo para um conjunto de pontos X em um espaço vetorial real V é o conjunto convexo mínimo que contém X ( Wikipedia )
A Wikipedia o visualiza bem, usando uma analogia com elástico, e existem alguns bons algoritmos para calculá-lo .
Um casco côncavo é visualizado usando a linha vermelha na imagem abaixo (a linha azul visualiza o casco convexo). Intuitivamente, é um polígono que abrange todos os pontos, mas tem menos (mínimo?) Área em comparação com o casco convexo. Como resultado, o comprimento do limite do polígono é maior.
Não consegui encontrar uma definição adequada, algoritmo e solução prática para a noção de casco côncavo. O Wiki da grama tem algumas descrições e imagens , e há uma solução comercial em concavehull.com .
Alguma idéia, algoritmos e links?
Em que contexto você deseja gerar cascos côncavos / formas alfa? No PostGIS, ArcMap, um mapa da web, seu próprio software?
PostGIS e meus próprios scripts Python.
Existe uma versão compatível com C ++ Linux da implementação do algoritmo do casco côncavo?
— 31418 Sylv255
A Biblioteca de Algoritmos de Geometria Computacional (CGAL) é uma biblioteca C ++ com Alpha Shapes. Possui um download do Linux e é licenciado como GPL / LGPL para a versão> = 4.0.
Como aponta o scw , você deseja uma implementação de formas α .
Edelsbrunner, H .; Kirkpatrick, D .; Seidel, R .; , "Sobre a forma de um conjunto de pontos no plano", Teoria da Informação, IEEE Transactions on, vol.29, no.4, pp. 551- 559, julho de 1983
Se você estiver usando a pilha PostGIS, a extensão Distância de direção opcional do pgRouting expõe uma implementação de formato alfa. Não tenho certeza se você pode variar o parâmetro alfa, no entanto.
Provavelmente existem muitos módulos python que você poderia usar. Eu ouvi coisas boas sobre CGAL , uma biblioteca de geometria computacional em C ++. Os wrappers Python existem para partes da CGAL, incluindo a exposição da implementação de forma alfa da CGAL ao Python .
Esteja ciente de que partes da CGAL são licenciadas sob a QPL, o que significa que, se você distribuir seu programa, vinculado à CGAL, poderá ser necessário liberá-lo sob a QPL. Não há problema em manter seu código de propriedade se você não redistribuir o código ou os binários do programa.
Não consigo compilar os wrappers python do CGAL - parece que eles não são suportados há um tempo e não funcionam mais com uma versão recente do CGAL.
— 21811 Conradlee
@mark: O segundo link que você postou parece estar morto.
ligações @fmark PostGIS parecem ser morto ..
Duckham, M., Kulik, L., Worboys, MF, Galton, A. (2008) Geração eficiente de polígonos simples para caracterizar a forma de um conjunto de pontos no plano. Reconhecimento de padrões v41, 3224-3236
Essa parece ser uma aplicação específica das formas alfa , que são da minha leitura uma forma mais geral desse problema. O R possui o módulo alphahull , que possui excelente documentação sobre o cálculo de formas alfa . Verifique também este plano de fundo detalhado das formas alfa. Se você só quer calcular cascas convexas / côncavas, veja lasboundary , parte de lastools , ele escalas bem e pode lidar com milhões de pontos de entrada.
Por fim, essa interessante aplicação de formas alfabéticas do Flickr fez as rondas há um tempo, mostrando sua utilidade para agregar conteúdo pontual gerado pelo usuário:
OMG a fonte é escrito em :-) Fortran
Existe o pacote clustr escrito em C ++, se for melhor para você; mas tenha cuidado com o licenciamento em CGAL: github.com/straup/Clustr
Belo exemplo do mundo real.
Há uma implementação de ST_ConcaveHull no tronco PostGIS. http://postgis.net/docs/ST_ConcaveHull.html
Acho que este aparece pela primeira vez na versão 2.0 do PostGIS
Criei uma ferramenta altamente eficiente, chamada [lasboundary] [1,2], que calcula um casco côncavo para o LIDAR no formato LAS / LAZ / SHP / ASCII e armazena o resultado como um polígono de limite de vetor no formato ESRI Shapefile ou um geo arquivo KML com referência.
Algumas fotos dos resultados estão aqui .
Sobre a implementação do Alpha-Shapes, há um artigo sobre "Convertendo o Alpha-Shapes em objetos SP"
** Atualização (15-01-2018) Houve inúmeras alterações nos objetos resultantes produzidos pelo pacote alphahull. Como tal, eu precisava reescrever a função. Adicionei uma função convexHull ao pacote spatialEco. No entanto, devido a restrições de licenciamento no pacote alphahull, esta função está disponível apenas na versão de desenvolvimento no GitHub. A versão de desenvolvimento pode ser instalada usando:
+1 Você poderia explicar como isso difere do pacote de formas alfa ?
A saída do objeto alphahull é armazenada como uma matriz e deve ser coagida a um objeto sp utilizável. Eu consideraria isso uma função "auxiliar" para criar um polígono que pode ser exportado para um formato GIS. Essa função usa o pacote alphahull para criar o objeto da matriz do casco, cria um objeto sp e explode o slot de polígono, tornando-o um objeto de quadro de dados de polígono de peça única. Nada está aparecendo na ajuda do pacote, mas pode haver coerção nativa implementada recentemente para um objeto de classe sp que eu não conheço. Se for esse o caso, informe-me para que eu possa desativar esta função.
— 21412 Jeffrey Evans
Obrigado @JeffreyEvans Eu consegui fazer isso funcionar. Você poderia explicar os parâmetros? Dei uma olhada no artigo vinculado da jstatsoft, mas é bastante impenetrável.
O JTS ( http://tsusiatsoftware.net/jts/main.html ) fornece uma implementação de Casco Convexo. Martin Davies também mencionou ter um algoritmo Alpha Shape em andamento, portanto, talvez você queira verificar o repositório SVN para ver se ele ainda existe, se é isso que você deseja.
Ainda não há implementação côncava de formas de casco / alfa a partir de junho de 2012, até onde eu sei.
Ainda nada em Maio de 2013.
O JTS está vivo? A última versão é de 19 de dezembro de 2006. vividsolutions.com/jts/JTSHome.htm
tente o link na resposta
O JTS agora está no Github e é a versão 1.15 da abordagem: github.com/locationtech/jts Embora, até onde eu saiba , ainda não pareça haver uma implementação do Alpha Shapes.
Falando sobre JTS, você pode usar o Geoscript para manipular a biblioteca JTS. http://geoscriptblog.blogspot.com/2010/06/unwrapped-jts-with-python.html para obter um artigo sobre casco convexo. As implementações do GeoScript estão disponíveis em JavaScript, Python, Scala e Groovy. O site oficial: http://geoscript.org
Aqui está um programa escrito em C que calcula cascos convexos, formas alfa, triangluações de Delauney e volumes de Voronoi:
Casco - Ken Clarkson (2002)
Outro algoritmo de casco convexo com implementações C e Java está aqui:
Casco Convexo (2D) - Geometria Computacional em C , Joseph O'Rourke (1998)
Para adicionar respostas anteriores a este post, pelo menos a partir do QGIS 2.6 possui algoritmo de casco côncavo
Camada de ponto de entrada [vector: point]
coloque aqui a descrição do parâmetro
Limite (0-1, onde 1 é equivalente ao Casco Convexo) [número]
Permitir furos [booleano]
Dividir geometria de várias partes em geometrias de peças únicas [booleano]
coloque aqui a descrição da saída
Processamento de uso do console.runalg ('qgis: côncavo', entrada, alfa, buracos, no_multigeometry, saída)
Além disso, a Esri possui uma ferramenta Geometria Mínima de Limite (Gerenciamento de Dados)
O que permite escolher o tipo de geometria, que inclui casco convexo
Existe um novo complemento para o GRASS GIS 7 disponível: v.concave.hull . Veja também http://grasswiki.osgeo.org/wiki/Create_concave_hull
Para ajudar com a parte de "definição adequada" da sua pergunta; você pode ter consultado https://en.wikipedia.org/wiki/Convex_hull e obtido o que poderia ser considerado uma definição "adequada", mas achou que falta, por isso talvez uma definição mais "útil" seja:
Para cada ponto dentro de um casco convexo, uma linha reta para qualquer ponto fora do casco só cruza o casco uma vez.
Isso é útil porque, dado um ponto, você pode construir uma linha através dela e testar a linha construída que cruza os segmentos do casco.