计算到凸hu的距离

Question

我使用scipy的ConvexHull类为一组点构造一个凸壳。我感兴趣的是一种计算新点到凸壳的最小距离的方法。在

在互联网的帮助下，我自己稍作调整，就想出了一个公式来计算一个点p或一组点点到凸包面的距离：

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

对于2D中的凸面外壳，上述方程将得出以下曲线图：

如您所见，对于凸壳内的点，结果非常好且正确（此处的距离为负值，需要乘以-1）。对于离壳最近的点是不正确的，但对于离壳最近的点也是正确的。（我用虚线标记了这些区域）对于这些点，正确的最小距离是到凸壳顶点的最小距离。在

如何区分最接近面或最接近顶点的点，以正确计算n维空间（至少3D）中点p或一组点点到凸包的最小距离？在

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)