// 座標のクリッピング
// http://fussy.web.fc2.com/algo/algo1-2.htmより

/* 端点分類コード */
enum Edge {
  LEFT 		= BIT0,
  RIGHT 	= BIT1,
  TOP 		= BIT2,
  BOTTOM 	= BIT3,
};

static int min_x,min_y;
static int max_x,max_y;

void setClippingArea(int sx,int sy,int ex,int ey)
/* クリッピングエリア設定 */
{
	min_x=sx;
	min_y=sy;
	max_x=ex;
	max_y=ey;
}

/*
  calc_seq_code : 端点分類コードを求める

  Coord c : 座標値

  戻り値 : 端点分類コード
*/
static
int calc_seq_code( int x,int y )
{
	int code = 0;
	if( x < min_x ) code += LEFT;
	if( x > max_x ) code += RIGHT;
	if( y < min_y ) code += TOP;
	if( y > max_y ) code += BOTTOM;

	return( code );
}

/*
  calc_midP : 中点分割法による交点の算出メインルーチン

  int a0, int b0, int a1, int b1 : 線分の座標
  int clip_a : クリッピングする座標

  クリッピング対象は bの方になる。

  戻り値 : クリッピング結果
*/
static
int calc_midP( int a0, int b0, int a1, int b1, int clip_a )
{
	/* もう一方の端点がウィンドウの辺上にある場合の対処 */
	if ( a0 == clip_a ) return( b0 );
	if ( a1 == clip_a ) return( b1 );

	/*
	線分の始点と終点を求める
	(必ず sa < ea となるようにする)
	*/
	int sa, sb, ea, eb;
	if ( a0 < a1 ) {
		sa = a0, sb = b0;
		ea = a1, eb = b1;
	} else {
		sa = a1, sb = b1;
		ea = a0, eb = b0;
	}

	int ca, cb;
	do {
		ca = ( sa + ea ) >> 1;
		cb = ( sb + eb ) >> 1;
		if ( ca < clip_a ) {
			sa = ca;
			sb = cb;
		} else {
			ea = ca;
			eb = cb;
		}
	} while ( ca != clip_a );

	return( cb );
}

/*
  calc_midP_x : 中点分割法による交点の算出(左右の辺)

  int sx,int sy, c1 : クリッピング前の線分座標
  int clip_x : 左(または右)の辺のX座標
  int *x,int *y : クリッピング後の座標

  戻り値 : クリッピング成功 >0 , 線分は完全に不可視 =0
*/
static
BOOL calc_midP_x( int sx,int sy, int ex,int ey, int clip_x, int *x,int *y )
{
	int cy = calc_midP( sx, sy, ex, ey, clip_x );

	/* エリア外の場合はFalseを返す */
	if ( ( cy < min_y ) || ( cy > max_y ) ) return( NO );

	*x = clip_x;
	*y = cy;

	return( YES );
}

/*
  calc_midP_y : 中点分割法による交点の算出(上下の辺)

  int sx,int sy, c1 : クリッピング前の線分座標
  int clip_y : 上(または下)の辺のY座標
  int *x,int *y : クリッピング後の座標

  戻り値 : クリッピング成功 >0 , 線分は完全に不可視 =0
*/
static
BOOL calc_midP_y( int sx,int sy, int ex,int ey, int clip_y, int *x,int *y )
{
	int cx = calc_midP( sy, sx, ey, ex, clip_y );

	/* エリア外の場合はFalseを返す */
	if ( ( cx < min_x ) || ( cx > max_x ) ) return( NO );

	*x = cx;
	*y = clip_y;

	return( YES );
}

