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

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

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

Я попытался установить последние привязки Python для cgal , но они не поддерживались некоторое время и больше не компилируется на Ubuntu 11.04 (я также пробовал на Ubuntu 10.04, и мне не повезло). Clustr , проект, разработанный на flickr Аароном Страупом Копом, также не будет компилироваться на Ubuntu 11.04 (вероятно, потому, что он также привязан к более старым библиотекам CGAL).

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

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

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

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

ОБНОВЛЕНИЕ Теперь я узнал, как получить то, что я хочу, из реализации Кена Кларксона и (более или менее того, что я хочу) из реализации диониса . Реализация Кларксона поступала правильно: она просто выводила индексы точек, а не сами точки (та же история с Дионисом), и мне нужно было правильно установить некоторые дополнительные флаги. Обертка, которую я написал, ниже.Это решение идеально, поскольку оно создает альфа-форму, которая одновременно соединена и не содержит отверстий. Альфа устанавливается автоматически. С другой стороны, Дионис не обнаруживает эти значения альфы автоматически. Плюс реализация Кларксона может быть настроена для вывода изображения формы ps (с флагом -afps). Чтобы код Кларксона скомпилировался с не-древней версией 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)