#include<windows.h>

//戻り値
#define SUCCESS			 0
#define TOO_MUCH_POINT	-1
#define NO_POINT		-2

//CreateMask 関数
//原画像を元にマスクを作成します

//mask		：マスク画像
//MaskColor	：背景として扱う色
//FaceColor	：追跡対象として扱う色
//image		：原画像
//iWidth	：原画像の横幅
//iHeight	：原画像の高さ
//BackColor	：原画像の背景色

//戻り値	：なし

void CreateMask(LPBYTE mask,BYTE MaskColor,BYTE FaceColor,
				LPDWORD image,int iWidth,int iHeight,DWORD BackColor)
{
	for(int y=0;y<iHeight;y++) 		for(int x=0;x<iWidth;x++) 			mask[x+y*iWidth]=(image[x+y*iWidth]!=BackColor)?FaceColor:MaskColor; }  //traceEx 関数 //追跡対象の１ピクセル外側を追跡します //輪郭の１ピクセル外側の座標が格納されていく事になります  //mask			：マスク画像 //iWidth		：マスク画像の横幅 //iHeight		：マスク画像の高さ //OutColor		：追跡対象の外側の色 //InColor		：追跡対象の内側の色 //*lpPoints		：輪郭の座標を格納します //nPointsSum	：複数の輪郭の座標の総数 //nPoints		：lpPoints 配列の要素の個数 //*lpPolyCounts	：座標の個数を格納します //xStart		：追跡を開始する x 座標 //yStart		：追跡を開始する y 座標  //戻り値		：0(=SUCCESS 正常) / -1(=TOO_MUCH_POINT 異常)  int traceEx(LPBYTE mask,int iWidth,int iHeight,BYTE OutColor,BYTE InColor, 				POINT *lpPoints,int nPointsSum,int nPoints,INT *lpPolyCounts, 				int xStart,int yStart) { 	int x=xStart; 	int y=yStart; 	int n=0;		//座標の個数 	int vec=9; 	BYTE from,to;  	while(1){ 		if(n!=0 && x==xStart && y==yStart){		//終点に達した 			*lpPolyCounts=n; 			return SUCCESS;		//正常 		} 		if(nPointsSum+n>=nPoints){		//終点に達せずバッファが満杯
			*lpPolyCounts=n;
			return TOO_MUCH_POINT;		//無限ループに陥った可能性が高い
		}
		switch(vec){		//優先順位を付けてチェックする(闇雲に調べると無限ループに陥る可能性が高い)
			case 6:
				//右中が輪郭？
				from=((x+1)<0 || iWidth<=(x+1) || y<0 || iHeight<=y)?OutColor:mask[x+1+y*iWidth];
				to=((x+1)<0 || iWidth<=(x+1) || (y+1)<0 || iHeight<=(y+1))?OutColor:mask[x+1+(y+1)*iWidth];
				if(from==OutColor && to==InColor){
					x=x+1; y=y;
					lpPoints[n].x=x; lpPoints[n].y=(iHeight-1)-y; n++;
					vec=7; continue;
				}
			case 3:
				//右上が輪郭？
				from=((x+1)<0 || iWidth<=(x+1) || (y+1)<0 || iHeight<=(y+1))?OutColor:mask[x+1+(y+1)*iWidth];
				to=(x<0 || iWidth<=x || (y+1)<0 || iHeight<=(y+1))?OutColor:mask[x+(y+1)*iWidth];
				if(from==OutColor && to==InColor){
					x=x+1; y=y+1;
					lpPoints[n].x=x; lpPoints[n].y=(iHeight-1)-y; n++;
					vec=8; continue;
				}
			case 2:
				//中上が輪郭？
				from=(x<0 || iWidth<=x || (y+1)<0 || iHeight<=(y+1))?OutColor:mask[x+(y+1)*iWidth];
				to=((x-1)<0 || iWidth<=(x-1) || (y+1)<0 || iHeight<=(y+1))?OutColor:mask[x-1+(y+1)*iWidth];
				if(from==OutColor && to==InColor){
					x=x; y=y+1;
					lpPoints[n].x=x; lpPoints[n].y=(iHeight-1)-y; n++;
					vec=9; continue;
				}
			case 1:
				//左上が輪郭？
				from=((x-1)<0 || iWidth<=(x-1) || (y+1)<0 || iHeight<=(y+1))?OutColor:mask[x-1+(y+1)*iWidth];
				to=((x-1)<0 || iWidth<=(x-1) || y<0 || iHeight<=y)?OutColor:mask[x-1+y*iWidth];
				if(from==OutColor && to==InColor){
					x=x-1; y=y+1;
					lpPoints[n].x=x; lpPoints[n].y=(iHeight-1)-y; n++;
					vec=6; continue;
				}
			case 4:
				//左中が輪郭？
				from=((x-1)<0 || iWidth<=(x-1) || y<0 || iHeight<=y)?OutColor:mask[x-1+y*iWidth];
				to=((x-1)<0 || iWidth<=(x-1) || (y-1)<0 || iHeight<=(y-1))?OutColor:mask[x-1+(y-1)*iWidth];
				if(from==OutColor && to==InColor){
					x=x-1; y=y;
					lpPoints[n].x=x; lpPoints[n].y=(iHeight-1)-y; n++;
					vec=3; continue;
				}
			case 7:
				//左下が輪郭？
				from=((x-1)<0 || iWidth<=(x-1) || (y-1)<0 || iHeight<=(y-1))?OutColor:mask[x-1+(y-1)*iWidth];
				to=(x<0 || iWidth<=x || (y-1)<0 || iHeight<=(y-1))?OutColor:mask[x+(y-1)*iWidth];
				if(from==OutColor && to==InColor){
					x=x-1; y=y-1;
					lpPoints[n].x=x; lpPoints[n].y=(iHeight-1)-y; n++;
					vec=2; continue;
				}
			case 8:
				//中下が輪郭？
				from=(x<0 || iWidth<=x || (y-1)<0 || iHeight<=(y-1))?OutColor:mask[x+(y-1)*iWidth];
				to=((x+1)<0 || iWidth<=(x+1) || (y-1)<0 || iHeight<=(y-1))?OutColor:mask[x+1+(y-1)*iWidth];
				if(from==OutColor && to==InColor){
					x=x; y=y-1;
					lpPoints[n].x=x; lpPoints[n].y=(iHeight-1)-y; n++;
					vec=1; continue;
				}
			case 9:
				//右下が輪郭？
				from=((x+1)<0 || iWidth<=(x+1) || (y-1)<0 || iHeight<=(y-1))?OutColor:mask[x+1+(y-1)*iWidth];
				to=((x+1)<0 || iWidth<=(x+1) || y<0 || iHeight<=y)?OutColor:mask[x+1+y*iWidth];
				if(from==OutColor && to==InColor){
					x=x+1; y=y-1;
					lpPoints[n].x=x; lpPoints[n].y=(iHeight-1)-y; n++;
					vec=4; continue;
				}
				vec=6;		//一番上へ
		}
	}
}

