Вычисление расстояния до выпуклой оболочки

Question

Я использую класс scipy ConvexHull, чтобы построить выпуклый корпус для набора точек. Меня интересует способ вычисления минимального расстояния новой точки P из выпуклого корпуса.

С помощью Интернета и небольшой настройки по себе я придумал эту формулу для вычисления расстояния точки P или набора точек точек для выпуклых граней корпуса:

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

Для выпуклой оболочки в 2D уравнение выше приведет к следующему сюжету:

Как вы можете видеть, т он получается довольно хорошо и правильно для точек внутри выпуклого корпуса (расстояние здесь отрицательное и нужно будет умножить на -1). Он также верен для точек, наиболее близких к грани, но неправильных для точек, наиболее близких к вершине выпуклой оболочки. (Я обозначил эти области пунктирными линиями). Для этих точек правильным минимальным расстоянием было бы минимальное расстояние до вершин вершинного корпуса.

Как можно различать точки, которые находятся ближе всего к фаске или ближе к вершине, чтобы правильно вычислить минимальное расстояние до выпуклой оболочки для точки P или множество точек точки в п-мерном пространство (по крайней мере, 3D)?

Answer 1

если точки выпуклой оболочки приведены в виде массива NX2 и точка задается как р = [х, у]

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)