Algoritmo de Fecho Convexo 2D

1. Descrição do Problema

        Dado um conjunto de pontos, computar seu fecho convexo: Polígono é definido normalmente por uma circulação de vértices. Vértices são pontos extremos. Ângulos internos estritamente convexos (< π).  Se 3 pontos na fronteira do polígono são colineares, o ponto do meio não é considerado.           

Fecho convexo de P: conjunto de combinações convexas de pontos de P, ou seja,

Problema: Dada uma coleção P de pontos do plano, determinar o fecho convexo de P.

Ponto (x, y) de P é extremo se não é combinação convexa de pontos de P \ {(x, y)}.

Pontos extremos de conv(P) são pontos extremos de P.

Representação do fecho convexo: vetor H[1 . . h] com índices dos pontos extremos na ordem em que aparecem na fronteira do fecho convexo (sentido anti-horário).

2. Pseudo-codigo

Os pontos de índice 2, 4, 5, 7 e 8 são extremos.

Algoritmo de Grahan

Este algoritmo é considerado o primeiro algoritmo de Geometria Computacional (1972).

Ideia: primeiro fazemos uma “ordenação angular” dos pontos em torno do ponto de menor Y-coordenada. Garantimos que o ponto de menor coordenada Y e maior coordenada X pertencerá ao fecho convexo e selecionamos este ponto como ponto inicial do fecho.

Cada ponto considerado tem que estar à esquerda da aresta anteriormente computada do fecho convexo (teste de orientação)

O produto vetorial formado pelo ponto i(1) e os i(2) e i(3) ( próximos pontos) ordenados deverá ser positivo quando o ponto (i+1) estiver a esquerda de i (vetor saindo do plano para cima) e negativo quando o ponto (i+1) estiver a direita de i (vetor saindo do plano para baixo). 

Neste caso o ponto (i+1) não pertence ao fecho convexo e deverá ser removido. O próximo ponto deve ser adicionado e um novo cálculo do produto vetorial deve ser feito entre estes três pontos (ex. i(1), i(3), i(4)). O processo se repete até que o primeiro ponto seja novamente alcançado. (ex. i(n-2), i(n-1), i(n)) onde i(n) = i(1).

Cada ponto selecionado a seguir deverá ter o menor ângulo em relação ao ponto anterior

3. Implementação

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

void TelaGL::graham()
{
    Ponto aux;
    QList<Ponto> fecho;
    fecho = L;
    fecho << L[0];
    int i = 0;
    // o laço percorre os pontos do vetor L de 0 até n-2 pontos
    // onde n é o tamanho do vetor.
    while(i < fecho.size()-2)
    {
        // calculo do produto vetorial entre a aresta do ponto (i+1,i+2) e
        // a aresta do ponto (i+1,i) 
        aux = util::cross(fecho[i+2]-fecho[i+1], fecho[i]-fecho[i+1]);
        // se o produto vetorial resultar em um número negativo, então o ponto 
        // i+1 é removido do vetor L 
        if(aux.z < 0)
        {
            fecho.removeAt(i+1);
            if(i!=0) i--;
            continue;
        }
        i++;
    }
    glColor3f(0,0,1);
    glBegin(GL_LINE_LOOP);
        for(int k=0; k<fecho.size(); k++)
        {
            glVertex2f(fecho[k].x, fecho[k].y);
        }
    glEnd();
    glColor3f(0,0,0);
}

Ponto util::cross(Ponto A, Ponto B)
{
    Ponto C;
    C.x = A.y*B.z - A.z*B.y;
    C.y = A.z*B.x - A.x*B.z;
    C.z = A.x*B.y - A.y*B.x;
    return C;
}

void TelaGL::paintGL()
{
    glClear(GL_COLOR_BUFFER_BIT);
    drawSinglePoints();
    PseudoAngulo::center = *menorPonto;
    PseudoAngulo::drawSquare(LADO,0);
    char s[10];
    for(int i=0; i<L.size(); i++)
    {
        L[i].d = PseudoAngulo::calcPseudoAngle(L[i],origem);
        menorPonto->d = 0;
        glRasterPos2f(L.at(i).x, L.at(i).y+0.04);
        sprintf(s,"%.4g", L.at(i).d);
        util::drawString(s,2);
    }
    int menorId = menorPonto->id;
    Sorter::sort(L);
    for(int i=0; i<L.size(); i++)
    {
        if(L[i].id == menorId)
        {
            menorPonto = &(L[i]);
        }
    }
    for(int i=0; i<L.size(); i++)
    {
        glRasterPos2f(L.at(i).x+0.025, L.at(i).y-0.02);
        L[i].id = i;
        sprintf(s,"%d", L[i].id);
        util::drawString(s,1);
    }
    graham();
}

4. Análise da Complexidade

• Achar o ponto mínimo: O(n)
• Ordena-Pontos(X,Y,n) : O(n lg n)
• Colocar e remover cada ponto
• Cada ponto entra no fecho convexo 1 vez
• Cada ponto pode sair do fecho convexo, no máximo,  1 vez
• Teste de todos os pontos: O(n)

 Conclusão: Varredura é O(n lg n)