/*+-------------------------------------------------------------------------+
  | MORFOLOGIA MATEMATICA:                                                  |
  | ----------------------                                                  |
  |                                                                         |
  | UTILS.H                                                                 |
  |                                                                         |
  |     Arquivo que contem algumas rotinas uteis para implementacao dos pro-|
  | gramas de morfologia matematica.                                        |
  |                                                                         |
  | Por Luiz Eduardo da Silva                                    JANEIRO/97 |
  +-------------------------------------------------------------------------+*/


/*+-------------------------------------------------------------------------+
  | Estrutura para implementacao de fila encadeada.                         |
  +-------------------------------------------------------------------------+*/
struct no {
  int i, j;
  struct no *next;
};

/*+-------------------------------------------------------------------------+
  | Adiciona um pixel na fila de pixel's. Esta rotina possibilita a varredu-|
  | ra dos pixel's vizinhos de uma regiao em ordem LARGURA-PRIMEIRO.        |
  +-------------------------------------------------------------------------+*/
void insere_fila (struct no **COM, struct no **FIM, int i, int j) {
    struct no *aux;
    aux = malloc (sizeof (struct no));
    aux->i = i;
    aux->j = j;
    aux->next = NULL;
    if (*FIM) (*FIM)->next = aux;
    (*FIM) = aux;
    if (!(*COM)) (*COM) = aux;
}

/*+-------------------------------------------------------------------------+
  | Retira um pixel na fila de pixeis.                                      |
  +-------------------------------------------------------------------------+*/
void retira_fila (struct no **COM, struct no **FIM, int *i, int *j) {
    struct no *aux;
    aux = (*COM);
    *i = aux->i;
    *j = aux->j;
    (*COM) = aux->next;
    free (aux);
    if (!(*COM)) (*FIM) = NULL;
}

/*+-------------------------------------------------------------------------+
  | Retorna se a fila esta vazia ou nao.                                    |
  +-------------------------------------------------------------------------+*/
int fila_vazia (struct no *COM) {
    return (COM == NULL);
}

/*+-------------------------------------------------------------------------+
  | Rotina de depuracao responsavel pela apresentacao da fila.              |
  +-------------------------------------------------------------------------+*/
void mostra_fila (struct no *COM) {
    struct no *aux;
    aux = COM;
    printf ("\nFILA: ");
    while (aux) {
	printf ("(%d,%d) ",aux->i, aux->j);
	aux = aux->next;
    }
    printf ("\n\n");
    return;
}

/*+-------------------------------------------------------------------------+
  | Funcao que retorna a coordenada do vizinho de um ponto.                 |
  |                    3 2 1                            1                   |
  |   Vizinhanca 8:    4 . 0          Vizinhanca 4:   2 . 0                 |
  |                    5 6 7                            3                   |
  +-------------------------------------------------------------------------+*/
int Viz (int v, int n, int i, int j, int nl, int nc, int *ip, int *jp) {
    if (v == 4) n = 2 * n;
    switch (n) {
    case 0: if (j+1<nc) {*ip = i; *jp = j+1; return TRUE;} break;
    case 1: if (i-1>=0 && j+1<nc) {*ip = i-1; *jp = j+1; return TRUE;} break;
    case 2: if (i-1>=0) {*ip = i-1; *jp = j; return TRUE;} break;
    case 3: if (i-1>=0 && j-1>=0) {*ip = i-1; *jp = j-1; return TRUE;} break;
    case 4: if (j-1>=0) {*ip = i; *jp = j-1; return TRUE;} break;
    case 5: if (i+1<nl && j-1>=0) {*ip = i+1; *jp = j-1; return TRUE;} break;
    case 6: if (i+1<nl) {*ip = i+1; *jp = j; return TRUE;} break;
    case 7: if (i+1<nl && j+1<nc) {*ip = i+1; *jp = j+1; return TRUE;} break;
    }
    return FALSE;
}

/*+-------------------------------------------------------------------------+
  | Rotina que retorna o "valor" do vizinho de um ponto (x,y) numa certa di-|
  | recao (dir).                                                            |
  |                              3 2 1                                      |
  |                    Direcoes  4 . 0                                      |
  |                              5 6 7                                      |
  +-------------------------------------------------------------------------+*/
