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

from matplotlib import pyplot as plt # библиотека для графиков
from random import randint # для сортировки и создания точек данных
from math import atan2 # для вычисления полярного угла
 
# Возвращаем список (x, y) координат длины 'num_points',
# каждая координата x и y выбирается случайным образом из диапазона
# от 'min' до 'max'. 
def create_points(ct,min=0,max=25):
    return [[randint(min,max),randint(min,max)] \
                    for _ in range(ct)]
 
# Создает диаграмму рассеяния, ввод - это список координат (x, y).
# Второй вход 'convx_hull' - это еще один список координат (x, y),
# состоящий из тех точек в координатах, которые составляют выпуклую оболочку,
# если не None, элементы этого списка будут использоваться для рисования внешнего
# граница (выпуклая оболочка, окружающая точки данных)
def scatter_plot(coords,convex_hull=None):
    xs,ys=zip(*coords) # распаковать в списки координат x и y 
    plt.scatter(xs,ys) # построить точки данных 
 
    if convex_hull!=None:
        # построить границу выпуклой оболочки, дополнительная итерация на
        # конец так, чтобы ограничивающая линия обтекала 
        for i in range(1,len(convex_hull)+1):
            if i==len(convex_hull): i=0 # обертка
            c0=convex_hull[i-1]
            c1=convex_hull[i]
            plt.plot((c0[0],c1[0]),(c0[1],c1[1]),'r')
    plt.show()
scatter_plot(create_points(10))
 
# Возвращает полярный угол (радианы) от p0 до p1.
# Если p1 равен None, по умолчанию он заменяется на
# глобальная переменная anchor, обычно устанавливается в
# функция 'graham_scan'.
def polar_angle(p0,p1=None):
    if p1==None: p1=anchor
    y_span=p0[1]-p1[1]
    x_span=p0[0]-p1[0]
    return atan2(y_span,x_span)
 
# Возвращает евклидово расстояние от p0 до p1,
# квадратный корень не применяется ради скорости.
# Если p1 равен None, по умолчанию он заменяется на
# глобальная переменная anchor, обычно устанавливается в
# функция 'graham_scan'.
def distance(p0,p1=None):
    if p1==None: p1=anchor
    y_span=p0[1]-p1[1]
    x_span=p0[0]-p1[0]
    return y_span**2 + x_span**2
 
# Возвращает определитель матрицы 3x3 ...
# [p1 (x) p1 (y) 1]
# [p2 (x) p2 (y) 1]
# [p3 (x) p3 (y) 1]
# Если> 0, то против часовой стрелки
# Если <0, то по часовой стрелке
# Если = 0, то коллинеарно 
def det(p1,p2,p3):
    return   (p2[0]-p1[0])*(p3[1]-p1[1]) \
            -(p2[1]-p1[1])*(p3[0]-p1[0])
 
# Сортировка по возрастанию полярного угла от точки привязки.
# Предполагается, что переменная 'anchor' является глобальной, устанавливается внутри 'graham_scan'.
# Для любых значений с равными полярными углами применяется вторая сортировка.
# обеспечить увеличение расстояния от точки «якоря». 
def quicksort(a):
    if len(a)<=1: return a
    smaller,equal,larger=[],[],[]
    piv_ang=polar_angle(a[randint(0,len(a)-1)]) # выбрать случайную точку поворота
    for pt in a:
        pt_ang=polar_angle(pt) # вычислить текущий угол точки
        if   pt_ang<piv_ang:  smaller.append(pt)
        elif pt_ang==piv_ang: equal.append(pt)
        else:        larger.append(pt)
    return   quicksort(smaller) \
            +sorted(equal,key=distance) \
            +quicksort(larger)
 
# Возвращает вершины, составляющие границы
# выпуклой оболочки, содержащие все точки входного множества.
# Входные "точки" - это список координат (x, y).
# Если 'show_progress' установлен в True, прогресс в
# Построение корпуса будет строиться на каждой итерации. 
def graham_scan(points,show_progress=True):
    global anchor # устанавливается, (x, y) с наименьшим значением y 
    
# Найдите точку (x, y) с наименьшим значением y,
# вместе с его индексом в списке "точек". Если
# есть несколько точек с одинаковым значением y,
# выбираем тот, у которого наименьший x. 
    min_idx=None
    for i,(x,y) in enumerate(points):
        if min_idx==None or y<points[min_idx][1]:
            min_idx=i
        if y==points[min_idx][1] and x<points[min_idx][0]:
            min_idx=i
# установить глобальную переменную 'anchor', используемую
# функции 'polar_angle' и 'distance' 
    anchor=points[min_idx]
# сортируем точки по полярному углу, затем удаляем
# якорь из отсортированного списка 
    sorted_pts=quicksort(points)
    del sorted_pts[sorted_pts.index(anchor)]
    
    # якорь и точка с наименьшим полярным углом всегда будут на корпусе 
    hull=[anchor,sorted_pts[0]]
    for s in sorted_pts[1:]:
            while det(hull[-2],hull[-1],s)<=0:
                del hull[-1] # возврат 
                #if len (hull) <2: break 
            hull.append(s)
            if show_progress: scatter_plot(points,hull)
    return hull
 
pts = create_points(10)
print ("Points:", pts)
hull = graham_scan(pts, True)
print ("Hull:", hull)
scatter_plot(pts, hull)