//EditMaskSubstance インライン関数
//EditMask 関数の実体
//プログラムを見やすくするためにインライン関数として分離しただけ

//mask			：マスク画像
//iWidth		：マスク画像の横幅
//iHeight		：マスク画像の高さ
//BeforeColor	：置き換え対象の色
//AfterColor	：置き換える色
//x				：この座標の８近傍で BeforeColor の色を持つ画素が置き換えられます
//y				：この座標の８近傍で BeforeColor の色を持つ画素が置き換えられます
//*replace		：置き換えた個数が格納されます

//戻り値		：なし

inline void EditMaskSubstance(LPBYTE mask,int iWidth,int iHeight,BYTE BeforeColor,BYTE AfterColor,
							  int x,int y,unsigned long *replace)
{
	int xm,xp,ym,yp;

	xm=x-1; xp=x+1; ym=y-1; yp=y+1;
	if(xm<0) xm=0; if(xp>iWidth-1) xp=iWidth-1;
	if(ym<0) ym=0; if(yp>iHeight-1) yp=iHeight-1;
	if(mask[xm+ym*iWidth]==BeforeColor){
		mask[xm+ym*iWidth]=AfterColor;	(*replace)++;
	}
	if(mask[x+ym*iWidth]==BeforeColor){
		mask[x+ym*iWidth]=AfterColor;	(*replace)++;
	}
	if(mask[xp+ym*iWidth]==BeforeColor){
		mask[xp+ym*iWidth]=AfterColor;	(*replace)++;
	}
	if(mask[xm+y*iWidth]==BeforeColor){
		mask[xm+y*iWidth]=AfterColor;	(*replace)++;
	}
	if(mask[xp+y*iWidth]==BeforeColor){
		mask[xp+y*iWidth]=AfterColor;	(*replace)++;
	}
	if(mask[xm+yp*iWidth]==BeforeColor){
		mask[xm+yp*iWidth]=AfterColor;	(*replace)++;
	}
	if(mask[x+yp*iWidth]==BeforeColor){
		mask[x+yp*iWidth]=AfterColor;	(*replace)++;
	}
	if(mask[xp+yp*iWidth]==BeforeColor){
		mask[xp+yp*iWidth]=AfterColor;	(*replace)++;
	}
}

