Diagrama de Voronoi - Algoritmo de Linha de Varredura

Algoritmo de Linha de Varredura

Dado um conjunto de p1,...,pn de pontos no plano, queremos construir um diagrama de Voronoi varrendo uma uma linha horizontal entre os pontos, mantendo o que foi visto ao longo do caminho. 

Para isso, precisamos usar uma estratégia adicional envolvendo parábolas. Parábolas são úteis para este problema de linha de varredura porque para qualquer ponto pi, há uma parábola separando pi da linha de varredura de tal maneira que cada ponto da parábola é eqüidistante tanto de p quanto da linha de varredura. Assim, quando a linha de varredura atinge um novo ponto de pj, sabemos, com base na parábola associada com cada ponto, qual é o ponto médio entre pi e pj.

O algoritmo irá varrer uma linha horizontal de baixo para cima, criando uma parábola para cada ponto, tal que para cada posição da linha de varredura, cada ponto é o foco de sua parábola e a diretriz da parábola é a própria linha de varredura. A parábola se torna mais aberta a medida que a linha de varredura avança para o topo do plano

Figura 1 

Em qualquer fase do processo, o algoritmo assemelha-se o que vemos na Figura 2.

Figura 2

Acima da a linha de varredura está um conjunto de sites não visitados, e todos os sites abaixo da linha de varredura já foram visitados pelo algoritmo. Os arcos mais próximos da  linha de varredura criar uma "fronteira de onda" (wavefront),  bloqueando a vista de outros arcos. Os pontos na "fronteira da onda" onde os arcos se encontram são chamados de pontos de interrupção, e note que cada ponto de interrupção é equidistante de seus correspondentes locais. Cada ponto já ultrapassado pela "fonteira da onda" é conhecido por pertencer a uma região específica de Voronoi.

Considere as seguintes observações:

1. Com o avanço da linha de varredura, um novo arco (de alguma parábola) é adicionado para a "fronteira da onda" somente quando a linha de varredura toca algum site. Isto é chamado de evento de site.
2.  A única maneira que um arco desaparecer a partir da frente de onda é quando dois arcos adjacentes de cruzam em um ponto comum. Chamamos a isto um evento de círculo

Estrutura de Dados

Como estamos interessados em ambos eventos de site e de círculo, vamos usar duas

estruturas de dados para armazenar as informações recuperadas durante todo o processo. 

A primeira estrutura de dados será uma árvore binária balanceada T usado para armazenar a "fronteira da onda". As folhas da árvore serão os arcos que compõem a "fronteira da onda" e os nós internos de T serão os pontos de interrupção (interseções de arcos).

Precisamos ser capazes de realizar as seguintes operações em T:

1. Inserções: quando um novo arco for adicionado na "fronteira da onda"
2. Deleções: quando um arco tornar-se invisível para a linha de varredura e não fizer mais parte da "fronteira da onda"
3. Busca: Para qualquer linha vertical que quisermos saber qual arco cruza.

A segunda estrutura de dados que queremos usar é uma fila de prioridade Q para armazenar os eventos encontrados. As operações que nós gostaríamos de usar são os seguintes:

1. Inserção: para incluir novos eventos quando ocorrerem no processo
2. Deleção: depois de processar o evento, ele não mais é necessário e deve ser excluído
3. Sucessor: após processar um evento, devemos processar o evento seguinte na fila baseado na posição do ponto na coordenada Y

Complexidade

No pior caso, existem 2n -1 arcos na "fronteira de onda" ao mesmo tempo. Isto ocorre quando cada arco está sobre a "fronteira de onda", mas um é dividido por outro arco da "fronteira de onda"). Então a árvore balanceada contém O(n) elementos. Como cada operação que queremos realizar em T leva não mais que tempo O (log n) e não há mais que n elementos na árvore, cada operação realizada na estrutura de dados do status da "fronteira de onda" é limitada a tempo O (log n).

Notamos que os eventos de círculo só podem ocorrer com três arcos consecutivos. Assim, em uma fila no máximo n sites lá nunca irá ocorrer mais do que n-2 eventos de círculo. Mais uma vez nossa fila tem n elementos, e assim cada uma das operações leva não mais que

tempo O(log n).