int p (int *I, int nc, int i, int j, int dir) {
   switch (dir) {
   case 0: return *(I+i*nc+j+1);
   case 1: return *(I+(i-1)*nc+j+1);
   case 2: return *(I+(i-1)*nc+j);
   case 3: return *(I+(i-1)*nc+j-1);
   case 4: return *(I+i*nc+j-1);
   case 5: return *(I+(i+1)*nc+j-1);
   case 6: return *(I+(i+1)*nc+j);
   case 7: return *(I+(i+1)*nc+j+1);
   }
}

/*+-------------------------------------------------------------------------+
  | Rotina utilizada na DEPURACAO.                                          |
  | Converte o valor do pixel por um valor entre 0 e 255, equivalente ao que|
  | faz o programa xv.                                                      |
  +-------------------------------------------------------------------------+*/
int c (int v, int mn) {
    return (int) v * 255 / mn;
}

/*+-------------------------------------------------------------------------+
  | Calcula o numero de conexidade de Yokoi (para vizinhanca-8)             |
  |       0 = ponto interno                  3 = ponto de bifurcacao (T)    |
  |       1 = ponto de borda                 4 = ponto de cruzamento (+)    |
  |       2 = ponto de conexao (-)                                          |
  |                             v3  v2  v1                                  |
  |                             v4  .   v0                                  |
  |                             v5  v6  v7                                  |
  +-------------------------------------------------------------------------+*/
int ABS (int i) {
  if (i < 0) return -i; else return i;
}

int yokoi (int *I, int nl, int nc, int y, int x, int mostra_calc){
  int yok, i, parcela, v[8];
  v[0] = 1 - ABS (*(I+y*nc+x+1));
  v[1] = 1 - ABS (*(I+(y-1)*nc+x+1));
  v[2] = 1 - ABS (*(I+(y-1)*nc+x));
  v[3] = 1 - ABS (*(I+(y-1)*nc+x-1));
  v[4] = 1 - ABS (*(I+y*nc+x-1));
  v[5] = 1 - ABS (*(I+(y+1)*nc+x-1));
  v[6] = 1 - ABS (*(I+(y+1)*nc+x));
  v[7] = 1 - ABS (*(I+(y+1)*nc+x+1));
  yok = 0;
  for (i = 0; i < 8; i+=2) {   
      parcela = ABS (v[i] - v[i]*v[(i+1)%8]*v[(i+2)%8]);
      yok = yok + parcela;
      if (mostra_calc)
         printf ("\nABS (%d - %d*%d*%d) = %d", 
                      v[i], v[i], v[(i+1)%8], v[(i+2)%8], parcela);
  }
  return yok;
}

/*+-------------------------------------------------------------------------+
  | Calcula o numero de conexidade de Rutovitz                              |
  |       0 = ponto interno                  3 = ponto de bifurcacao (T)    |
  |       1 = ponto de borda                 4 = ponto de cruzamento (+)    |
  |       2 = ponto de conexao (-)                                          |
  |                             v3  v2  v1                                  |
  |                             v4  .   v0                                  |
  |                             v5  v6  v7                                  |
  +-------------------------------------------------------------------------+*/
int rut (int *I, int nl, int nc, int y, int x){
  int r, i, v[8];
  v[0] = ABS (*(I+y*nc+x+1));
  v[1] = ABS (*(I+(y-1)*nc+x+1));
  v[2] = ABS (*(I+(y-1)*nc+x));
  v[3] = ABS (*(I+(y-1)*nc+x-1));
  v[4] = ABS (*(I+y*nc+x-1));
  v[5] = ABS (*(I+(y+1)*nc+x-1));
  v[6] = ABS (*(I+(y+1)*nc+x));
  v[7] = ABS (*(I+(y+1)*nc+x+1));
  r = 0;
  for (i = 0; i < 8; i++)
      r = r + ABS (v[i] - v[(i+1)%8]);
  return (int) r / 2;
}

