Algoritmo para encontrar polígonos que encierran puntos

8

Estoy tratando de encontrar un algoritmo que pueda determinar los polígonos más pequeños posibles para cubrir varios puntos.

Sé cómo obtener el casco convexo alrededor de todos los puntos, pero digamos que los puntos están ubicados en diferentes islas, ¿es posible determinar que hay una brecha entre los diferentes grupos y obtener polígonos separados para cada grupo?

algorithm polygon convex-hull clustering concave-hull jjrdk
fuente
La respuesta es que solo se necesita un polígono; su área puede ser arbitrariamente cercana a cero; Y nunca es único. (Una forma de encontrar una solución: existen puntos en el plano desde los cuales todos los puntos del conjunto original son visibles. Trace una ruta que no se cruce entre sí desde este punto hacia cada uno de los puntos dados, formando una estrella con rayos extremadamente estrechos.) Esto muestra que el problema no está enunciado de manera incompleta: necesita una declaración más clara y exhaustiva del objetivo analítico.
whuber

Respuestas:

9

Parece que primero necesita un algoritmo de agrupación (p. Ej., K-significa agrupación), seguido de un casco (casco convexo, pero un casco cóncavo puede tener un área más pequeña pero más difícil de implementar).


fuente
Ver también: en.wikipedia.org/wiki/Hierarchical_clustering
julien
3

La herramienta "Clustr" que utilizamos (d) en Flickr para generar los archivos de forma derivados de fotos geoetiquetadas podría ser útil:

https://github.com/straup/Clustr

(Stackexchange me impide agregar más de 2 enlaces en esta publicación. Si busca "la forma de alfa", puede encontrar la publicación de blog code.flickr que hicimos cuando anunciamos los archivos de forma).

Fue diseñado para tratar de generar el contorno a partir de una bolsa de puntos en constante cambio (también conocido como fotos). Los bits matemáticos reales están aquí:

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

Clustr tiene algunos errores conocidos, pero en su mayoría funciona, la mayoría de las veces ...

usuario2016
fuente
2

desde la perspectiva de una base de datos, parece que quiere agrupar los puntos en las islas y hacer un casco convexo en cada grupo.

en postgis se vería algo así 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
fuente
No creo que haya sido claro en mi pregunta inicial. El punto era que no sé dónde están los puntos, pero estarán en una ubicación distinta, por lo que necesitaba un algoritmo para crear dinámicamente grupos donde estén los puntos, no moverlos a áreas definidas. Modifiqué el algoritmo de agrupación k-means para buscar en el conjunto de datos los centroides del grupo y luego el grupo.
jjrdk
¿Quieres decir que no sabes dónde están las islas? No tienes una representación vectorial de las islas, está bien. Pero, ¿qué quieres decir con "no moverlos"? ¿No
sugerí
No sé dónde se ubicarán los grupos (islas), dependerá de la ubicación de los puntos. Así que estoy tratando de encontrar el polígono más pequeño que encierra las ubicaciones de los puntos. Por movimiento, me refería a los puntos de agrupación en un recuento definido de agrupaciones como en la agrupación de k-medias.
jjrdk
1

arcpy.AggregatePoints_cartography (pntGeometryList, outAppendFeatureClass, buffer_radius)

Donde pntGeometryList es su lista de puntos, outAppendFeatureClass la clase de entidad que creará la agregación y buffer_radius que determinará los enlaces entre cada punto 'orientado externamente'.

Peludo
fuente
Disculpas, acabo de recibir el resto de tu pregunta, que no leí.
Peludo
¿Cómo cotejas tus puntos?
Peludo
1

Al principio pensé que la sugerencia de Dan para k-means tenía sentido, pero después de mirar los resultados del conjunto de datos del mouse en la página de wikipedia para k-means , parece que la agrupación de Expectation-Maximization está más cerca de lo que quieres.

ingrese la descripción de la imagen aquí

Kirk Kuykendall
fuente
1
Gracias por su respuesta, en realidad seguí adelante e hice una versión modificada del algoritmo k-means que se agrupa por distancia máxima. Escribí sobre esto aquí: reimers.dk/blogs/jacob_reimers_weblog/archive/2011/03/08/…
jjrdk
Se ve muy bien. Creo que EM seguro sería más difícil de implementar. Sería interesante ver si su código funcionaría en Silverlight, tal vez usando este TPL .
Kirk Kuykendall