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

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

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

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

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

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

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

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


python numpy scipy distance convex-hull
person Woltan    schedule 06.12.2016    source источник
comment
используйте формулу точки для сегмента для каждого из выпуклых сегментов корпуса и возьмите минимум   -  person OMRY VOLK    schedule 06.12.2016
comment
@ user4421975 Не могли бы вы уточнить свой комментарий? В чем суть формулы сегмента?   -  person Woltan    schedule 06.12.2016
comment
для каждой точки вычислите расстояние до каждого линейного сегмента выпуклой оболочки, используя stackoverflow.com/questions/849211/ и выберите ближайшее   -  person OMRY VOLK    schedule 06.12.2016

Ответы (1)


arrow_upward
1
arrow_downward

если точки выпуклой оболочки заданы как массив 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)
person OMRY VOLK    schedule 06.12.2016
comment
Спасибо за ваш ответ. Возможно ли это преобразование в n-мерное пространство? Или хотя бы 3д? Я не упомянул об этом в своем вопросе и соответствующим образом отредактирую вопрос. - person Woltan; 06.12.2016
comment
Я уверен, что вы можете изменить формулу, чтобы она соответствовала 3D, если немного погуглите - person OMRY VOLK; 06.12.2016
comment
Вы можете переместить sqrt после min, чтобы уменьшить количество операций. - person Eran Yogev; 02.06.2021