計算到凸包的距離

Question

我正在使用ConvexHull類的scipy爲一組點構造一個凸包。我感興趣的是一種計算來自凸包的新點的最小距離的方法。

隨着互聯網的幫助，並通過自己一點點的調整，我想出了這個公式來計算點P的距離或一組點點的凸包方面：

np.max(np.dot(self.equations[:, :-1], points.T).T + self.equations[:, -1], axis=-1) 

對於2D凸殼上面的等式將導致以下情節：

正如你可以看到噸他的結果非常好，並且對於凸包內的點是正確的（這裏的距離是負值，需要乘以-1）。對於最接近面的點也是正確的，但對於最接近凸包頂點的點不正確。 （我用虛線標記這些區域）對於這些點，正確的最小距離將是到凸包頂點的最小距離。

我怎樣才能點是最接近的小平面或最接近於頂點正確計算的凸殼的最小距離爲N維的點P或一組點點區分空間（至少3D）？

Answer 1

如果凸包的點被給定爲一個NX2陣列和點給定爲P = [X，Y]

import math 
#from http://stackoverflow.com/questions/849211/shortest-distance-between-a-point-and-a-line-segment 
def dist(x1,y1, x2,y2, x3,y3): # x3,y3 is the point 
    px = x2-x1 
    py = y2-y1 

    something = px*px + py*py 

    u = ((x3 - x1) * px + (y3 - y1) * py)/float(something) 

    if u > 1: 
     u = 1 
    elif u < 0: 
     u = 0 

    x = x1 + u * px 
    y = y1 + u * py 

    dx = x - x3 
    dy = y - y3 

    # Note: If the actual distance does not matter, 
    # if you only want to compare what this function 
    # returns to other results of this function, you 
    # can just return the squared distance instead 
    # (i.e. remove the sqrt) to gain a little performance 

    dist = math.sqrt(dx*dx + dy*dy) 

    return dist 

dists=[] 
for i in range(len(points)-1): 
    dists.append(dist(points[i][0],points[i][1],points[i+1][0],points[i+1][1],p[0],p[1])) 
dist = min(dists)