/*
  calc_intsec_x : 数学的手法による交点の算出(左右の辺)

  int sx,int sy, c1 : クリッピング前の線分座標
  int clip_x : 左(または右)の辺のX座標
  int *x,int *y : クリッピング後の座標

  戻り値 : クリッピング成功 >0 , 線分は完全に不可視 =0
*/
static
BOOL calc_intsec_x( int sx,int sy, int ex,int ey, int clip_x, int *x,int *y )
{
	int cy = ( ey - sy ) * ( clip_x - sx ) / ( ex - sx ) + sy;

	/* エリア外の場合はFalseを返す */
	if ( ( cy < min_y ) || ( cy > max_y ) ) return( NO );

	*x = clip_x;
	*y = cy;

	return( YES );
}

/*
  calc_intsec_y : 数学的手法による交点の算出(上下の辺)

  int sx,int sy, c1 : クリッピング前の線分座標
  int clip_y : 上(または下)の辺のY座標
  int *x,int *y : クリッピング後の座標

  戻り値 : クリッピング成功 >0 , 線分は完全に不可視 =0
*/
static
BOOL calc_intsec_y( int sx,int sy, int ex,int ey ,int clip_y, int *x,int *y)
{
	int cx = ( ex - sx ) * ( clip_y - sy ) / ( ey - sy ) + sx;

	/* エリア外の場合はFalseを返す */
	if ( ( cx < min_x ) || ( cx > max_x ) ) return( NO );

	*x = cx;
	*y = clip_y;

	return( YES );
}

/*
  クリッピング後の座標を求める
  int code    : 端点分類コード
  sx,sy,ex,ey : 線分の座標
  *x,*y       : クリッピング後の座標

  戻り値 : クリッピング成功 >0 , 線分は完全に不可視 =0
*/
static
BOOL calc_clipped_point( int code, int sx,int sy, int ex,int ey, int *x,int *y)
{
	/* ウィンドウの左端より外側にある */
	if ( ( code & LEFT ) != 0 ) {
		if ( calc_intsec_x( sx,sy, ex,ey, min_x, x,y ) )	return( YES );
	}
	/* ウィンドウの右端より外側にある */
	if ( ( code & RIGHT ) != 0 ){
		if ( calc_intsec_x( sx,sy, ex,ey, max_x, x,y ) )    return( YES );
	}
	/* ウィンドウの上端より外側にある */
	if ( ( code & TOP ) != 0){
		if ( calc_intsec_y( sx,sy, ex,ey, min_y, x,y ) )    return( YES );
	}
	/* ウィンドウの下端より外側にある */
	if ( ( code & BOTTOM ) != 0 ){
		if ( calc_intsec_y( sx,sy, ex,ey, max_y, x,y ) )    return( YES );
	}
	return( NO );  /* クリッピングされなかった場合、線分は完全に不可視 */
}

/*
  クリッピングメインルーチン
  sx,sy : 始点の座標
  ex,ey : 終点の座標

  戻り値 :
   >0 ... クリッピングされた
   0  ... クリッピングの必要なし
   <0 ... 線分は完全に不可視
*/
int clipping( int *sx,int *sy,int *ex,int *ey)
{
	int code0, code1; /* 端点分類コード */

	code0 = calc_seq_code( *sx,*sy );  /* 始点の端点分類コードを求める */
	code1 = calc_seq_code( *ex,*ey );  /* 終点の端点分類コードを求める */

	/* 端点分類コードがどちらも0000ならばクリッピングは必要なし */
	if ( ( code0 == 0 ) && ( code1 == 0 ) ) return( 0 );

	/* 始点・終点の端点分類コードの論理積が非０ならば線分は完全に不可視 */
	if ( ( code0 & code1 ) != 0 ) return( -1 );

	/* 始点のクリッピング */
	if( code0 != 0 ) {
		if ( ! calc_clipped_point( code0, *sx,*sy, *ex,*ey, sx,sy ) )  return( -1 );
	}

	/* 終点のクリッピング */
	if( code1 != 0 ) {
		if ( ! calc_clipped_point( code1, *sx,*sy, *ex,*ey, ex,ey ) )  return( -1 );
	}

	return( 1 );
}
