\documentclass[a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage[english]{babel}
\usepackage{graphicx}
\usepackage[colorlinks, urlcolor=blue]{hyperref}

\renewcommand{\familydefault}{\sfdefault}
\title{Relatório do trabalho 2 \\ Diagrama de Voronoi}
\author{João Paulo Pizani Flor \\ Mauricio Oliveira Haensch}
\date{\today}


\begin{document}
	
\maketitle
\thispagestyle{empty}
\pagebreak

\section{Introdução}
  \paragraph{}
  Para o segundo trabalho prático da disciplina era necessário a implementação de um algoritmo para construção do diagrama de Voronoi, para ser utilizado em um conjunto de pontos 2D, assim como nos casos específicos de espirais simples e duplas.

  \paragraph{}
  Para um conjunto A de \textbf{n} pontos dispostos em um espaço, chamados centróides, o diagrama de Voronoi é a segmentação desse espaço de forma com que cada um dos segmentos formados está associado a um dos centróides, representando a sub-área do espaço cuja distância até esse ponto é menor que a qualquer outro ponto do conjunto A. 

  \paragraph{}
  O algoritmo para geração do diagrama de Voronoi possui as seguintes etapas:

  \begin{itemize}
    \item Combinação de pontos do conjunto 3 a 3 para formação de circunferências, de modo com que nenhum outro ponto esteja dentro da circunferência;
    \item Geração de triângulos a partir dos pontos que formam as circunferências que satisfazem a condição anterior;
    \item Cálculo das mediatrizes de cada triângulo criado;
  \end{itemize}

  \begin{figure}[h!]
    \begin{center}
      \includegraphics[scale=0.5]{img/circunferencias.jpg} 
      \caption{Conjunto de pontos inicial e geração das circunferências.}
      \label{figure:circunferencias}
    \end{center}
  \end{figure}

  \begin{figure}[h!]
    \begin{center}
      \includegraphics[scale=0.5]{img/triangulos.jpg} 
      \caption{Formação dos triângulos a partir das circunferências válidas (com apenas 3 pontos).}
      \label{figure:triangulos}
    \end{center}
  \end{figure}

  \begin{figure}[h!]
    \begin{center}
      \includegraphics[scale=0.5]{img/mediatrizes.jpg} 
      \caption{Cálculo das mediatrizes e suas intersecções.}
      \label{figure:mediatrizes}
    \end{center}
  \end{figure}

  \paragraph{}
  A partir do conjunto de mediatrizes encontrados, são calculados seus pontos de intersecção de forma com que novos polígonos possam ser formados. Cada um dos polígonos é um segmento do diagrama de Voronoi associada ao seu centróide.

\pagebreak
\section{Ferramentas utilizadas}
  \paragraph{}
  A linguagem utilizada para implementação do programa era de livre escolha dos alunos, assim como outras ferramentas que pudessem ser utilizadas para representação gráfica dos padrões, por exemplo. As ferramentas escolhidas foram as mesmas utilizadas para a implementação do trabalho anterior:

  \begin{description}
    \item[Linguagem de programação - Python:] escolhida por ser uma linguagem já bem conhecida pela equipe, com boas bibliotecas e documentação, além de agilizar o desenvolvimento.
    \item[Interface gráfica - Qt + PyQt:] PyQt é um \textit{binding} do framework gráfico Qt para a linguagem Python, escolhida por já ser conhecida pelos integrantes.
    \item[NumPy:] Biblioteca da linguagem Python utilizada para computação científica, com diversas estruturas e funções otimizadas. Para este trabalho, utilizamos algumas de suas funções de álgebra linear, para fazer operações com matrizes. 
  \end{description}

  \paragraph{}
  O trabalho foi desenvolvido no ambiente Linux/Ubuntu e para executá-lo são necessários alguns pacotes\footnote{os nomes dos pacotes citados são específicos para a distribuição Ubuntu, para outras distribuições devem ser procurados os pacotes correspondentes.} para a interface gráfica:

  \begin{itemize}
    \item pyqt4-dev-tools
    \item libqtgui4
    \item libqtcore4
  \end{itemize}
  

\pagebreak
\section{Resultados}
   \paragraph{}
   A geração de um conjunto inicial de pontos de 2 dimensões e a geração de espirais simples e duplas foi mantida do trabalho anterior, assim como a maior parte da interface gráfica. Poucos ajustes nas funções já existentes foram realizados e adicionamos uma funcionalidade de adição de um ponto por clique na tela, facilitando a adição de um conjunto de pontos para teste.

 
   \paragraph{}
   Para desenvolver o algoritmo do diagrama de Voronoi, seguimos a etapa inicial com o cálculo das circunferências normalmente. São geradas combinações 3 a 3 dos pontos no conjunto de pontos inicial e é verificado se essa circunferência não possui nenhum outro ponto interno a ela, caso em que a circunferência é descartada. 


   \paragraph{}
   A partir do conjunto de circunferências válidas, são gerados triângulos formados pelos 3 pontos que
   descrevem a circunferência. Nesse ponto do nosso algoritmo, possuímos uma estrutura que guarda todos os
   conjuntos (centro, raio) que descrevem uma circunferência válida e uma outra estrutura que mapeia cada
   centróide (conjunto de pontos inicial) para os triângulos adjacentes a eles. Essas estruturas são usadas no
   passo posterior para gerar os polígonos do diagrama de Voronoi.


   \paragraph{}
   O algoritmo apresentado em sala realizava o cálculo das intersecções das medianas (reta perpendicular a um dos lados do triângulo, passando pelo ponto médio desse lado) para descobrir as bordas de cada polígono que definem uma célula do diagrama do Voronoi. Porém, vimos que esses pontos de intersecção são os circuncentros dos triângulos (ponto de encontro das 3 medianas), que é também o centro do círculo circunscrito ao triângulo.


   \paragraph{}
   Como já tínhamos os centros dos círculos armazenados, bastava que soubéssemos quais deles deveriam ser ligados para que fossem formadas as células, e por isso guardamos o mapa ligando cada centróide aos triângulos que o formam. Desse modo, para encontrar a célula de um centróide no diagrama de Voronoi, bastava ligar os circuncentros dos triângulos adjacentes a ele na ordem correta. Para encontrar essa ordem, utilizamos o algoritmo de fecho convexo de Graham\footnote{Dado um conjunto de pontos, o algoritmo de Graham deve encontrar o maior polígono fechado possível (fecho convexo). Esse algoritmo começa pelo ponto de menor coordenada Y e varre os outros pontos, ordenando-os de acordo com o ângulo formado entre eles a reta que passa pela coordenada X do ponto inicial, em sentido anti-horário.}.


   \paragraph{}
   Esse método resolve o problema para todos os centróides internos do conjunto de pontos inicial. Já para os pontos mais externos, é necessário encontrar as células abertas que definem o diagrama de Voronoi. Para isso, separamos o conjunto de pontos inicial em centróides internos e centróides externos, com a ajuda do algoritmo de Graham (executando o algoritmo no conjunto total de pontos, ele formará um polígono fechado com os pontos mais externos, então calculamos a diferença entre o conjunto inicial e o resultado da varredura do algoritmo para acharmos os pontos internos). Os pontos internos são tratados como explicado anteriormente enquanto aplicamos um tratamento especial aos pontos externos.


   \paragraph{}
   Para os pontos externos, ligamos os circuncentros dos triângulos adjacentes a 2 semi-retas formadas pelas
   medianas das bordas do polígono externo. O algoritmo de Graham é novamente utilizado nesse passo, para que
   seja estabelecida uma ordem na lista dos pontos obtidos, e possamos desenhar o polígono. Os segmentos de
   reta que se projetam ``para fora'' do diagrama de Voronoi são, obviamente, finitos. A ilusão de infinitude
   é obtida prolongando-se o segmento para coordenadas bem maiores do que as capazes de serem mostradas na
   interface gráfica.
   
   \paragraph{}
   A seguir, uma imagem com o resultado obtido pela aplicação do algoritmo de diagrama de Voronoi num conjunto arbitrário de pontos 2D.

%    \begin{figure}[h!]
     \begin{center}
	\includegraphics[scale=0.4]{img/voronoi.png}
	Diagrama de Voronoi sobre um conjunto arbitrário de pontos 2D. 
% 	\caption{Diagrama de Voronoi sobre um conjunto arbitrário de pontos 2D.}
% 	\label{figure:espiral}
     \end{center}
%    \end{figure}


   \paragraph{}
   Como casos especiais, as espirais simples e duplas deveriam ser testados com o algoritmo de diagrama de Voronoi implementado. Seguem abaixo 2 exemplos da aplicação do nosso algoritmo, considerando apenas as células fechadas (sem o cálculo das células externas).

%     \begin{figure}[h!]
      \begin{center}
	\includegraphics[scale=0.4]{img/espiral.png}
	Aplicação do algoritmo sobre uma espiral dupla, apenas com as células internas. 
% 	\caption{Aplicação do algoritmo sobre uma espiral dupla, apenas com as células internas.}
% 	\label{figure:espiral}
      \end{center}
%     \end{figure}

%     \begin{figure}[h!]
      \begin{center}
	\includegraphics[scale=0.4]{img/espiralDupla.png}
	Outro exemplo de espiral dupla, apenas com as células internas. 
% 	\caption{Outro exemplo de espiral dupla, apenas com as células internas.}
% 	\label{figure:espiral2}
      \end{center}
%     \end{figure}

%   \subsection{Geração de dados iniciais}
%     
% 
% 	  \paragraph{}
% 	  A seguir, exemplos da geração de dados de 2 dimensões. A primeira imagem mostra a geração de 20 pontos iniciais distribuídos aleatoriamente no espaço, cada um representando uma classe. 
% 
% 	  \begin{center}
% 		  \includegraphics[scale=0.4]{img/dados2Diniciais.png} 
% 		  Conjunto inicial de dados com 2D, formado por 20 pontos.
% 	  \end{center}
% 
% 
% 	  \paragraph{}
% 	  Implementamos também a geração de dados em espiral. A função de geração de espiral foi implementada em coordenadas polares, com um passo posterior de transformação para coordenadas cartesianas. Alguns parâmetros da espiral podem ser ajustados pelo usuário, como a distância entre 2 voltas sucessivas da espiral, o número de pontos e o nível de ruído. 
% 
% 
% 
% 	  \paragraph{}
% 	  Na geração de uma espiral com ruído, cada ponto sofre um deslocamento aleatório dentro de um quadrado cujo lado é determinado pelo nível de ruído, que varia de 0 a 2,5. A seguir, 2 imagens com nível crescente de ruído.
% 
% 	  \begin{center}
% 		  \includegraphics[scale=0.4]{img/espiralPoucoRuido.png} 
% 		  Espiral simples com um pouco de ruído.
% 	  \end{center}
% 
% 	  \begin{center}
% 		  \includegraphics[scale=0.4]{img/espiralMuitoRuido.png} 
% 		  Espiral simples com muito ruído.
% 	  \end{center}
% 
% 	  \paragraph{}
% 	  Outro requisito do trabalho era a geração de uma espiral dupla. Isos é feito através da geração de duas espirais simples, deslocando a posição inicial de uma delas em 180 graus com relação à outra, formando dois braços, cada um representando uma classe.
% 
% 	  \begin{center}
% 		\includegraphics[scale=0.4]{img/espiralDupla.png} 
% 		Espiral dupla.
% 	  \end{center}
% 
% 
%   \subsection{Classificação de novos pontos}
% 
%       \paragraph{}
%       A classificação de pontos deveria ser implementada seguindo o algoritmo kNearestNeighbour (incluindo o caso especial onde k=1) e utilizando 2 métricas de distância: distância euclidiana e distância de Manhattan. A primeira imagem demonstra a classificação de 500 pontos aleatórios sobre o conjunto de dados inicial de 2 dimensões já apresentado. Os novos padrões foram classificados com k=1 e utilizando a distância euclidiana.
% 
%       \begin{center}
% 	  \includegraphics[scale=0.4]{img/dados2D500pontos.png} 
% 	  500 pontos classificados por Nearest Neighbour com distância Euclidiana.
%       \end{center}
% 
%       \paragraph{}
%       Além da geração aleatório, é possível que o usuário determine um ponto arbitrário a ser classificado. A imagem a seguir mostra essa possibilidade, no caso o ponto central da área de desenho (coordenadas x=50 e y=50), também classificado com o mesmo algoritmo e métrica que o caso anterior.
% 
%       \begin{center}
% 	  \includegraphics[scale=0.4]{img/dados2DpontoCentral.png} 
% 	  Classificação de um ponto escolhido pelo usuário, através de Nearest Neighbour com distância Euclidiana.
%       \end{center}
% 
%       \paragraph{}
%       A seguir, duas imagens de espirais duplas. Na primeira figura foram adicionados 3000 pontos aleatórios, classificados pelo algoritmo \textit{kNearestNeighbour} com k=2 e utilizando a \textit{distância de Manhattan}. A segunda figura demonstra uma espiral após a adição de um grande número de pontos, quase totalizando a área disponível da interface, mostrando as regiões cobertas por cada classe da espiral dupla.
% 
%       \begin{center}
% 	  \includegraphics[scale=0.4]{img/espiralDupla3000pontos.png} 
% 	  Espiral dupla com 3000 pontos aleatórios (kNearestNeighour com k=2 e distância de Manhattan)
%       \end{center}
% 
% 
%       \begin{center}
% 	  \includegraphics[scale=0.4]{img/espiralComMuitosPontos.png} 
% 	  Espiral dupla com trocentos pontos.
%       \end{center}

  
\section{Referências}

  \begin{itemize}
	  \item Python -	\url{http://www.python.org/}
	  \item Qt - \url{http://doc.qt.nokia.com/}
	  \item pyQt - \url{http://www.riverbankcomputing.co.uk/software/pyqt/intro}
  \end{itemize}

\end{document}
