Question

Como encontrar o fecho convexo (convex hull) de um conjunto de pontos?

Answer 1

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).

Comments

Muito legal!

Answer 2

Uma implementação usando força bruta:

import numpy as np
import matplotlib.pyplot as plt
np.random.seed(100)
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])

def convex_hull(vector):
    n=np.shape(vector)[0]
    convexHull=[]
    for i in range(n-1):
        for j in range(i+1,n):
#            a=vector[i,1]-vector[j,1]
#            b=vector[i,0]-vector[j,0]
#            c=vector[i,0]*vector[j,1]-vector[j,0]*vector[i,1]
            a=(vector[i,1]-vector[j,1])/(vector[i,0]-vector[j,0])
            b=vector[i,1]-a*vector[i,0]
            lineIsConvexHull=True
            first=True
            k=0
            while((lineIsConvexHull)and(k<n)):
                if((k!=i)and(k!=j)):
                    if(first):
                        #signTest=np.sign(a*vector[k,0]+b*vector[k,1]-c)
                        signTest=np.sign(vector[k,1]-a*vector[k,0]-b)
                        first=False
                        #print signTest
                    else:
                        #sign=np.sign(a*vector[k,0]+b*vector[k,1]-c)
                        sign=np.sign(vector[k,1]-a*vector[k,0]-b)
                        if(sign*signTest<0):
                            lineIsConvexHull=False
                            #print sign
                k=k+1            
            if(lineIsConvexHull):                
                convexHull.append([vector[i,:],vector[j,:]])

    return convexHull

if __name__ == '__main__':

    n=10
    vector=np.random.uniform(size=[n,2])    
    convexHull=convex_hull(vector)
    plt.plot(vector[:,0],vector[:,1],'b.',markersize=20)
    k=len(convexHull)
    for i in range(k):
        plt.plot([convexHull[i][0][0],convexHull[i][1][0]],[convexHull[i][0][1],convexHull[i][1][1]],'r',markersize=20)        
#    plt.plot([point1[0],point2[0]],[point1[1],point2[1]],'r',markersize=20)
    plt.savefig('convexHull.eps')

A idéia é bem simples... Os seguimentos que estão no fecho são aqueles cujos pontos do polígono ficam sempre a esquerda ou a direita deles (dos seguimentos).