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)