Porque há um número constante de eventos de site em Q e cada operação leva uma quantidade constante de tempo, vemos que o algoritmo de varredura de linha para determinar o diagrama de Voronoi em um conjunto de n pontos é executado em tempo de O (n log n).

Pseudo-código

Entrada: um conjunto P = (p1,p2,...pn) pontos no plano
Saida: O Diagrama de Voronoi Vor(P)

1. Inicialize uma fila de prioridade Q com eventos de site ordenados em ordem crescente pela coordenada x; inicialize uma estrutura de árvore balanceada vazia T 

2. Enquanto Q não estiver vazia

    (a) capture o próximo evento q fora de Q de menor coordenada Y
    (b) se q é um evento de site X:
          i. Se T estiver vazio, insira q em T e retorne, senão faça os passos ii a iv
          ii. Encontre o arco B que cruza a parábola X criada pela "fronteira de onda" e o site x

         iii. Insira uma nova parábola em T e divida a parábola (B) que está cortada em duas partes. Reequilibre T se necessário

         iv. Atualize Q pela deleção do evento de círculo que já não é alcançavel baseado no corte da "fronteira de onda" (ABC) e pela inserção dos três novos eventos de círculos possíveis criados pelo novo evento de site (A-B1-X, B1-X-B2, X-B2-C)

   (b) se q é um evento de círculo (x:ABxDE -> ABDE):
        i. Grave o Vértice de Voronoi
       ii. Delete o arco que desapareceu de T
      iii. Atualize Q devido a deleção de 3 novos eventos de círculos impossíveis (A-B-x, B-x-D, x-D-E) e insira os dois novos eventos de círculo possíveis A-B-D, B-D-E).

Diagrama de Voronoi

O Diagrama de Voronoi foi inventado para resolver um problema simples: Como dividir uma cidade em áreas irregulares de forma a que a área coberta por um carteiro vinculado a uma determinada agência de correio seja otimizada?

G. F. Voronoi, em sua tese de doutorado entitulada Sobre uma generalização do algoritmo de quebra de cadeias publicada em Varsóvia, Polônia, em 1896, desenvolveu um método onde, com base em uma triangulação pré-existente de pontos que representam os centros de alguma coisa (no caso da primeira aplicação, agências de correio), se determina qual a área de influência de cada um destes centros em função da posição dos outros centros, delimitando de forma geométrica cada área de influência.

O diagrama de Voronoi é um  método que muito útil para reconhecimento de padrões para delimitar as áreas de categorias ou classes em uma representação geométrica de suas distribuições.

Os “centros” são denominados de centróides. Se existe um conjunto de padrões constituído de um elemento típico para cada categoria que queremos representar (protótipo), pode-se  utilizar o diagrama de Voronoi para determinar a extensão de cada uma das categorias, apenas utilizando cada um dos protótipos como um centróide e gerando um diagrama de Voronoi sobre estes.

Para podermos gerar um diagrama de Voronoi partimos do conjunto de protótipos e geramos primeiramente uma triangulação. Para isto utilizamos o método da Triangulação de Delaunay, que veremos em detalhe adiante. Na figura 1, a triangulação está em vermelho.

Figura 1 - Triangulação de Delaunay

Realizada a triangulação, geramos as linhas que formarão as fronteiras das células do diagrama de Voronoi. Estas fronteiras são geradas por linhas perpendiculares ao ponto médio de cada aresta da triangulação produzida anteriormente. As intersecções destas perpendiculares formam os vértices das células do diagrama de Voronoi. Os segmentos de reta da perpendicular que se estendem para além de sua primeira intersecção com outra perpendicular nos dois sentidos são descartados.

Estruturas Geométricas:

Região de Voronoi 

• Vor(p)
• Coleção de pontos bidimensionais, onde todos os pontos estão mais perto do vértice p do que de qualquer outro vértice no grafo. 
• Diagrama de Voronoi é a união de todas as regiões de Voronoi do grafo
• Triangulação de Delaunay está relacionada com Diagrama de Voronoi
• Dois vértices p e q estão conectados em Del(V) apenas se Vor(p) e Vor(q) compartilham uma mesma borda

Triangulação de Delaunay

