¿Cómo se genera el casco no convexo de una serie de puntos?

Actualmente estoy tratando de construir el área cubierta por un dispositivo durante un período de funcionamiento. El primer paso en este proceso parece ser la construcción de un polígono del área cubierta. Dado que el patrón no es una forma estándar, los cascos convexos exageran el área cubierta saltando al área de cobertura más grande posible.¿Cómo se genera el casco no convexo de una serie de puntos?

He encontrado un documento que parece cubrir el concepto de generación de casco no convexo, pero no hay discusiones sobre cómo implementar esto en un lenguaje de alto nivel. http://www.geosensor.net/papers/duckham08.PR.pdf

¿Alguien ha visto un algoritmo directo para construir un casco no cóncavo o un casco cóncavo o quizás cualquier código python para lograr el mismo resultado?

He intentado cascos convexos principalmente qhull, con un tamaño de borde limitado con éxito limitado. También he notado algunas bibliotecas con licencia que no podrán distribuirse, por lo que desafortunadamente no está disponible. ¿Alguna mejor idea o libro de cocina?

Fuente

2010-09-01 TelsaBoil

Posiblemente la información relacionada: http://gis.stackexchange.com/questions/1200/concave-hull-definition-algorithms-and-practical-solutions – Gilead

¿Está el problema bien definido? ¿Desea * cualquier * casco no convexo que cubra los puntos? ¿O hay algunas restricciones adicionales? Considere tres puntos formando un triángulo equilátero y un cuarto punto en el centro. Hay (al menos) tres cascos no convexos posibles que encierran esos puntos. –

Wow, todos estos sitios variados de intercambio de pila realmente hacen un buen trabajo al mover preguntas fuera de la vista de las personas que podrían responderlas. :( –

Puedes probar buscando en Alpha Shapes. La biblioteca de CGAL puede calcularlos.

Editar: Veo que el papel que vinculó hace referencia a las formas alfa, y también tiene una lista de algoritmos. ¿No es ese nivel lo suficientemente alto para ti? Dado que enumeró Python como una etiqueta, estoy seguro de que hay bibliotecas de triangulación Delaunay en Python, que creo que es la parte más difícil de implementar el algoritmo; solo necesita asegurarse de que puede modificar la salida de triangulación resultante. Las funciones de consulta de límites probablemente se pueden implementar con matrices asociativas.

Fuente

2010-09-01 18:26:20

Desafortunadamente, los enlaces de python para CGAL que mencionas ya no se compilan con las últimas versiones de boost-python y CGAL. Parece que el proyecto ya no se admite. ¿Hay alguna otra alternativa de Python? – conradlee

-1

Escribí an application para calcular el casco no convexo de un conjunto de puntos (necesitará Java jre para ejecutarlo).

Fuente

2011-04-02 06:19:51

Pero estás no va a compartir el código? –

¿Cómo se genera el casco no convexo de una serie de puntos?

Respuesta

Cuestiones relacionadas