점 집합으로부터 볼록 레이어를 생성하기위한 효율적인 알고리즘

Question

저는 파이썬에서 볼록 레이어를 생성하려고 시도하고있는 포인트 목록을 가지고 있습니다.

현재 단순히 다음 사용하고 있습니다 : 볼록은 한 번에 하나의 선체 만들 그냥

def convex_layers(points): 
    points = sorted(set(points)) 
    layers = [] 
    while points: 
     #Create the next convex hull 
     hull = convex_hull(points) 

     #Create the new list of points 
     for point in hull: 
     points.remove(point) 

     #Update the list of layers 
     layers.append(hull) 
    return layers 

합니다. 작동하는 동안 반복되는 추가로 간단히 번식하려고하는 것처럼 보입니다. 그래서 내가 바라는 점은 점 집합에서 볼록 레이어를 생성하기위한보다 효율적인 알고리즘이있는 경우입니다.

Answer 1

monotone chain algorithm을 사용하는 경우 사전 식 정렬을 한 번만 수행해야합니다. 그러면 각각의 연속적인 계층은 O (n) 시간에 발견 될 수 있습니다. 이것은 각 레이어를 정렬하는 것보다 빠릅니다.

Answer 2

scipy spatial.convexHull으로 시도 할 수 있습니다.

또는 code on GitHub 게시했습니다.