Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

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

0 votos
313 visitas
perguntada Abr 7, 2016 em Ciência da Computação por danielcajueiro (5,726 pontos)  
Compartilhe

2 Respostas

+1 voto
respondida Abr 12, 2016 por PRosa (61 pontos)  
editado Abr 12, 2016 por PRosa

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:
A imagem será apresentada aqui.

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

A imagem será apresentada aqui.

A imagem será apresentada aqui.

comentou Abr 13, 2016 por danielcajueiro (5,726 pontos)  
Muito legal!
0 votos
respondida Abr 7, 2016 por danielcajueiro (5,726 pontos)  

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

convex hull

...