Как я могу найти альфа-форму (вогнутый корпус) облака 2d-точки?

Я ищу реализацию, которая вычисляет альфа-формы в двух измерениях. Я бегу ubuntu. Я бы предпочел утилиту командной строки для этой задачи, но также будет хорошо с библиотекой python.

В Google я нашел множество реализаций, которые вычисляют альфа-формы. Но ни один из них не выводит то, что я хочу. В качестве ввода у меня есть список двумерных точек (например, одна пара поплавков на строку в текстовом файле). В качестве вывода я хочу получить еще один список двумерных точек с тем же масштабом.

Я попытался установить последние привязки python cgal, но они не поддерживались через некоторое время и больше не компилируются на Ubuntu 11.04 (я также пытался использовать Ubuntu 10.04 и не повезло). Clustr, проект, разработанный в Flickr от Aaron Straup Cope, также не будет компилироваться на Ubuntu 11.04 (вероятно, потому, что он также связан с более старыми библиотеками CGAL).

Я также попробовал эту реализацию от Кен Кларксона в лабораториях колокола. Он выводит почти то, что я хочу, результат, похоже, находится в другом масштабе, и он превращает float в ints.

Я также попробовал привязки python dionysus. Они скомпилированы, но когда я передал функцию fill_alpha2D_complex(points, f) своим списком точек, результат не был тем, что я ожидал. Это был не список двумерных точек, а скорее "диаграмма персистентности", я не знаю, что это значит.

Кто-нибудь знает о простом решении этой проблемы?

ОБНОВЛЕНИЕ: Я хочу распечатать точки, связанные с альфа-формой, где она уже не находится на грани отказа. Я думаю, что это означает "дать мне точки, связанные с наименьшим значением альфа, чтобы связать фигуру".

UPDATE Теперь я узнал, как получить то, что я хочу от реализация Кен Кларксона и (более или менее то, что Я хочу) из реализации dionysus. Реализация Кларксона была правильной, она просто выводила индексы точек, а не самих точек (одна и та же история с дионисом), и мне нужно было получить некоторые необязательные флаги. Обертка, которую я написал, приведена ниже. Это решение идеально подходит, поскольку оно создает альфа-форму, которая соединена и не содержит отверстий. Альфа устанавливается автоматически. С другой стороны, Дионис не обнаруживает автоматически эти значения альфа. Плюс реализация Clarkson может быть настроена на вывод изображения ps формы (с флагом -afps). Чтобы получить код Clarkson для компиляции с не-древней версией GCC, вам необходимо выполнить описанный ниже шаг здесь. Следующий код может использоваться как библиотека или как отдельная оболочка:

#!/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)

Ответ 1