Convex Hull und SciPy

Question

Ich versuche Scipy (0.10.1) für einen schnellen Hack zu verwenden, um die konvexe Hülle zu visualisieren.

Ich kann die konvexe Hülle mit dem folgenden Code erhalten:

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

die Zahlen sind der Vertex-Indizes:

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 

das resultierende Array wie folgt aussieht. Mein Problem ist sie sind nicht bestellt. Ich brauche sie in CW- oder CCW-Reihenfolge, um sie einfach in KML zu visualisieren.

Gibt es eine einfache Möglichkeit, scipy.spatial die richtige Reihenfolge im Uhrzeigersinn zu berechnen?

Answer 1

So scheint dieser Code den Trick zu tun, könnte aber einfacher sein ... Im Wesentlichen sammle ich zuerst die Eckennummern aus dem Rumpf. Dann berechne ich den Mittelwert, zentriere den Datensatz neu und sortiere ihn nach dem Winkel vom Mittelwert.

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

Ich fand eine schöne Methode, aber es erfordert scipy 0.11.0 (sparse.csgraph)

Hier ist ein vollständiges Beispiel, die tatsächliche Sortierung sind die 2 lignes nach der „Art Rumpf ... " Kommentar.

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

Im aktuellen dev doc (0.13.0.dev) von scipy.spatial.ConvexHull gibt es eine vertices Eigenschaft, die gegen den Uhrzeigersinn in 2D.