/***************************************************************/
/* Contour tracking program                                    */
/* The file contains three subroutines:                        */
/*      1. NextCheckPoint  find the next point on the contour  */
/*      2. OneTraceBWImg  find a contour in B&W image          */
/*      3. TraceAllCnt  find all contours in the B&W image     */
/*                                                             */
/* Author: ZUO Zhengrong                                       */
/* Date  : 21/05/2001                                          */
/***************************************************************/

#include "stdlib.h"
#include "math.h"

#define ONE    255
#define ZERO   0
#define MID    128
#define MAXLEN 1024

#ifndef _COORDINATE_
#define _COORDINATE_
typedef struct
{
  short   x;
  short   y;
}COORDINATE;
#endif

void OneTraceBWImg(unsigned char **SegImg, int Row, int Col, int StartX, int StartY,
	int *CntX, int *CntY, int *CntPointNum);
int NextCheckPoint(int Row, int Col, int SearchDirection, int CurrentX, int CurrentY, int * NextX, int * NextY);
void TraceAllCnt(unsigned char **SegImg, int Row, int Col);

/*  Find all contours in B&W image                                         */
/*                                                                         */
void TraceAllCnt(unsigned char **SegImg, int Row, int Col)
{
   int StartX, StartY;
   int i,j;
   unsigned char *pSegImg;      /* the pointer to the image array */
   int CntX[MAXLEN],CntY[MAXLEN];  /* the array to store X-Y coordinate of the contour */
   int CntPointNum;               

   for(i=0; i<Row; i++)
   for(j=0; j<Col; j++)
   {
      if(j)
	if(SegImg[i][j]==ONE && SegImg[i][j-1]==ZERO) 
	{
	  StartX = i;
	  StartY = j;
	  OneTraceBWImg(SegImg,Row,Col,StartX,StartY,CntX,CntY,&CntPointNum);
	}
      else
	if(SegImg[i][j]==ONE) 
	{
	  StartX = i;
	  StartY = j;
	  OneTraceBWImg(SegImg,Row,Col,StartX,StartY,CntX,CntY,&CntPointNum);
	}
   }
   return ;
 
}

void OneTraceBWImg(unsigned char **SegImg, int Row, int Col, int StartX, int StartY,
	int *CntX, int *CntY, int *CntPointNum)
{
   static int CheckPointX;
   static int CheckPointY;
   static int i,j;
   static int NextPointX, NextPointY;
   static int SearchDirection,NextDirection;           /* search direction  */
   static int First;
   static int Found;
   static int changedirect;
   static int HasNextPoint;

   CheckPointX = StartX;
   CheckPointY = StartY;
   *CntPointNum = 0;

   CntX[*CntPointNum] = CheckPointX;
   CntY[*CntPointNum] = CheckPointY;
   *CntPointNum++;


   SearchDirection = 6;
   First = 1;

   while (StartX != CheckPointX || StartY != CheckPointY || First == 1)
   {
      Found = 0;
      changedirect = 0;
      while (Found ==0 )
      {
	  NextDirection = SearchDirection-1;
	  if(NextDirection<0) NextDirection += 8;
	  HasNextPoint = NextCheckPoint(Row, Col,NextDirection, CheckPointX, CheckPointY, &NextPointX, &NextPointY);    
	  if(HasNextPoint && SegImg[NextPointY][NextPointX]==ONE)
	  {
	     CheckPointX = NextPointX;
	     CheckPointY = NextPointY;
	     SegImg[CheckPointX][CheckPointY] = MID;
	     CntX[*CntPointNum] = CheckPointX;
	     CntY[*CntPointNum] = CheckPointY;
	     *CntPointNum++;
	     changedirect=0;
	     SearchDirection = SearchDirection-2;
	     if(SearchDirection<0) SearchDirection += 8;
	     Found = 1;
	     goto end;
	  }

	  HasNextPoint = NextCheckPoint(Row, Col, SearchDirection, CheckPointX, CheckPointY, &NextPointX, &NextPointY); 
	  if(HasNextPoint && SegImg[NextPointY][NextPointX]==ONE)
	  {
	     CheckPointX = NextPointX;
	     CheckPointY = NextPointY;
	     SegImg[CheckPointX][CheckPointY] = MID;
	     CntX[*CntPointNum] = CheckPointX;
	     CntY[*CntPointNum] = CheckPointY;
	     *CntPointNum++;
	     changedirect=0;
	     Found = 1;
	     goto end;
	  }

	  NextDirection = SearchDirection+1;
	  if(NextDirection>7) NextDirection -= 8;
	  HasNextPoint = NextCheckPoint(Row, Col, NextDirection, CheckPointX, CheckPointY, &NextPointX, &NextPointY);   
	  if(HasNextPoint && SegImg[NextPointY][NextPointX]==ONE)
	  {
	     CheckPointX = NextPointX;
	     CheckPointY = NextPointY;
	     SegImg[CheckPointX][CheckPointY] = MID;
	     CntX[*CntPointNum] = CheckPointX;
	     CntY[*CntPointNum] = CheckPointY;
	     *CntPointNum++;
	     changedirect=0;
	     Found = 1;
	     goto end;
	  }

	  changedirect++;
	  if(changedirect>4) break;
end:      if(!Found)
	  SearchDirection = SearchDirection+2; 
	  if(SearchDirection>7) SearchDirection -= 8;
      }
      First = 0;
   }
}


int NextCheckPoint(int Row, int Col, int SearchDirection, int CurrentX, int CurrentY, int * NextX, int * NextY)
{
    switch (SearchDirection)
    {
	case 0:
	    *NextX = CurrentX + 1;
	    *NextY = CurrentY;
	    if(*NextX>=Col) return 0;
	    break;
	case 1:
	    *NextX = CurrentX + 1;
	    *NextY = CurrentY - 1;
	    if(*NextX>=Col || *NextY<0) return 0;
	    break;
	case 2:
	    *NextX = CurrentX;
	    *NextY = CurrentY - 1;
	    if(*NextY<0) return 0;
	    break;
	case 3:
	    *NextX = CurrentX - 1;
	    *NextY = CurrentY - 1;
	    if(*NextX < 0 || *NextY<0) return 0;
	    break;
	case 4:
	    *NextX = CurrentX - 1;
	    *NextY = CurrentY;
	    if(*NextX<0) return 0;
	    break;
	case 5:
	    *NextX = CurrentX - 1;
	    *NextY = CurrentY + 1;
	    if(*NextX<0 || *NextY>=Row) return 0;
	    break;
	case 6:
	    *NextX = CurrentX;
	    *NextY = CurrentY + 1;
	    if(*NextY>=Row) return 0;
	    break;
	case 7:
	    *NextX = CurrentX + 1;
	    *NextY = CurrentY + 1;
	    if(*NextX>=Col || *NextY>=Row) return 0;
	    break;
	}
	return 1;
}