Algoritmo de Cobertura de Vértice

1. Descrição do Algoritmo

Problema: Dado um conjunto S de pontos no plano, determinar P o fecho convexo de S

O objetivo é achar os pontos que formam o fecho convexo entre um conjunto de pontos aleatórios no plano 2D.

Proposta de Solução: Marcha de Jarvis (Gift Wrapping Wrapping)

1º Acha-se o 1˚ ponto = p1 (ponto com menor valor em Y e maior valor em X).
2  Faz ordenamento angular, usando pseudo-ângulo dos demais pontos em relação a p1
3º gira-se uma reta horizontal em p1 sentido contrário ao movimento dos ponteiros do relógio até achar p2
4º Calcula-se o pseudo ângulo de p1p2 em relação ao eixo X
5º Obtem-se o próximo ponto ordenado com menor ângulo (ex. p3), calculando-se o pseudo ângulo dos pontos ordenados e p1 em relação ao eixo X, subtraindo o valor do ângulo do ponto anterior e ignorando ângulos com valores negativos.
6º repete-se o processo até o próximo ponto ser p1

O fecho convexo pode ser definido como um polígono convexo que tem todos os seus vértices em S e contém todos os pontos de S em seu interior.

A ideia do algoritmo é adicionar um elemento de cada vez na solução e, não mais remover algum elemento dela. Neste problema, primeiramente descobrimos um primeiro vértice do polígono P.

Podemos usar o ponto mais a direita e abaixo (de maior coordenada x e menor coordenada y) e chamar este ponto de p1.

O problema de encontrar este ponto pode ser resolvido em tempo linear inspecionando todos os vértices e retornando o de maior coordenada x e menor coordenada y.

Geometricamente, podemos calcular o pseudo-ângulo de p2 medido no sentido anti-horário.
Para acharmos o próximo vértice, pegamos o ponto p3 ∈ S que minimiza  (p1, p2, p3) e assim por diante, até retornarmos ao ponto p1.

2. Implementação

os programas foram desenvolvidos na ferramenta QT Creator em C++, utilizando a biblioteca glut.lib e o framework Qt

// Ao clicar o mouse, o programa desenha um ponto na tela e acrecenta este
// ponto a uma lista e chama o método fecho para calcular e desenhar o fecho
// convexo

void Tela::mousePressEvent ( QMouseEvent * event )
{
Ponto P(event->x(),this->height - event->y(),this->counter);
this->Lista << P;
this->counter++;
this->fecho();
updateGL();
}

void Tela::drawHull()
{
    glColor3f(1,0,0);
    for(int i = 0; i < this->Fecho.size()-1; i++)
    {
        glBegin(GL_LINES);
        glVertex2f(Fecho[i]->coord.x, Fecho[i]->coord.y);
        glVertex2f(Fecho[i+1]->coord.x, Fecho[i+1]->coord.y);
        glEnd();
    }
}

void Tela::fecho()
{
    if(this->Lista.size() > 1)
    {
        this->Fecho.clear();
        float yMax = INFINITY;
        float anguloMax;
        Ponto *menorY, *ptCorrente, *ptAnterior;
        vec4 vCorrente = vec4(1.0,0.0,0.0,0.0);
        for(int i = 0; i < Lista.size(); i++)
        {
            if(this->Lista.at(i).coord.y < yMax)
            {
                yMax = this->Lista[i].coord.y;
                menorY = &(this->Lista[i]);
            }
        }
        this->Fecho << menorY;
        for(int i = 0; i < Lista.size(); i++)
        {
            if(&(this->Lista[i]) != menorY)
                this->Lista[i].d = dot(normalize(this->Lista[i].coord - menorY->coord),vCorrente);
            else
                this->Lista[i].d = -INFINITY;
        }
        anguloMax = -INFINITY;
        for(int i = 0; i < Lista.size(); i++)
        {
            if(this->Lista[i].d > anguloMax)
            {
                anguloMax = this->Lista[i].d;
                ptCorrente = &(this->Lista[i]);
            }
        }
        this->Fecho << ptCorrente;
        ptAnterior = menorY;
        while(menorY != ptCorrente)
        {
            vCorrente = normalize(ptCorrente->coord - ptAnterior->coord);
            ptAnterior = ptCorrente;
            for(int i = 0; i < Lista.size(); i++)
            {
                if(&(this->Lista[i]) != ptAnterior)
                    this->Lista[i].d = dot(normalize(this->Lista[i].coord - ptAnterior->coord),vCorrente);
                else
                    this->Lista[i].d = -INFINITY;
            }
            anguloMax = -INFINITY;
            for(int i = 0; i < Lista.size(); i++)
            {
                if(this->Lista[i].d > anguloMax)
                {
                    anguloMax = this->Lista[i].d;
                    ptCorrente = &(this->Lista[i]);
                }
            }
            this->Fecho << ptCorrente;
        }
        updateGL();
    }
}

3. Análise da Complexidade

Consumo de Tempo do Algoritmo:

1. Ordenação dos pontos: O (n lg n)

2. Encontrar o ponto de menor y e maior x: O(n)

2. Ligação dos pontos para formação do fecho:  O (nh), onde h é o número de pontos no fecho convexo

Cálculo da Complexidade: O (n lg n)