//EditMask 関数
//ある座標に隣接している特定の色を置き換えます

//mask			：マスク画像
//iWidth		：マスク画像の横幅
//iHeight		：マスク画像の高さ
//BeforeColor	：置き換え対象の色
//AfterColor	：置き換える色
//xStart		：この座標に隣接している BeforeColor の色を持つ画素が置き換えられます
//yStart		：この座標に隣接している BeforeColor の色を持つ画素が置き換えられます
//vec			：最初に調べる方向

//戻り値		：なし

void EditMask(LPBYTE mask,int iWidth,int iHeight,BYTE BeforeColor,BYTE AfterColor,
			  int xStart,int yStart,int vec)
{
	int x,y;
	unsigned long replace;		//置き換えた個数

	mask[xStart+yStart*iWidth]=AfterColor;
	while(1){
		switch(vec){
			case 0:
				replace=0;
				for(y=0;y<iHeight;y++) 					for(x=0;x<iWidth;x++) 						if(mask[x+y*iWidth]==AfterColor) 							EditMaskSubstance(mask,iWidth,iHeight,BeforeColor,AfterColor,x,y,&replace); 				if(replace==0) return; 			case 1: 				replace=0; 				for(x=iWidth-1;x>=0;x--)
					for(y=0;y<iHeight;y++) 						if(mask[x+y*iWidth]==AfterColor) 							EditMaskSubstance(mask,iWidth,iHeight,BeforeColor,AfterColor,x,y,&replace); 				if(replace==0) return; 			case 2: 				replace=0; 				for(y=iHeight-1;y>=0;y--)
					for(x=iWidth-1;x>=0;x--)
						if(mask[x+y*iWidth]==AfterColor)
							EditMaskSubstance(mask,iWidth,iHeight,BeforeColor,AfterColor,x,y,&replace);
				if(replace==0) return;
			case 3:
				replace=0;
				for(x=0;x<iWidth;x++) 					for(y=iHeight-1;y>=0;y--)
						if(mask[x+y*iWidth]==AfterColor)
							EditMaskSubstance(mask,iWidth,iHeight,BeforeColor,AfterColor,x,y,&replace);
				if(replace==0) return;
		}
		vec=0;		//二周目以降は一番上から
	}
}

//EditMaskAssist 関数
//画像の四辺に隣接している特定の色を置き換えるように
//EditMask 関数を呼び出します

//mask		：マスク画像
//iWidth	：マスク画像の横幅
//iHeight	：マスク画像の高さ
//MaskColor	：置き換え対象の色
//EditColor	：置き換える色

//戻り値	：なし

void EditMaskAssist(LPBYTE mask,int iWidth,int iHeight,BYTE MaskColor,BYTE EditColor)
{
	int x,y;

	for(x=0;x<iWidth;x++)			//下 		if(mask[x]==MaskColor) 			EditMask(mask,iWidth,iHeight,MaskColor,EditColor,x,0,0);  	for(y=0;y<iHeight;y++)			//右 		if(mask[iWidth-1+y*iWidth]==MaskColor) 			EditMask(mask,iWidth,iHeight,MaskColor,EditColor,iWidth-1,y,1);  	for(x=iWidth-1;x>=0;x--)		//上
		if(mask[x+(iHeight-1)*iWidth]==MaskColor)
			EditMask(mask,iWidth,iHeight,MaskColor,EditColor,x,iHeight-1,2);

	for(y=iHeight-1;y>=0;y--)		//左
		if(mask[y*iWidth]==MaskColor)
			EditMask(mask,iWidth,iHeight,MaskColor,EditColor,0,y,3);
}

