¿Cómo puedo encontrar la forma alfa (casco cóncavo) de una nube de 2d?

Question

Estoy buscando una implementación que calcule formas alfa en dos dimensiones. Estoy ejecutando ubuntu. Preferiría una utilidad de línea de comandos para esta tarea, pero también estaría bien con una biblioteca de Python.

En Google he encontrado muchas implementaciones que calculan formas alfa. Pero ninguno de ellos produce lo que quiero. Como entrada, tengo una lista de dos puntos dimensionales (por ejemplo, un par de flotadores por línea en un archivo de texto). Como salida quiero otra lista de dos puntos dimensionales con la misma escala.

He intentado instalar los últimos enlaces python de cgal, pero estos no han sido compatibles desde hace tiempo y ya no se compilan en Ubuntu 11.04 (también probé Ubuntu 10.04 y no tuve suerte). Clustr, un proyecto desarrollado en flickr por Aaron Straup Cope tampoco compilará en Ubuntu 11.04 (probablemente porque también está vinculado a bibliotecas CGAL más antiguas).

También probé this implementation de un Ken Clarkson en Bell Labs. Emite casi lo que quiero, el resultado parece estar en otra escala y convierte los flotadores en entradas.

También probé las vinculaciones de python de dionysus. Estos compilados, pero cuando alimenté la función fill_alpha2D_complex(points, f) con mi lista de puntos, la salida no era la que esperaba. No era una lista de dos puntos dimensionales, sino que parece ser un "diagrama de persistencia". No sé lo que eso significa.

¿Alguien sabe de una solución simple a este problema?

ACTUALIZACIÓN: Quiero imprimir los puntos asociados con la forma alfa donde está a punto de no estar conectado. Creo que esto significa "darme los puntos asociados con el valor alfa más pequeño para que la forma esté conectada".

ACTUALIZACIÓN Ahora descubrí cómo conseguir lo que quiero de Ken Clarkson's implementation y (más o menos lo que quiero) del dionysus implementation. La implementación de Clarkson estaba haciendo lo correcto, solo sacaba los índices de los puntos en lugar de los puntos en sí (la misma historia con dionysus), y necesitaba obtener algunas banderas opcionales correctas. El contenedor que escribí está debajo. Esta solución es ideal porque produce una forma alfa que está conectada y no contiene agujeros. Alpha se establece automáticamente. Dionysus, por otro lado, no descubre automáticamente estos valores de alfa. Además, la implementación de Clarkson se puede configurar para generar una imagen ps de la forma (con el indicador -afps). Para obtener el código de Clarkson para compilar con la versión no antigua de GCC, debe seguir el paso descrito here. El siguiente código puede ser utilizado como una biblioteca o como un solo envoltorio:

#!/usr/bin/python -O 

import sys, os 
import subprocess 
import tempfile 

hull_path = "./hull.exe" 

def get_alpha_shape(points): 
    # Write points to tempfile 
    tmpfile = tempfile.NamedTemporaryFile(delete=False) 
    for point in points: 
     tmpfile.write("%0.7f %0.7f\n" % point) 
    tmpfile.close() 

    # Run hull 
    command = "%s -A -m1000000 -oN < %s" % (hull_path, tmpfile.name) 
    print >> sys.stderr, "Running command: %s" % command 
    retcode = subprocess.call(command, shell=True) 
    if retcode != 0: 
     print >> sys.stderr, "Warning: bad retcode returned by hull. Retcode value:" % retcode 
    os.remove(tmpfile.name) 

    # Parse results 
    results_file = open("hout-alf") 
    results_file.next() # skip header 
    results_indices = [[int(i) for i in line.rstrip().split()] for line in results_file] 
# print "results length = %d" % len(results_indices) 
    results_file.close() 
    os.remove(results_file.name) 

    return [(points[i], points[j]) for i,j in results_indices] 

if __name__ == "__main__": 
    points = [tuple([float(i) for i in line.rstrip().split()]) for line in sys.stdin] 
    for point_i, point_j in get_alpha_shape(points): 
     sys.stdout.write("%0.7f,%0.7f\t%0.7f,%0.7f\n" % (point_i[0], point_i[1], point_j[0], point_j[1])) 
    sys.exit(0) 

Answer 1

encontré this en la documentación de Dioniso, que podrían darle la forma alfa:

complex = Filtration() 
fill_alpha2D_complex(points, complex) 
alphashape = [s for s in complex if s.data[0] <= .5] 

Entonces yo creo que necesita para hacer algo como:

for simplex in alphashape: 
    print [v for v in simplex.vertices]