Làm thế nào tôi có thể tìm thấy hình dạng alpha (lõm lõm) của một đám mây điểm 2d?

Question

Tôi đang tìm cách triển khai tính toán hình dạng alpha theo hai chiều. Tôi đang chạy ubuntu. Tôi thích một tiện ích dòng lệnh cho nhiệm vụ này, nhưng cũng sẽ ổn với thư viện python.

Trong Google, tôi đã tìm thấy nhiều triển khai tính toán hình dạng alpha. Nhưng không ai trong số họ sản xuất những gì tôi muốn. Là đầu vào, tôi có một danh sách các điểm hai chiều (ví dụ: một cặp nổi trên mỗi dòng trong một tệp văn bản). Khi đầu ra, tôi muốn có một danh sách hai điểm chiều khác là với cùng một tỷ lệ.

Tôi đã thử cài đặt các ràng buộc python mới nhất của cgal, nhưng chúng không được hỗ trợ trong một thời gian và không còn biên dịch trên Ubuntu 11.04 (tôi cũng đã thử trên Ubuntu 10.04 và không có may mắn). Clustr, một dự án được phát triển tại flickr bởi Aaron Straup Cope cũng sẽ không biên dịch trên Ubuntu 11.04 (có thể vì nó cũng được gắn với các thư viện CGAL cũ hơn).

Tôi cũng đã thử sử dụng this implementation từ Ken Clarkson tại phòng thí nghiệm chuông. Nó kết quả đầu ra gần như những gì tôi muốn, đầu ra có vẻ là ở quy mô khác và nó biến nổi thành ints.

Tôi cũng đã thử các kết buộc python của dionysus. Những biên dịch, nhưng khi tôi cho ăn hàm fill_alpha2D_complex(points, f) với danh sách các điểm của tôi, đầu ra không phải là những gì tôi mong đợi. Nó không phải là một danh sách các điểm hai chiều, mà đúng hơn là một "sơ đồ bền bỉ" Tôi không biết điều đó có nghĩa là gì.

Có ai biết giải pháp đơn giản cho vấn đề này không?

CẬP NHẬT: Tôi muốn in các điểm được liên kết với hình dạng alpha nơi nó đang trên bờ vực không được kết nối nữa. Tôi nghĩ điều này có nghĩa là "cho tôi những điểm liên kết với giá trị alpha nhỏ nhất sao cho hình dạng được kết nối."

CẬP NHẬT Tôi đã tìm ra cách để có được những gì tôi muốn từ Ken Clarkson's implementation và (nhiều hơn hoặc ít hơn những gì tôi muốn) từ dionysus implementation. Việc thực hiện của Clarkson đã làm đúng, nó chỉ xuất ra các chỉ số của các điểm chứ không phải là các điểm (cùng câu chuyện với dionysus), và tôi cần phải có một số cờ tùy chọn ngay. Các wrapper tôi đã viết là dưới đây. Giải pháp này lý tưởng vì nó tạo ra một hình dạng alpha vừa kết nối vừa không có lỗ. Alpha được đặt tự động. Dionysus, mặt khác, không tự động phát hiện ra giá trị alpha này. Cộng với việc thực hiện Clarkson có thể được thiết lập để xuất ra một hình ảnh ps của hình dạng (với cờ -afps). Để có được mã của Clarkson biên dịch với phiên bản GCC không cổ, bạn cần thực hiện theo bước được nêu here. Các mã sau đây có thể được sử dụng như một thư viện hoặc là một độc lập wrapper:

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

tôi thấy this trong tài liệu dionysus mà có thể cung cấp cho bạn hình dạng alpha:

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

Sau đó, tôi tin rằng bạn cần để làm điều gì đó như:

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