//GetOutlineExPlus 関数
//対象の外側(複数)と内側(複数)の両方の輪郭を取得します

//image			：原画像
//iWidth		：原画像の横幅
//iHeight		：原画像の高さ
//BackColor		：背景色
//*lpPoints		：輪郭の座標を格納します
//nPoints		：lpPoints 配列の要素の個数
//*lpPolyCounts	：座標の個数を格納します
//nPolyCounts	：lpPolyCounts 配列の要素の個数
//*nCount		：輪郭の個数を格納します
//mask			：原画像と同じサイズの画像を渡して下さい
//inside		：内側の輪郭を検出する(TRUE) / しない(FALSE)

//戻り値		：0(=SUCCESS 正常) / -1(=TOO_MUCH_POINT 異常) / -2(=NO_POINT 異常)

//DANGER！
//正しく準備された画像を渡して下さい
//不正な画像を渡した場合はマシンが暴走する可能性もあります
//以下の画像は危険です
//○追跡対象の領域が多すぎる(背景色が意図した領域以外で使われている)
//○追跡対象または背景領域が複雑すぎる(１ピクセル幅しかない細い領域は危険です)

int GetOutlineExPlus(LPDWORD image,int iWidth,int iHeight,int BackColor,
					 POINT *lpPoints,int nPoints,INT *lpPolyCounts,int nPolyCounts,int *nCount,
					 LPBYTE mask,BOOL inside)
{
	const BYTE MaskColor =0x00;		//背景として扱う色
	const BYTE FaceColor =0xFF;		//追跡対象として扱う色
	const BYTE EditColorF=0x7F;		//追跡が終了した前景を EditColorF で置き換える
	const BYTE EditColorB=0x80;		//追跡が終了した背景を EditColorB で置き換える
	BYTE from,to;
	int x,y,i;
	int iPoints=0;					//複数の輪郭の座標の総数
	int iCounts=0;					//輪郭の個数

	CreateMask(mask,MaskColor,FaceColor,image,iWidth,iHeight,BackColor);

	for(y=0;y<iHeight;y++){ 		for(x=0;x<iWidth;x++){ 			from=((x-1)<0)?MaskColor:mask[x-1+y*iWidth]; 			to=mask[x+y*iWidth]; 			if(from==MaskColor && to==FaceColor){		//外側の輪郭 				i=traceEx(mask,iWidth,iHeight,MaskColor,FaceColor, 					&lpPoints[iPoints],iPoints,nPoints,&lpPolyCounts[iCounts],x-1,y); 				if(i) return i; 				iPoints+=lpPolyCounts[iCounts++]; 				if(iCounts>=nPolyCounts) goto DEST;
				EditMask(mask,iWidth,iHeight,FaceColor,EditColorF,x,y,0);
			}
		}
	}
	if(inside==TRUE){
		EditMaskAssist(mask,iWidth,iHeight,MaskColor,EditColorB);
		for(y=0;y<iHeight;y++){ 			for(x=1;x<iWidth;x++){ 				from=mask[x-1+y*iWidth]; 				to=mask[x+y*iWidth]; 				if(from==EditColorF && to==MaskColor){		//内側の輪郭 					i=traceEx(mask,iWidth,iHeight,EditColorF,MaskColor, 						&lpPoints[iPoints],iPoints,nPoints,&lpPolyCounts[iCounts],x-1,y); 					if(i) return i; 					iPoints+=lpPolyCounts[iCounts++]; 					if(iCounts>=nPolyCounts) goto DEST;
					EditMask(mask,iWidth,iHeight,MaskColor,EditColorB,x,y,0);
				}
			}
		}
	}
DEST:
	*nCount=iCounts;

	if(iCounts) return SUCCESS;
	else return NO_POINT;
}