/*+-------------------------------------------------------------------------+
  | Funcao que retorna o numero de componentes conexos formados pelos vizi- |
  | nhos de um determinado ponto.                                           |
  | Parametros:                                                             |
  | viz = o vetor dos pontos vizinhos de um ponto, cada elemento deste ve-  |
  |       tor contem 1 se satisfaz a um determinado criterio (ser estrita-  |
  |       mente maior, maior-igual, estritamente menor ou menor-igua ao     |
  |       ponto central), e contem 0 se NAO satisfaz ao criterio.           |
  | n =   vizinhanca 4 ou 8. Esta vizinhanca e' utilizado para adjacencia   |
  |       do ponto central e para verificar se dois vizinhos estao conecta- |
  |       dos ou nao. Entao n = 4 representa que queremos o numero de com-  |
  |       ponentes conexos formado pelos 4-vizinhos de um ponto que estao 4 |
  |       conectados.                                                       |
  | Vizinhanca Considerada:                                                 |
  |                           3   2   1                                     |
  |                           4       0                                     |
  |                           5   6   7                                     |
  +-------------------------------------------------------------------------+*/
int ObtemNumComp (int *viz, int n) {
    int i, j, k, e, conta=0;

    /*--- OBS: Para n = 4 considerar apenas as duas primeiras ---*/
    /*--- colunas da tabela abaixo, o valor 8 representa uma  ---*/
    /*--- posicao nao utilizada da tabela.                    ---*/
    int conect[8][4]=
    {{1,7,2,6},  /* O ponto 0 e' vizinho dos pontos 1,7,2,6 */
     {0,2,8,8},  /* O ponto 1 e' vizinho dos pontos 0,2     */
     {1,3,0,4},  /* O ponto 2 e' vizinho dos pontos 1,3,0,4 */
     {2,4,8,8},  /* O ponto 3 e' vizinho dos pontos 2,4     */
     {3,5,2,6},  /* O ponto 4 e' vizinho dos pontos 3,5,2,6 */
     {4,6,8,8},  /* O ponto 5 e' vizinho dos pontos 4,6     */
     {5,7,4,0},  /* O ponto 6 e' vizinho dos pontos 5,7,4,0 */
     {6,0,8,8}   /* O ponto 7 e' vizinho dos pontos 6,0     */
    };
    
    int fila[]={0,0,0,0,0,0,0,0};
    
    for (i=0; i<8 && !viz[i]; i+=(8/n));
    if (i >= 8) return 0;

    viz[i]=0;
    fila[i]=1;
    while(1){
	for(k=0; k<8 && !fila[k]; k++);
	if(k>=8) {
	    conta++;
	    for (;i<8 && !viz[i]; i+=(8/n));
	    if(i>=8) return conta;
            viz[i]=0;
	    fila[i]=1;
	}
	else{
	    fila[k] = 0;
	    for(j=0;j<n/2;j++){
		e=conect[k][j];
		if(e < 8 && !fila[e] && viz[e]){
		    viz[e]=0;
		    fila[e]=1;
		}
	    }
	}
    }  	  
} 

/*+-------------------------------------------------------------------------+
  | Funcao que verifica se um ponto na imagem WSHED e' simples. Um ponto nu-|
  | ma imagem binaria e' simples se o numero de componentes conexos da forma|
  | e' "1" e o numero de componentes conexos do fundo tambem e' "1".        |
  +-------------------------------------------------------------------------+*/
int ponto_simples (int *W, int i, int j, int nl, int nc) {
    int x, v[8], Cforma[8], Cfundo[8], NCforma, NCfundo;
    v[0] = *(W+i*nc+j+1);
    v[1] = *(W+(i-1)*nc+j+1);
    v[2] = *(W+(i-1)*nc+j);
    v[3] = *(W+(i-1)*nc+j-1);
    v[4] = *(W+i*nc+j-1);
    v[5] = *(W+(i+1)*nc+j-1);
    v[6] = *(W+(i+1)*nc+j);
    v[7] = *(W+(i+1)*nc+j+1);
    for (x = 0; x < 8; x++) {
	Cforma[x] = v[x] == 1;
	Cfundo[x] = v[x] == 0;
    }
    NCforma = ObtemNumComp(Cforma,8);
    NCfundo = ObtemNumComp(Cfundo,4);
    if (NCforma == 1 && NCfundo == 1) return 1;
    return 0;
}