Algoritmo para encontrar polígonos que envolvem pontos

8

Estou tentando encontrar um algoritmo que possa determinar os menores polígonos possíveis para cobrir vários pontos.

Eu sei como obter o casco convexo em torno de todos os pontos, mas digo que os pontos estão localizados em ilhas diferentes, é possível determinar que existe uma lacuna entre os diferentes grupos e obter polígonos separados para cada grupo?

algorithm polygon convex-hull clustering concave-hull jjrdk
fonte
A resposta é que apenas um polígono é necessário; sua área pode ser arbitrariamente próxima de zero; e nunca é único. (Uma maneira de encontrar uma solução: existem pontos no plano a partir dos quais todos os pontos do conjunto original são visíveis. Trace uma rota que não se intercepte a partir desse ponto até cada um dos pontos indicados, formando uma estrela com raios extremamente estreitos.) Isso mostra que o problema está incompleto: ele precisa de uma declaração mais clara e completa do objetivo analítico.
whuber

Respostas:

9

Parece que você precisa de um algoritmo de agrupamento (por exemplo, agrupamento K-means) primeiro, seguido de um casco (casco convexo, mas um casco côncavo pode ter uma área menor, mas mais difícil de implementar).


fonte
Veja também: en.wikipedia.org/wiki/Hierarchical_clustering
julien
3

A ferramenta "Clustr" que usamos (d) no Flickr para gerar os shapefiles derivados de fotos com identificação geográfica pode ser útil:

https://github.com/straup/Clustr

(O Stackexchange está me impedindo de adicionar mais de 2 links nesta postagem. Se você pesquisar "a forma de alfa", poderá encontrar a postagem do blog code.flickr que fizemos quando anunciamos os shapefiles.)

Ele foi projetado para tentar gerar o contorno a partir de um saco de pontos em constante mudança (também conhecido como fotos). Os bits matemáticos reais estão aqui:

http://www.cgal.org/Manual/3.2/doc_html/cgal_manual/Alpha_shapes_3/Chapter_main.html

Clustr tem alguns bugs conhecidos, mas geralmente funciona, na maioria das vezes ...

user2016
fonte
2

do ponto de vista do banco de dados, parece que você deseja agrupar os pontos nas ilhas e fazer um casco convexo em cada grupo.

no postgis, seria algo como:

SELECT ST_Convexhull(ST_Collect(p.the_geom))
FROM pointtable p INNER JOIN islands i ON ST_Intersects(p.the_geom,i.the_geom)
GROUP BY i.id;

/ Nicklas

Nicklas Avén
fonte
Eu não acho que fui claro na minha pergunta inicial. O ponto é que eu não sei onde estão os pontos, mas eles estarão em diferentes locais distintos, então eu precisava de um algoritmo para criar dinamicamente clusters onde os pontos estão, não movê-los para áreas definidas. Modifiquei o algoritmo de agrupamento k-means para pesquisar no conjunto de dados por centróides de cluster e depois agrupar.
jjrdk
Você quer dizer que não sabe onde estão as ilhas? Você não tem uma representação vetorial das ilhas, ok. Mas o que você quer dizer com "não movê-los". ? Eu não sugiro mover qualquer coisa ..
Nicklas Aven
Não sei onde os grupos (ilhas) estarão localizados, isso dependerá da localização dos pontos. Então, eu estou tentando encontrar o menor polígono que envolve os locais dos pontos. Por movimento, eu quis dizer pontos de cluster em uma contagem definida de clusters como no cluster k-means.
Jjrdk
1

arcpy.AggregatePoints_cartography (pntGeometryList, outAppendFeatureClass, buffer_radius)

Onde pntGeometryList é sua lista de pontos, outAppendFeatureClass a classe de característica que a agregação criará e buffer_radius, que determinará os links entre cada ponto 'externo'.

Peludo
fonte
Desculpas, acabei de receber o resto da sua pergunta, que eu não li.
Hairy
Como você classifica seus pontos?
Hairy
1

No começo, pensei que a sugestão de Dan para k-means fazia sentido, mas depois de examinar os resultados do conjunto de dados do mouse na página da wikipedia para k-means , parece que o cluster de Expectativa-Maximização está mais próximo do que você deseja.

insira a descrição da imagem aqui

Kirk Kuykendall
fonte
1
Obrigado pela sua resposta, na verdade eu fui adiante e fiz uma versão modificada do algoritmo k-means que agrupa por distância máxima. Eu publiquei um
jjrdk
Parece ótimo. Eu acho que o EM seria mais difícil de implementar. Seria interessante ver se seu código funcionaria no silverlight, talvez usando este TPL .
Kirk Kuykendall