• Del(V)
• Assume que nenhum 4 vértices são co-circulares 
• Triangulação é de Delaunay se o circulo circunscrito de cada um de seus triângulos não contém outro vértice em seu interior

Passo-a-passo para criação do Diagrama de Voronoi.

Passo 1: Determinação dos pontos para os triângulos (Triangulação de Delaunay) 

Tome sua distribuição de dados e encontre todos os triângulos definidos por três pontos da distribuição, de tal forma que um círculo passando por estes três pontos não inclua nenhum outro ponto.

 Passo 1

Passo 2: Determinação dos triangulos (Triangulação de Delaunay)

Para cada conjunto de três pontos satisfazendo a condição de Delaunay encontrado, gere um triângulo.

Passo 2

Passo 3: Determinação das células (Diagrama de Voronoi)

P.3.1. Determine o ponto médio de cada uma das arestas do conjunto de triângulos gerado anteriormente. Considere cada aresta apenas uma vez.
P.3.2. Gere uma linha perpendicular a cada uma das arestas.
P.3.3. Determine as duas intersecções mais próximas de cada aresta com duas outras arestas. Um intersecção para cada lado. Ignore os segmentos de reta que seguem para além das intersecções.
P.3.4. Forme as células do diagrama com os polígonos formados por segmentos adjacentes. Ciclos geram células internas, polígonos abertos células externas.

Passo 3

Apresentação do Algoritmo MergeSort

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)

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)

Algoritmo de Ordenação

1. Descrição do Algoritmo

Seja um conjunto de n pontos gerados de forma aleatória no plano. Para cada ponto deseja-se executar uma varredura angular, no sentido anti-horário, visitando todos os outros n–1 pontos do conjunto.

Para cada ponto é possível determinar os ângulos entre esse ponto e todos os demais n–1 pontos e ordenar os ângulos. Neste exemplo será usado o algoritmo de MergeSort (ordenação por intercalação). Esse algoritmo usa um dos paradigmas fundamentais de construção de algoritmos: a obtenção da solução de um problema através da combinação das soluções de problemas de tamanho menor.

O algoritmo de ordenação utiliza o cálculo do pseudo-ângulo em quadrado unitário para ordenar os pontos no plano 2D.

Passos do Algoritmo:

1.  Escolher um número n de pontos

2. Definir uma Região 2 D com dimensões definidas (w e h)

3. Gerar n números aleatórios dentro do intervalo de (w,h) 4. Pesquisar o menor ponto y 

5. Este ponto será o centro de um quadrado 2 X 2 

6. Lançar raios e medir pseudo-ângulo 

7. No caso de pontos colineares, ordenar por ordem euclidiana 

8. Medir tempo de execução e uso de cpu dos algoritmos 


2. Pseudo-código

Cálculo do Pseudo-Ângulo:

ALGORITMO Pseudo-Angulo(x=x1,y=x2):
if y ≥ 0
   if x ≥ 0
      if x ≥ y
         return y/x
      return 2 – x/y
   if -x ≤ y
       return 2 + (-x)/y
   return 4 – y/(-x)
if x < 0
   if -x ≥ -y
       return 4 + (-y)/(-x)
   return 6 - (-x)/(-y)
if x ≤ -y
   return 6 + x/(-y)
return 8 - (-y)/x


3. Implementação

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

Programa Principal:
Main.cpp
======
#include "mainwindow.h"
#include <GL/glut.h>
#include <QApplication>

int main(int argc, char *argv[])
{
    QApplication a(argc, argv);
    glutInit(&argc, argv);
    MainWindow w;
    w.show();
    return a.exec();
}

Programa Ponto.cpp
===============

#include "ponto.h"

int Ponto::idGen = 0;

Ponto::Ponto(float x, float y, float z)
{
    this->x = x;
    this->y = y;
    this->z = z;
    this->d = 0;
    this->id = idGen++;
}

Ponto::Ponto(float x, float y)
{
    this->x = x;
    this->y = y;
    this->z = 0;
    this->d = 0;
    this->id = idGen++;
}

Ponto::Ponto()
{
    this->x = 0;
    this->y = 0;
    this->z = 0;
    this->d = 0;
}

void Ponto::setId(float id)
{
    this->id = id;
}

Programa de Cálculo do Pseudo-ângulo

Pseudoangulo.cpp

