Convex Hull và SciPy

Question

Tôi đang cố gắng sử dụng scipy (0.10.1) để có bản hack nhanh để hình dung thân lồi.

Tôi có thể lấy thân lồi sử dụng đoạn mã sau:

vecs = [[-0.094218, 51.478927], [-0.09348, 51.479364], [-0.094218, 51.478927], 
     ... 
     [-0.094218, 51.478927], [-0.094321, 51.479918], [-0.094218, 51.478927], 
     [-0.094222, 51.478837], [-0.094241, 51.478388], [-0.094108, 51.478116], 
     [-0.09445, 51.480279], [-0.094256, 51.478028], [-0.094326, 51.500511]] 
hull = scipy.spatial.Delaunay(vecs).convex_hull 

mảng kết quả trông như thế này:

[[56, 9], [16, 1], [56, 1], [55, 9], [53, 55], [53, 16]] 

các con số là các chỉ số đỉnh. Vấn đề của tôi là họ không được đặt hàng. Tôi cần chúng để được theo thứ tự CW hoặc CCW để dễ dàng hình dung chúng trong KML.

Có cách nào dễ dàng để có scipy.spatial tính toán thứ tự theo chiều kim đồng hồ đúng không?

Answer 1

Vì vậy, mã này dường như thực hiện thủ thuật, nhưng có thể đơn giản hơn ... Về cơ bản, trước tiên tôi thu thập các số đỉnh từ thân tàu. Sau đó, tôi tính toán giá trị trung bình, thu thập số liệu và sắp xếp nó theo góc từ giá trị trung bình.

ps = set() 
for x, y in hull: 
    ps.add(x) 
    ps.add(y) 
ps = numpy.array(list(ps)) 
center = vecs[ps].mean(axis=0) 
A = vecs[ps] - center 
h = vecs[ps[numpy.argsort(numpy.arctan2(A[:,1], A[:,0]))]] 

Answer 2

tôi phát hiện ra một phương pháp tốt đẹp, nhưng nó đòi hỏi scipy 0.11.0 (sparse.csgraph)

Đây là một ví dụ đầy đủ, việc phân loại thực tế là 2 Lignes sau khi "loại thân ... " bình luận.

import numpy as np 
import scipy as sp 

# random point cloud and hull 
X = np.random.randint(0,200,(30,2)) 
hull = sp.spatial.qhull.Delaunay(X).convex_hull 

# sort hull indices using (sparse) adjacency matrix graph stuff 
g = sp.sparse.csr_matrix((np.ones(hull.shape[0]),hull.T), shape=(hull.max()+1,)*2) 
sorted_hull = sp.sparse.csgraph.depth_first_order(g,hull[0,0],directed=False)[0] 

# display with matplotlib 
from matplotlib import pyplot as plt 
plt.plot(X[:,0],X[:,1],'.') 
plt.plot(X[sorted_hull,0],X[sorted_hull,1]) 

Answer 3

Trong doc dev hiện tại (0.13.0.dev) của scipy.spatial.ConvexHull, có một tài sản mà là ngược chiều kim đồng trong 2D vertices.