5

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:

Distance to Convex Hull

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)?

Woltan
  • 13,723
  • 15
  • 78
  • 104
  • use a point to segment formula for each of the convex hull segments and take the minimum – OMRY VOLK Dec 06 '16 at 16:42
  • @user4421975 Could you please elaborate on your comment? What is a point of a segment formula? – Woltan Dec 06 '16 at 16:57
  • for each point calculate it's distance to each line segment of the convex hull using http://stackoverflow.com/questions/849211/shortest-distance-between-a-point-and-a-line-segment and take the closest one – OMRY VOLK Dec 06 '16 at 17:07

1 Answers1

1

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)
OMRY VOLK
  • 1,429
  • 11
  • 24