/* MAC5749 	Analise de Formas e Classificacao */
/* EP2  	Algoritmo de Rotulacao de Componentes Conexas */
/* Entrega: 	11/09/2003 */
/* Aluno: 	Robson Ribeiro Correia */

/* Funcoes: 

EncontraComponentesConexas (matriz, linhas, colunas);
RotulaVizinhanca4 (matriz, linha, coluna, rotulo);
RotulaVizinhanca8 (matriz, linha, coluna, rotulo);

*/

#include <stdio.h>

#define LIN 255
#define COL 255

#define PRETO '1' 		/* no formato pbm */
#define BRANCO '0'		/* no formato pbm */
#define MAXGRAY 255		/* no formato pgm */

#define EOL '\n'
#define BLANK ' '

int pixels[LIN][COL];			/* matriz para manipular os pixels da figura */

main()
{
   extern int pixels[LIN][COL];	/* para armazenar os pixels do pbm */

   int letter;					/* para ler caracteres do arquivo */
   
   char linha1[COL];			/* para ler as 3 primeiras linhas */
   char linha2[COL];			/* do arquivo pbm */
   char linha3[COL];

   int i, j, k;					/* contadores */

   FILE *fopen(), *fpbm, *fpgm; /* para ler os arquivos "pbm" e "pgm" */	

   /* Gambiarra para escrever o rotulo no formato apropriado pgm */
   int decimal;    				/* rotulo, a ser convertido de decimal para caracteres */
   char ascii;    				/* caracter para receber a conversao */
   char string[COL];	   		/* string para receber a conversao */
   int dezenas;					/* quantidade de dezenas que um no. vai ter */

   /* abre o arquivo pbm para leitura */
   if ((fpbm = fopen("squares.pbm", "r")) == NULL)
      {
	printf("Erro abrindo o arquivo leitura\n");
	exit(1);
      }

   /* abre o arquivo pgm para escrita */
   if ((fpgm = fopen("squares.pgm", "w")) == NULL)
      {
	printf("Erro abrindoo arquivo de escrita\n");
	exit(1);
      }

   /* le as 3 primeiras linhas do arquivo pbm */
   fgets(linha1, COL, fpbm);
   fgets(linha2, COL, fpbm);
   fgets(linha3, COL, fpbm);


   /* armazena os pixels lidos do arquivo na matriz pixels */
   for(i=0; i < LIN; i++)
      {
      for(j=0; j <= COL; j++)
         {
            pixels[i][j] = getc(fpbm);
            letter = getc(fpbm);		/* le o espaco em branco */
         }
      letter = getc(fpbm);				/* le o final da linha */
      }

   /* procura as componentes conexas na matriz pixels */
   EncontraComponentesConexas(pixels, LIN+1, COL);
   
   /* armazena as seguintes linhas no arquivo pgm */
   fputs("P2\n", fpgm);
   fputs("# Biblioteca de Imagens de Robson Correia (c)2003\n", fpgm);
   fputs("255 256 256\n", fpgm);

   /* escreve os pixels no arquivo pgm */
   for(i=0; i < LIN; i++)
      {
      for(j=0; j <= COL; j++)
         {
         if (pixels[i][j] != BRANCO)
            {
            dezenas = 0;
            decimal = pixels[i][j];
            while (decimal > 0)
               {
               ascii = (decimal % 10) + 48;
               string[dezenas] = ascii;
               string[++dezenas] = NULL;
               decimal /=  10;
               }

            for(k= dezenas-1; k >= 0; k--)
               {
               putc(string[k], fpgm);
               }

            putc(BLANK, fpgm);
            
            }
         else
            {
            putc(BLANK, fpgm);
	    putc(BLANK, fpgm);
            putc(pixels[i][j], fpgm);
            putc(BLANK, fpgm);
            }
         }
      putc(EOL, fpgm);
      }
   putc(EOF, fpgm);

   /* fecha os arquivos */
   fclose(fpbm);
   fclose(fpgm);
}


EncontraComponentesConexas(matriz, linhas, colunas)

/* A implementacao do algoritmo de rotulacao de componentes conexas 
 * propriamente dito.
 */

/* Entrada:
 *	- matriz: 	uma matriz de pixels no formato pbm, ou seja, 0s e 1s
 *	- linhas: 	no. de linhas da matriz
 *	- colunas: 	no. de colunas da matriz
 */

/* Saida:
 *	- matriz: 	a mesma matriz de entrada, agora no formato pgm, 
 *			ou seja, os valores dos pixels vao de 0 a 256. Porem
 *			esses valores nao indicam niveis de cinza, mas
 *			componentes conexas. Cada componente terah o mesmo
 *			rotulo, comecando por 256 e decrescendo ate 2.
 */

int matriz[LIN][COL];
int linhas, colunas;

