Outra alternativa de implementação, também utilizando força bruta, faz uso do coeficiente angular entre os pontos para desenhar o fecho convexo, tendo como ponto inicial o ponto "mais ao Norte" (maior y):
import numpy as np
import matplotlib.pyplot as plt
import math
def fecho_convexo(vet):
n=np.shape(vet)[0]
fecho=[]
# Ponto inicial: maior Y
maiorY,ind=0,0
for i in range(1,n):
if (vet[i,1] > maiorY):
maiorY,ind=vet[i,1],i
fecho.append(vet[ind])
# Busca pontos do fecho nos 4 "quadrantes"
for i in range(4+1):
fecho=PontosDoFecho(i,fecho,vet)
return fecho
def PontosDoFecho(direcao,fecho,vet):
ABAIXO_DIREITA,ABAIXO_ESQUERDA,ACIMA_ESQUERDA,ACIMA_DIREITA=1,2,3,4
n=np.shape(vet)[0]
lAchouPto=True
while(lAchouPto):
maiorBeta=-50000
ptoAtual = fecho[len(fecho)-1]
lAchouPto=False
for i in range(n):
if (direcao==ABAIXO_DIREITA and vet[i,1] < ptoAtual[1] and vet[i,0] > ptoAtual[0]) or \
(direcao==ABAIXO_ESQUERDA and vet[i,1] < ptoAtual[1] and vet[i,0] < ptoAtual[0]) or \
(direcao==ACIMA_ESQUERDA and vet[i,1] > ptoAtual[1] and vet[i,0] < ptoAtual[0]) or \
(direcao==ACIMA_DIREITA and vet[i,1] > ptoAtual[1] and vet[i,0] > ptoAtual[0]):
beta=(vet[i,1]-ptoAtual[1]) / (vet[i,0]-ptoAtual[0])
if (beta > maiorBeta):
maiorBeta,ind=beta,i
lAchouPto=True
if (lAchouPto):
fecho.append(vet[ind])
return fecho
if __name__ == '__main__':
np.random.seed(100)
vector=np.random.uniform(size=[1000,2])
convexHull=fecho_convexo(vector)
fig=plt.figure(num=None, figsize=(8, 8), dpi=80, facecolor='w', edgecolor='k')
plt.hold(True)
epsilon=0.1
plt.axis([0-epsilon, 1+epsilon, 0-epsilon, 1+epsilon])
plt.plot(vector[:,0],vector[:,1],'b+',markersize=10)
k=len(convexHull)
for i in range(k):
if (i==k-1):
j=0
else:
j=i+1
plt.plot([convexHull[i][0],convexHull[j][0]],[convexHull[i][1],convexHull[j][1]],'r',markersize=10)
Fecho para 1000 pontos:

Fiz uma comparação entre os custos de processamento de 3 algoritmos: implementação da resposta 1 (convex-hull); implementação em wikibooks (convex-hull-2) e a implementação acima (fecho-convexo).

