计算到凸包的距离 [英] Computing the distance to a convex hull

问题描述

我正在使用

如您所见，结果非常好，并且对于凸包内的点是正确的(此处的距离为负，需要与 -1 相乘).对于最接近小平面的点也是正确的，但对于最接近凸包的顶点的点也是不正确的.(我用虚线标记了这些区域)对于这些点，正确的最小距离应该是到凸包顶点的最小距离.

如何区分最接近小平面或最接近顶点的点，以正确计算点 P 或一组点 points到凸包的最小距离在n维空间(至少3D)中?

解决方案

如果凸包的点以NX2数组的形式给出，并且该点以p = [x，y]的形式给出

 导入数学#from http://stackoverflow.com/questions/849211/shortest-distance-between-a-point-and-a-line-segmentdef dist(x1，y1，x2，y2，x3，y3):#x3，y3是点px = x2-x1py = y2-y1某物= px * px + py * pyu =((x3-x1)* px +(y3-y1)* py)/浮点数如果u>1:u = 1Elif你<0:u = 0x = x1 + u * pxy = y1 + u * pydx = x-x3dy = y-y3#注意:如果实际距离无关紧要，#如果您只想比较此功能#返回此函数的其他结果，您#可以只返回平方距离#(即删除sqrt)以提高性能dist = math.sqrt(dx * dx + dy * dy)返回distdists = []对于范围内的我(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 =分钟(dists) 

I am using the ConvexHull class of scipy to construct a convex hull for a set of points. I am interested in a way to compute the minimum distance of a new point P from the convex hull.

With the help of the internet and a little tweaking by myself I came up with this formula to compute the distance of a point P or a set of points points to the convex hull facets:

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

For a convex hull in 2D the equation above will result in the following plot:

As you can see the result is pretty good and correct for points within the convex hull (The distance here is negative and would need to be multiplied with -1). It is also correct for points that are closest to a facet but incorrect for points that are closest to a vertex of the convex hull. (I marked these regions with the dashed lines) For these points the correct minimum distance would be the minimum distance to the convex hull vertices.

How can I distinguish between points that are closest to a facet or closest to a vertex to correctly compute the minimum distance to the convex hull for a point P or a set of points points in an n-Dimensional space (At least 3D)?

解决方案

if the points of the convex hull are given as a NX2 array and the point is given as 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)

这篇关于计算到凸包的距离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！