it-swarm-pt.tech

Existe um algoritmo eficiente para gerar um casco côncavo 2D?

Tendo um conjunto de pontos (2D) de um arquivo GIS (um mapa da cidade), eu preciso gerar o polígono que define o 'contorno' para esse mapa (seu limite). Seus parâmetros de entrada seriam os pontos definidos e um 'comprimento máximo da borda'. Em seguida, emitirá o polígono correspondente (provavelmente não convexo).

A melhor solução que encontrei até agora foi gerar os triângulos Delaunay e depois remover as arestas externas que são mais longas que o comprimento máximo do Edge. Depois que todas as arestas externas são mais curtas do que isso, simplesmente removo as arestas internas e obtenho o polígono que quero. O problema é que isso é muito demorado e eu estou querendo saber se há uma maneira melhor.

59
Fabio Ceconello

Este paper 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 .

2
Amirali

Um dos ex-alunos do nosso laboratório usou algumas técnicas aplicáveis ​​para sua tese de doutorado. Eu acredito que um deles é chamado de "formas alfa" e é referenciado no seguinte artigo:

http://www.cis.rit.edu/people/faculty/kerekes/pdfs/AIPR_2007_Gurram.pdf

Esse documento fornece algumas referências adicionais que você pode seguir.

10
nsanders

A resposta pode ainda ser interessante para outra pessoa: pode-se aplicar um variação do algoritmo de marcha quadrada, aplicado (1) dentro do casco côncavo, e (2) então (eg 3) diferente escalas que dependem da densidade média de pontos. As escalas precisam ser múltiplas entre si, assim você constrói uma grade que você pode usar para uma amostragem eficiente. Isso permite encontrar rapidamente amostras vazias = quadrados, amostras que estão completamente dentro de um "cluster/nuvem" de pontos e aquelas que estão entre elas. A última categoria pode então ser usada para determinar facilmente a linha poligonal que representa uma parte do casco côncavo.

Tudo é linear nesta abordagem, nenhuma triangulação é necessária, não usa formas alfa e é diferente da oferta comercial/patenteada como descrito aqui ( http://www.concavehull.com/ )

2
monnoo

Os sujeitos aqui afirmam ter desenvolvido uma aproximação de vizinhos k mais próximos para determinar o casco côncavo de um conjunto de pontos que se comportam "quase linearmente no número de pontos". Infelizmente o papel deles parece estar muito bem guardado e você terá que perguntar eles por isso.

Aqui está um bom conjunto de referências que inclui o acima e pode levar você a encontrar uma melhor abordagem.

2
Vinko Vrsalovic

O SDK interativo do Bing Maps V8 tem uma opção de casco côncavo nas operações de formas avançadas.

https://www.bing.com/mapspreview/sdkrelease/mapcontrol/isdk/advancedshapeoperations?toWww=1&redig=D53FACBB1A00423195C53D841EA0D14E#JS

Dentro do ArcGIS 10.5.1, a extensão 3D Analyst possui uma ferramenta Minimum Bounding Volume com os tipos de geometria de casco côncavo, esfera, envelope ou casco convexo. Pode ser usado em qualquer nível de licença.

Existe um algoritmo de casco côncavo aqui: https://github.com/mapbox/concaveman

1
Jaybird64

Uma solução simples é percorrer o Edge do polígono. Dado um Edge atual om o limite conectando pontos P0 e P1, o próximo ponto no limite P2 será o ponto com o menor possível A, onde

H01 = bearing from P0 to P1
H12 = bearing from P1 to P2
A = fmod( H12-H01+360, 360 )
|P2-P1| <= MaxEdgeLength

Então você define

P0 <- P1
P1 <- P2

e repita até você voltar ao ponto de partida.

Isso ainda é O (N ^ 2), então você vai querer classificar sua lista de pontos um pouco. Você pode limitar o conjunto de pontos que você precisa considerar em cada iteração se você classificar os pontos, digamos, no rolamento do centroide da cidade.

1
Mike F

Você pode fazê-lo no QGIS com este plug-in; https://github.com/detlevn/QGIS-ConcaveHull-Plugin

Dependendo de como você precisa para interagir com seus dados, provavelmente vale a pena conferir como isso foi feito aqui.

1
Cameron

Boa pergunta! Eu não tentei isso em tudo, mas meu primeiro tiro seria este método iterativo:

  1. Crie um conjunto N ("não contido") e adicione todos os pontos do seu conjunto a N.
  2. Escolha 3 pontos de N aleatoriamente para formar um polígono inicial P. Remova-os de N.
  3. Use algum algoritmo ponto-em-polígono e observe os pontos em N. Para cada ponto em N, se ele estiver agora contido por P, remova-o de N. Assim que você encontrar um ponto em N que ainda esteja não contido em P, continue na etapa 4. Se N ficar vazio, você está pronto.
  4. Chame o ponto que você encontrou A. Encontre a linha em P mais próxima de A, e adicione A no meio dela.
  5. Volte para o passo 3

Eu acho que funcionaria desde que funcionasse bem - uma boa heurística para seus 3 pontos iniciais poderia ajudar.

Boa sorte!

1
Rob Dickerson

Como uma referência amplamente adotada, o PostGIS começa com um casco convexo e depois o cava, você pode vê-lo aqui.

https://github.com/postgis/postgis/blob/380583da73227ca1a52da0e0b3413b92ae69af9d/postgis/postgis.sql.in#L5819

0
Evan Carroll

Uma solução aproximada rápida (também útil para cascos convexos) é encontrar os limites norte e sul para cada pequeno elemento leste-oeste.

Com base em quantos detalhes você deseja, crie uma matriz de tamanho fixo de limites superior/inferior. Para cada ponto, calcule em qual coluna E-W está e atualize os limites superior/inferior dessa coluna. Depois de processar todos os pontos, você pode interpolar os pontos superior/inferior das colunas perdidas.

Também vale a pena fazer uma verificação rápida de antemão para formas muito longas e finas e decidir qual é a posição NS ou Ew.

0
Martin Beckett