计算到凸包的距离

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)