计算到凸包的距离

Question

我正在使用scipy的ConvexHull类构建一组点的凸包。我希望找到一种方法来计算一个新点P到凸包的最小距离。

在互联网的帮助下，再加上我的一点调整，我得出了这个公式来计算一个点P或一组点points到凸包面的距离：

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

在二维凸包中，上述方程将导致以下图形：

如您所见，对于凸包内的点，结果非常好且正确（这里的距离为负数，需要乘以-1）。对于最靠近一个面的点也是正确的，但对于最靠近凸包顶点的点则不正确（我用虚线标记了这些区域）。对于这些点，正确的最小距离应该是到凸包顶点的最小距离。

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

- Woltan

---

使用点来分割每个凸包段的公式，并取最小值。 - OMRY VOLK

@user4421975，您能否详细说明一下您的评论？什么是线段公式的作用？ - Woltan

对于每个点，使用 https://dev59.com/fXRA5IYBdhLWcg3wuAcp 计算它到凸包的每条线段的距离，并取最近的距离。 - OMRY VOLK

Answer 1

如果凸包的点以 NX2 数组的形式给出，而点 p=[x,y] 也已知。

import math
#from https://dev59.com/fXRA5IYBdhLWcg3wuAcp
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)

- OMRY VOLK

---

谢谢您的回答。这个方法也可以转换成n维空间吗？或者至少是3D空间吗？我在问题中没有提到这一点，我会相应地编辑问题。 - Woltan

我相信如果你稍微搜索一下，就可以改变公式适应3D。 - OMRY VOLK

你可以将sqrt移到min之后以减少操作。 - Eran Yogev