============

#include "pseudoangulo.h"

Ponto PseudoAngulo::center;

float PseudoAngulo::calcPseudoAngle(Ponto p, Ponto origem)

{

    if(p.y - origem.y  >= center.y + origem.y)

    {

        if(p.x - origem.x >= center.x - origem.x)

        {

            if(fabs(p.x - center.x) >= fabs(p.y - center.y))

            {

                return fabs(p.y - center.y)/fabs(p.x - center.x); //1º octante

            }

            return 2 - fabs(p.x - center.x)/fabs(p.y - center.y); //2º octante

        }

        if( fabs(p.x - center.x) <= fabs(p.y - center.y) )

        {

            return 2 + fabs(p.x - center.x)/fabs(p.y - center.y); //3º octante

        }

        return 4 - fabs(p.y - center.y)/fabs(p.x - center.x);     //4º octante

    }

}

void PseudoAngulo::drawSquare(float lado)

{

    glLineWidth(1.5);

    glColor3f(0,0,0);

    glBegin(GL_LINE_LOOP);

        glVertex2f( center.x - lado , center.y - lado );

        glVertex2f( center.x + lado , center.y - lado );

        glVertex2f( center.x + lado , center.y + lado );

        glVertex2f( center.x - lado , center.y + lado );

    glEnd();

    glBegin(GL_LINES);

        glVertex2f( center.x , center.y - 2*lado );

        glVertex2f( center.x , center.y + 2*lado );

        glVertex2f( center.x - 2*lado , center.y );

        glVertex2f( center.x + 2*lado , center.y );

    glEnd();

    glLineWidth(1);

}

Programa de Cálculo de Ordenação dos Pontos utilizando MergeSort

Sorter.cpp

=======

#include "sorter.h"

clock_t Sorter::tInicio;

clock_t Sorter::tFim;

double Sorter::tDecorrido;

int Sorter::trocas;

int Sorter::comparacoes;

Sorter::Sorter()

{

}

void Sorter::sort(QList<Ponto> &L)

{

    tDecorrido = 0;

    trocas = 0;

    comparacoes = 0;

    mergeSort(L,0,L.size()-1);

}

void Sorter::merge(QList<Ponto> &L, int p, int q, int r)

{

    int n1 = q - p + 1;

    int n2 = r - q;

    QList<Ponto> left;

    QList<Ponto> right;

    for(int i = 0; i < n1; i++)

        left << L.at(p + i);

    for(int j = 0; j < n2; j++)

        right << L.at(q + j + 1);

    Ponto pleft = Ponto();

    Ponto pright = Ponto();

    pleft.d = INFINITY;

    pright.d = INFINITY;

    left << pleft;

    right << pright;

    int i = 0;

    int j = 0;

    for(int k = p; k <= r; k++ )

    {

        comparacoes++;

        if(left.at(i).d < right.at(j).d)

        {

            L.replace(k, left.at(i));

            i++;

            trocas++;

        }

        else

        {

            L.replace(k, right.at(j));

            j++;

            trocas++;

        }

    }

}

void Sorter::mergeSort(QList<Ponto> &L, int p, int r)

{

    tInicio = clock();

    if(p < r)

    {

        int q = (int) (p+r)/2;

        mergeSort(L,p,q);

        mergeSort(L,q+1,r);

        merge(L,p,q,r);

    }

    tFim = clock();

    tDecorrido = (double) (tFim - tInicio) / (CLOCKS_PER_SEC);

}

4. Análise da Complexidade

Criar os pontos aleatórios e achar o ponto mínimo: O(n)

Ordenar os pontos: O(n log n)

Calcular e imprimir o pseudo ângulo O(n-1)

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

Apresentação do Blog

Portfólio de Programas de Geometria Computacional

Aluno: Eliseu Castelo Branco Júnior

Disciplina: Geometria Computacional

Professor: Creto Vidal

Este blog apresenta implementações de algoritmos de Geometria Computacional

1. Algoritmo de Ordenação

2. Algoritmo de Cobertura de Vértice
3. Algoritmo de MergeSort

4. Algoritmo de Fecho Convexo 2D (Graham)
5. Algoritmo de Voronoi
6. Algoritmo de Triangulação de Delaunay