凸包への距離を計算する

Question

私はConvexHullクラスのscipyを使用して、一連の点の凸包を作成しています。私は凸包から新しい点Pの最小距離を計算する方法に興味があります。

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

：インターネットの助けを借りて、私はポイント Pまたは点の集合 ポイント凸包ファセットへの距離を計算するために、この式を思い付い自分で少しひねると

あなたがトンを見ることができるように

：

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)