볼록한 선체까지의 거리 계산하기

Question

나는 ConvexHull scipy 클래스를 사용하여 점 집합에 대한 볼록 선체를 만듭니다. 나는 convex houll로부터 새로운 점 P의 최소 거리를 계산하는 방법에 관심이있다. 인터넷의 도움과 자신에 의해 약간의 조정으로

나는 점 P의 거리 또는 점 세트를 계산하는 공식 함께했다 포인트 볼록 선체 측면에 :

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

식 위에서 다음 플롯 될 것이다 2D 볼록 선체

:

t는 볼 수 있듯이 그는 결과가 꽤 좋으며 볼록 선체 내의 점을 수정합니다. 여기에 거리가 음수이고 -1으로 곱해야합니다. 또한 패싯에 가장 가깝지만 볼록 선체의 꼭지점에 가장 가까운 점에 대해서는 올바르지 않습니다. (나는이 영역을 점선으로 표시했다.)이 점들에 대해 정확한 최소 거리는 볼록한 선체 꼭지점까지의 최소 거리가 될 것이다.

어떻게 정확하게 N 차원의 포인트 P 또는 점 세트 점위한 볼록 선체의 최소 거리를 계산하는 정점 패싯에 가까운 또는 가장 가까이있는 지점을 구별 할 공간 (적어도 3D)?

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)