{
   /* declaracao de variaveis */
   int i, j;			/* contadores */
   int rotulo;			/* contador para o rotulo */

   rotulo = MAXGRAY;
   
   for(i=0; i < linhas; i++)
      for(j=0; j < colunas; j++)
            if (matriz[i][j] == PRETO)
            {
               /* rotula o pixel encontrado */
               matriz[i][j] = rotulo;

               /* rotula a vizinhanca, e na verdade toda a componente */
               RotulaVizinhanca8(matriz, i, j, rotulo);
               
               /* decrementa o rotulo */
               if (rotulo > 2) 
                  rotulo--;
               else
                  {
                  printf("Sua figura tem mais que 255 componentes conexas!\n");
                  break;
                  }
            }
}


RotulaVizinhanca8(matriz, linha, coluna, rotulo)

/* Procedimento auxiliar para a rotulacao da componente conexa.
 * Eh chamado recursivamente para cada pixel vizinhho que tenha valor 1,
 * ou seja, que nao tenha valor 0, ou que ainda nao tenha sido rotulado.
 * Soh deve terminar sua execucao depois que tiver rotulado toda a componente
 * conexa. Entao retorna para a funcao chamadora (EncontraComponenteConexa),
 * de onde continuarah a procura por novas componentes.
 */

int matriz[LIN][COL];
int linha, coluna, rotulo;

{
   /* Verifica V0 */
   if ((matriz[linha][coluna+1] == PRETO) && (coluna+1 <= COL))
      {
         matriz[linha][coluna+1] = rotulo;
         RotulaVizinhanca8(matriz, linha, coluna+1, rotulo);
      }
   
   /* Verifica V1 */
   if ((matriz[linha-1][coluna+1] == PRETO) && (linha-1 >= 0) && (coluna+1 <= COL))
      {
         matriz[linha-1][coluna+1] = rotulo;
         RotulaVizinhanca8(matriz, linha-1, coluna+1, rotulo);
      }

   /* Verifica V2 */
   if ((matriz[linha-1][coluna] == PRETO) && (linha-1 >= 0))
      {
         matriz[linha-1][coluna] = rotulo;
         RotulaVizinhanca8(matriz, linha-1, coluna, rotulo);
      }

   /* Verifica V3 */
   if ((matriz[linha-1][coluna-1] == PRETO) && (linha-1 >= 0) && ((coluna-1) >= 0))
      {
         matriz[linha-1][coluna-1] = rotulo;
         RotulaVizinhanca8(matriz, linha-1, coluna-1, rotulo);
      }

   /* Verifica V4 */
   if ((matriz[linha][coluna-1] == PRETO) && (coluna-1 >= 0))
      {
         matriz[linha][coluna-1] = rotulo;
         RotulaVizinhanca8(matriz, linha, coluna-1, rotulo);
      }

   /* Verifica V5 */
   if ((matriz[linha+1][coluna-1] == PRETO) && (linha+1 <= LIN) && (coluna-1 >= 0))
      {
         matriz[linha+1][coluna-1] = rotulo;
         RotulaVizinhanca8(matriz, linha+1, coluna-1, rotulo);
      }

   /* Verifica V6 */
   if ((matriz[linha+1][coluna] == PRETO) && (linha+1 <= LIN))
      {
         matriz[linha+1][coluna] = rotulo;
         RotulaVizinhanca8(matriz, linha+1, coluna, rotulo);
      }

   /* Verifica V7 */
   if ((matriz[linha+1][coluna+1] == PRETO) && (linha+1 <= LIN) && (coluna+1 <= COL))
      {
         matriz[linha+1][coluna+1] = rotulo;
         RotulaVizinhanca8(matriz, linha+1, coluna+1, rotulo);
      }
}

RotulaVizinhanca4(matriz, linha, coluna, rotulo)

/* Procedimento auxiliar para a rotulacao da componente conexa.
 * Eh chamado recursivamente para cada pixel vizinhho que tenha valor 1,
 * ou seja, que nao tenha valor 0, ou que ainda nao tenha sido rotulado.
 * Soh deve terminar sua execucao depois que tiver rotulado toda a componente
 * conexa. Entao retorna para a funcao chamadora (EncontraComponenteConexa),
 * de onde continuarah a procura por novas componentes.
 */

int matriz[LIN][COL];
int linha, coluna, rotulo;

{
   /* Verifica V0 */
   if ((matriz[linha][coluna+1] == PRETO) && (coluna+1 <= COL))
      {
         matriz[linha][coluna+1] = rotulo;
         RotulaVizinhanca8(matriz, linha, coluna+1, rotulo);
      }
   

   /* Verifica V1 */
   if ((matriz[linha-1][coluna] == PRETO) && (linha-1 >= 0))
      {
         matriz[linha-1][coluna] = rotulo;
         RotulaVizinhanca8(matriz, linha-1, coluna, rotulo);
      }

   /* Verifica V2 */
   if ((matriz[linha][coluna-1] == PRETO) && (coluna-1 >= 0))
      {
         matriz[linha][coluna-1] = rotulo;
         RotulaVizinhanca8(matriz, linha, coluna-1, rotulo);
      }

   /* Verifica V3 */
   if ((matriz[linha+1][coluna] == PRETO) && (linha+1 <= LIN))
      {
         matriz[linha+1][coluna] = rotulo;
         RotulaVizinhanca8(matriz, linha+1, coluna, rotulo);
      }
}