// EdgeFind.cpp: implementation of the CEdgeFind class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "EdgeFind.h"
#include "SISBuffer.h"
#include "EdgeProc.h"
#include <numeric>

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
CEdgeFind::CEdgeFind()
{
	m_pHproj = NULL;
	m_pVproj = NULL;
}

CEdgeFind::~CEdgeFind()
{
	if(m_pHproj != NULL)
		delete[] m_pHproj, m_pHproj=NULL;
	if(m_pVproj != NULL)
		delete[] m_pVproj, m_pVproj=NULL;	
}

int CEdgeFind::Find_RightEdge(CSISBuffer *pBuffer, double pitch, int threshold, double rDefect, int nContinue)
{
	if(!pBuffer->IsValidBuffer())	return -1;

	int x, y;
	int width, height;
	int iPitch= (int)(pitch);
	
	width= pBuffer->GetWidth()- iPitch- 6;
	height= pBuffer->GetHeight()- 5;
	
	double pa, pb;
	pb= pitch- iPitch;
	pa= 1- pb;
	
	threshold*= 6;
	
	int cContinue= 0;
	int count;
//	int org, tar;
	int nDefect= (int)(height*rDefect);
	for(x= width- 1; x>= 0; x--)
	{
		count= 0;
		for(y= 0; y< height; y++)
		{			
			/*
			//2 by 1
			org= pBuffer->GetPixel(x, y)+ pBuffer->GetPixel(x+ 1, y);
			tar= (int)(pBuffer->GetPixel(x+ iPitch, y)*pa+ pBuffer->GetPixel(x+iPitch+ 1, y)+ pBuffer->GetPixel(x+iPitch+ 2, y)*pb);
			*/

			//3 by 2
//			org= pBuffer->GetPixel(x, y)+ pBuffer->GetPixel(x+ 1, y)+ pBuffer->GetPixel(x+ 2, y);
//			org+=pBuffer->GetPixel(x, y+1)+ pBuffer->GetPixel(x+ 1, y+1)+ pBuffer->GetPixel(x+ 2, y+1);
//			tar= (int)(pBuffer->GetPixel(x+ iPitch, y)*pa+ pBuffer->GetPixel(x+iPitch+ 1, y)+ pBuffer->GetPixel(x+iPitch+ 2, y)+ pBuffer->GetPixel(x+iPitch+ 3, y)*pb);
//			tar+=(int)(pBuffer->GetPixel(x+ iPitch, y+1)*pa+ pBuffer->GetPixel(x+iPitch+ 1, y+1)+ pBuffer->GetPixel(x+iPitch+ 2, y+1)+ pBuffer->GetPixel(x+iPitch+ 3, y+1)*pb);
//			if(abs(org- tar) > threshold)
			if(abs(pBuffer->GetDiff32(x, y, pitch)) > threshold)
			{
				count++;
			}
		}
		if(count >= nDefect)
		{
			cContinue++;
			if(cContinue >= nContinue)
				return x+ nContinue;
		}
		else
		{
			cContinue= 0;
		}
	}
	return -1;
}

int CEdgeFind::Find_LeftEdge(CSISBuffer *pBuffer, double pitch, int threshold, double rDefect, int nContinue)
{
	if(!pBuffer->IsValidBuffer())	return -1;
	
	int x, y;
	int width, height;
	int iPitch= (int)(pitch);
	
	width= pBuffer->GetWidth()- iPitch- 6;
	height= pBuffer->GetHeight()- 5;
	
	double pa, pb;
	pb= pitch- iPitch;
	pa= 1- pb;
	
	threshold*= 6;
	
	int cContinue= 0;
	int count;
//	int org, tar;
	int nDefect= (int)(height*rDefect);
	for(x= 0; x< width; x++)
	{
		count= 0;
		for(y= 0; y< height; y++)
		{
			/*
			//2 by 1
			org= pBuffer->GetPixel(x, y)+ pBuffer->GetPixel(x+ 1, y);
			tar= (int)(pBuffer->GetPixel(x+ iPitch, y)*pa+ pBuffer->GetPixel(x+iPitch+ 1, y)+ pBuffer->GetPixel(x+iPitch+ 2, y)*pb);
			*/
			//3 by 2
//			org= pBuffer->GetPixel(x, y)+ pBuffer->GetPixel(x+ 1, y)+ pBuffer->GetPixel(x+ 2, y);
//			org+=pBuffer->GetPixel(x, y+1)+ pBuffer->GetPixel(x+ 1, y+1)+ pBuffer->GetPixel(x+ 2, y+1);
//			tar= (int)(pBuffer->GetPixel(x+ iPitch, y)*pa+ pBuffer->GetPixel(x+iPitch+ 1, y)+ pBuffer->GetPixel(x+iPitch+ 2, y)+ pBuffer->GetPixel(x+iPitch+ 3, y)*pb);
//			tar+=(int)(pBuffer->GetPixel(x+ iPitch, y+1)*pa+ pBuffer->GetPixel(x+iPitch+ 1, y+1)+ pBuffer->GetPixel(x+iPitch+ 2, y+1)+ pBuffer->GetPixel(x+iPitch+ 3, y+1)*pb);

//			if(abs(org- tar) > threshold)
			if(abs(pBuffer->GetDiff32(x, y, pitch)) > threshold)
			{
				count++;
			}
		}
		if(count >= nDefect)
		{
			cContinue++;
			if(cContinue >= nContinue)
				return x+ 2+ iPitch- nContinue;
		}
		else
		{
			cContinue= 0;
		}
	}
	return -1;
}

int	CEdgeFind::Find_LeftCanny(CSISBuffer *pBuffer,int nThres)
{
	LPBYTE		pImg = pBuffer->GetDataAddress();
	CSize		szImg = CSize(pBuffer->GetWidth(),pBuffer->GetHeight());

	if(pImg == NULL || szImg.cx <= 0 || szImg.cy <= 0)
		return -1;

	int			nLeftLine = -1;
	const	int nFindLineRatio = (int)((double)szImg.cy*0.5);

	LPBYTE		pTgt = new BYTE[szImg.cx*szImg.cy];
	ZeroMemory(pTgt,sizeof(BYTE)*szImg.cx*szImg.cy);

	CEdgeProc		EdgeProc;

	CSISBuffer		mosisEdge(pTgt,szImg.cx,szImg.cy);	
	if(EdgeProc.CannyEdgeProcessing(pImg,CRect(0,0,szImg.cx,szImg.cy),GM_Sobel,nThres,mosisEdge) == FALSE)
	{
		delete[] pTgt, pTgt=NULL;
		return nLeftLine;
	}

// 	CString				str;
// 	if(pImg != NULL)
// 	{
// 		CSISBuffer		mosis(pImg,szImg.cx,szImg.cy);
// 		str.Format("D:\\Image\\Org.bmp");
// 		CBufferAttach		attach(str);
// 		attach.AttachToFile(mosis);
// 	}
// 
// 	if(pTgt != NULL)
// 	{
// 		CSISBuffer		mosis(pTgt,szImg.cx,szImg.cy);
// 		str.Format("D:\\Image\\Edge.bmp");
// 		CBufferAttach		attach(str);
// 		attach.AttachToFile(mosis);
// 	}

	int			u,v,nCount;

	for(u=2;u<szImg.cx-2;u++)
	{
		nCount = 0;
		for(v=2;v<szImg.cy-2;v++)
		{
			if(*(pTgt+v*szImg.cx+u) == 255)
				nCount++;
		}

		if(nCount >= nFindLineRatio)
		{
			nLeftLine = u;
			break;
		}
	}

	delete[] pTgt, pTgt=NULL;

	return nLeftLine;
}

double CEdgeFind::FindLine_H(LPBYTE pImg,CSize szImg,CRect &rectIns,int nThres,EDGELINE_POLAR enDir,EdgeSignalType enSignalType,enEdgeFindType enFind)
{
	if(pImg ==  NULL || szImg.cx <= 0)
		return -1;

	if(enFind == EDGE_PROJECTION)
		return FindGlassHorizontalLine(pImg,szImg,rectIns,nThres,TRUE);

	if(m_pHproj != NULL)
		delete[] m_pHproj, m_pHproj=NULL;	

	m_pHproj = new IMPROJ[szImg.cx+1];
	ZeroMemory(m_pHproj,sizeof(IMPROJ)*(szImg.cx+1));

	CRect		rect = rectIns;
	ULONG		nProjMax,nProjMin;	
	int			nPos = -1;	
	double		dAvgPos = 0;

	AssertOnFrameRect(rect,szImg);

	if(FV_ProjGet(pImg,szImg,rect,PROJECTION_VERTICAL,m_pHproj,&nProjMax,&nProjMin) == TRUE)
	{		
		switch(enFind)
		{
		case EDGE_MAXCONTRAST:
			nPos = FindMaxContrastEx(m_pHproj,rect.left,rect.right,szImg.cx,rect.Height(),enDir,nThres);
			break;
		case EDGE_FIRSTEDGE:
			nPos = FindFirstEdge(m_pHproj,rect.left,rect.right,szImg.cx,rect.Height(),enDir,nThres);
			break;
		default:
			{
				if(m_pHproj != NULL)
					delete[] m_pHproj, m_pHproj=NULL;	
				return dAvgPos;
			}
		}

		if(nPos <= -1)
		{			
			CSISBuffer		buffer(pImg,szImg.cx,szImg.cy);		
			int	nMaxVal;
			nPos = FindMaxContrast(buffer,rect,TRUE,nMaxVal);
			if(nPos == -1)
			{
				if(m_pHproj != NULL)
					delete[] m_pHproj, m_pHproj=NULL;	
				return dAvgPos;
			}
		}

		dAvgPos = (double)nPos;

		rect.left = nPos - 5;
		rect.right = nPos + 5;
		double dTmp = FindLineSubPixel(pImg,szImg,rect,nThres,-nThres,DIR_HORIZONTAL,SearchTypeIn2Out,enSignalType);
		if(dTmp != -1)
			dAvgPos = dTmp;

		//dAvgPos = GetSubPixelPos(pImg,nPos,szImg,rect,dRatio,bLeft,DIR_HORIZONTAL,nNumber);
	}

	if(m_pHproj != NULL)
		delete[] m_pHproj, m_pHproj=NULL;	

	return dAvgPos;
}

BOOL CEdgeFind::FindGlssEdgeLine(int &nPos,CRect rect,LPIMPROJ pProj,BOOL bDir,PROJECTION_TYPE nType,int nThres,int nContiValue,int nDist)
{	
	if(pProj == NULL)
		return FALSE;

	int     nThreshold = nThres * rect.Width();
	int		iX,nCountinueCount,nGab;

	nPos = -1;
	nCountinueCount = 0;
	switch(nType)
	{
	case PROJECTION_VERTICAL:
		{			
			nThreshold = nThres * rect.Height();
			if(bDir == TRUE)				// Left -> Right
			{				
				for(iX=rect.left;iX<rect.right-nDist;iX++)
				{
					nGab = abs(pProj[iX].f - pProj[iX+nDist].f);			
					if (nGab > nThreshold)
						nCountinueCount++;
					else
						nCountinueCount = 0;

					if (nCountinueCount >= nContiValue)
					{
						nPos = pProj[iX+nDist].x-(nContiValue-1);
						return TRUE;
					}			
				}				
			}
			else							// Right -> Left
			{			
				for(iX=rect.right-1;iX>=rect.left+nDist;iX--)
				{
					nGab = abs(pProj[iX].f - pProj[iX-nDist].f);			
					if (nGab > nThreshold)
						nCountinueCount++;
					else
						nCountinueCount = 0;

					if (nCountinueCount >= nContiValue)
					{
						nPos = pProj[iX-nDist].x+(nContiValue-1);
						return TRUE;
					}			
				}
			}
		}
		break;
	case PROJECTION_HORIZONTAL:
		{			
			nThreshold = nThres * rect.Width();
			if(bDir == TRUE)			// Top -> Bottom
			{				
				for(iX=rect.top;iX<rect.bottom-nDist;iX++)
				{
					nGab = abs(pProj[iX].f - pProj[iX+nDist].f);			
					if (nGab > nThreshold)
						nCountinueCount++;
					else
						nCountinueCount = 0;

					if (nCountinueCount >= nContiValue)
					{
						nPos = pProj[iX+nDist].x-(nContiValue-1);
						return TRUE;
					}			
				}	
			}
			else						// Bottom -> Top
			{
				for(iX=rect.bottom-1;iX>=rect.top+nDist;iX--)
				{
					nGab = abs(pProj[iX].f - pProj[iX-nDist].f);			
					if (nGab > nThreshold)
						nCountinueCount++;
					else
						nCountinueCount = 0;

					if (nCountinueCount >= nContiValue)
					{
						nPos = pProj[iX-nDist].x+(nContiValue-1);
						return TRUE;
					}			
				}	
			}
		}
		break;
	}	

	return FALSE;
}

double CEdgeFind::FindGlassHorizontalLine(LPBYTE pImg,CSize szImg,CRect &rectIns,int nThres,BOOL bDir, int nDist)
{
	if(pImg ==  NULL || szImg.cx <= 0)
		return -1;

	if(m_pHproj != NULL)
		delete[] m_pHproj, m_pHproj=NULL;	

	m_pHproj = new IMPROJ[szImg.cx+1];
	ZeroMemory(m_pHproj,sizeof(IMPROJ)*(szImg.cx+1));
	
	CRect		rect = rectIns;
	ULONG		nProjMax,nProjMin;
	BOOL		bRet = FALSE;	
	int			nPos = -1;
	const int	nContinueCnt = 2;
	const int	nLevelDist = nDist;
	double		dAvgPos = 0;

	AssertOnFrameRect(rect,szImg);

	if(FV_ProjGet(pImg,szImg,rect,PROJECTION_VERTICAL,m_pHproj,&nProjMax,&nProjMin) == TRUE)
	{		
		if(FindGlssEdgeLine(nPos,rect,m_pHproj,bDir,PROJECTION_VERTICAL,nThres,nContinueCnt,nLevelDist) == FALSE)
		{
			if(m_pHproj != NULL)
				delete[] m_pHproj, m_pHproj=NULL;	
			return -1;
		}
		else
		{
			dAvgPos = nPos;

			/*
			CRect				rectCon(nPos-2,rect.top,nPos+2,rect.bottom);
			CSISBuffer		buffer(pImg,szImg.cx,szImg.cy);			

			int nMaxVal;
			int nMaxCon = FindMaxContrast(buffer,rectCon,TRUE,nMaxVal);
			if(nMaxCon != -1)
				nPos = nMaxCon;

			double		cPos;
			double		dPosVal[3];
			int			nHorStart = nPos;
			int			v;
			double		dSumPos=0,dSumCnt=0;

			for(v=rect.top;v<rect.bottom;v++)
			{				
				dPosVal[0] = *(pImg+v*szImg.cx+(nHorStart-1));
				dPosVal[1] = *(pImg+v*szImg.cx+(nHorStart));
				dPosVal[2] = *(pImg+v*szImg.cx+(nHorStart+1));				
				
				cPos = 0;
				if(parabolicInterpolate(dPosVal[0],dPosVal[1],dPosVal[2],&cPos) == TRUE)
				{
					dSumPos += cPos;
					dSumCnt++;
				}				
			}
			
			dAvgPos = 0;
			if(dSumCnt > 0)
				dAvgPos = dSumPos/dSumCnt;

			dAvgPos += nPos;
			*/

		}
	}

	if(m_pHproj != NULL)
		delete[] m_pHproj, m_pHproj=NULL;	
	
	return dAvgPos;
}

double CEdgeFind::FindGlassVerticalLine(LPBYTE pImg,CSize szImg,CRect &rectIns,int nThres,BOOL bDir,int nDist)
{
	if(pImg == NULL || szImg.cy <= 0) 
		return -1;

	if(m_pVproj != NULL)
		delete[] m_pVproj, m_pVproj=NULL;	

	m_pVproj = new IMPROJ[szImg.cy+1];
	ZeroMemory(m_pVproj,sizeof(IMPROJ)*(szImg.cy+1));

	CRect		rect = rectIns;
	ULONG		nProjMax,nProjMin;
	BOOL		bRet = FALSE;
	int			nVertical = -1;
	const int	nContinueCnt = 3;
	const int	nLevelDist = nDist;
	double		dAvgPos;
	
	AssertOnFrameRect(rect,szImg);	

	if(FV_ProjGet(pImg,szImg,rect,PROJECTION_HORIZONTAL,m_pVproj,&nProjMax,&nProjMin) == TRUE)
	{
		if(FindGlssEdgeLine(nVertical,rect,m_pVproj,bDir,PROJECTION_HORIZONTAL,nThres,nContinueCnt,nLevelDist) == FALSE)
		{				
			if(m_pVproj != NULL)
				delete[] m_pVproj, m_pVproj=NULL;	
			return -1;
		}
		else
		{
			dAvgPos = nVertical;
			/*
			CRect				rectCon(rect.left,nVertical-2,rect.right,nVertical+2);
			CSISBuffer		buffer(pImg,szImg.cx,szImg.cy);			

			int nMaxVal;
			int nMaxCon = FindMaxContrast(buffer,rectCon,FALSE,nMaxVal,bDir);
			if(nMaxCon != -1)
				nVertical = nMaxCon;

			double		cPos;
			double		dPosVal[3];
			int			nVertStart = nVertical;
			int			u;
			double		dSumPos=0,dSumCnt=0;

			for(u=rect.left;u<rect.right;u++)
			{
				dPosVal[0] = *(pImg+(nVertStart-1)*szImg.cx+u);
				dPosVal[1] = *(pImg+(nVertStart)*szImg.cx+u);
				dPosVal[2] = *(pImg+(nVertStart+1)*szImg.cx+u);			

				cPos = 0;
				if(parabolicInterpolate(dPosVal[0],dPosVal[1],dPosVal[2],&cPos) == TRUE)
				{
					dSumPos += cPos;
					dSumCnt++;
				}				
			}

			dAvgPos = 0;
			if(dSumCnt > 0)
				dAvgPos = dSumPos/dSumCnt;

			dAvgPos += nVertical;
			*/
		}
	}

	if(m_pVproj != NULL)
		delete[] m_pVproj, m_pVproj=NULL;
	
	return dAvgPos;
}

double CEdgeFind::FindLine_V(LPBYTE pImg,CSize szImg,CRect &rectIns,int nThres,EDGELINE_POLAR enDir,EdgeSignalType enSignalType,enEdgeFindType enFind,BOOL bTop)
{
	if(pImg ==  NULL || szImg.cy <= 0)
		return -1;

	if(enFind == EDGE_PROJECTION)
	{
		return FindGlassVerticalLine(pImg,szImg,rectIns,nThres,bTop);
	}

	if(m_pVproj != NULL)
		delete[] m_pVproj, m_pVproj=NULL;	

	m_pVproj = new IMPROJ[szImg.cy+1];
	ZeroMemory(m_pVproj,sizeof(IMPROJ)*(szImg.cy+1));

	CRect		rect = rectIns;
	ULONG		nProjMax,nProjMin;	
	int			nPos = -1;	
	double		dAvgPos = 0;

	AssertOnFrameRect(rect,szImg);

	if(FV_ProjGet(pImg,szImg,rect,PROJECTION_HORIZONTAL,m_pVproj,&nProjMax,&nProjMin) == TRUE)
	{		
		switch(enFind)
		{
		case EDGE_MAXCONTRAST:
			nPos = FindMaxContrastEx(m_pVproj,rect.top,rect.bottom,szImg.cy,rect.Width(),enDir,nThres,bTop);
			break;
		case EDGE_FIRSTEDGE:
			nPos = FindFirstEdge(m_pVproj,rect.top,rect.bottom,szImg.cy,rect.Width(),enDir,nThres,bTop);
			break;
		default:
			{
				if(m_pVproj != NULL)
					delete[] m_pVproj, m_pVproj=NULL;	
				return dAvgPos;
			}
		}

		if(nPos <= -1)
		{			
			CSISBuffer		buffer(pImg,szImg.cx,szImg.cy);		
			int nMaxVal;			
			nPos = FindMaxContrast(buffer,rect,FALSE,nMaxVal,bTop);
			if(nPos == -1)
			{
				if(m_pVproj != NULL)
					delete[] m_pVproj, m_pVproj=NULL;	
				return dAvgPos;
			}
		}

		dAvgPos = (double)nPos;

		rect.top = nPos - 5;
		rect.bottom = nPos + 5;
		double dTmp = FindLineSubPixel(pImg,szImg,rect,nThres,-nThres,DIR_VERTICAL,SearchTypeIn2Out,enSignalType);
		if(dTmp != -1)
			dAvgPos = dTmp;

		//dAvgPos = GetSubPixelPos(pImg,nPos,szImg,rect,dRatio,bTop,DIR_VERTICAL,nNumber);
	}

	if(m_pVproj != NULL)
		delete[] m_pVproj, m_pVproj=NULL;	

	return dAvgPos;
}

void CEdgeFind::AssertOnFrameRect(CRect &rect,CSize szImg)
{
	if(szImg.cx <= 0 || szImg.cy <= 0)
		return;

	if(rect.left < 0) rect.left = 0;
	if(rect.left > szImg.cx) rect.left = szImg.cx-1;	
	if(rect.right < 0) rect.right = 0;
	if(rect.right > szImg.cx) rect.right = szImg.cx-1;	
	if(rect.left > rect.right) std::swap(rect.left,rect.right);
	if(rect.top < 0) rect.top = 0;
	if(rect.top > szImg.cy) rect.top = szImg.cy-1;
	if(rect.bottom < 0) rect.bottom = 0;
	if(rect.bottom > szImg.cy) rect.bottom = szImg.cy-1;
	if(rect.top > rect.bottom) std::swap(rect.top,rect.bottom);
}

// BOOL IMProjGet(IMAGE src, ROI roi, long type, IMPROJ* res, unsigned long* max, unsigned long* min)
//  * Get the projected data
//  * Parameters
//    - src : image
//    - rect : ROI
//    - type : direction
//    - res : projection data pointer
//    - max : maximum value
//    - min : minimum value
//------------------------------------------------------------------------
BOOL CEdgeFind::FV_ProjGet(LPBYTE src,CSize szImg, CRect &rect, PROJECTION_TYPE type, IMPROJ* res, ULONG* max, ULONG* min)
{
	if(res == NULL || src == NULL)
		return FALSE;

	long			cu = szImg.cx, cv = szImg.cy;
	unsigned char	*buf = src;
	long			u, v, i;
	unsigned long	sum, *mx = max, *mn = min;

	switch(type)
	{
	case PROJECTION_VERTICAL:
		ZeroMemory(res,sizeof(IMPROJ)*rect.Width());

		*mx = 0;
		*mn = (rect.bottom-rect.top+1)*255;

		for(i=0, u=rect.left; u<rect.right; u++)
		{
			sum = 0L;
			for(v=rect.top; v<rect.bottom; v++) 
				sum += *(buf+u+cu*v);

			res[u].x = u; 
			res[u].f = sum;

			if(*mx < sum) *mx = sum;
			if(*mn > sum) *mn = sum;			

			i++;			
		}		
		return TRUE;		
	case PROJECTION_HORIZONTAL:
		ZeroMemory(res,sizeof(IMPROJ)*rect.Height());

		*mx = 0;
		*mn = (rect.right-rect.left+1)*255;

		for(i=0, v=rect.top; v<rect.bottom; v++)
		{
			sum = 0L;
			for(u=rect.left; u<rect.right; u++) 
				sum += *(buf+u+cu*v);

			res[v].x = v; 			
			res[v].f = sum;

			if(*mx < sum) *mx = sum;
			if(*mn > sum) *mn = sum;
			i++;
		}
		return TRUE;
	}
	return	FALSE;
}

int CEdgeFind::FindMaxContrastEx(IMPROJ* src, int nStart,int nEnd, long Width, long Height, EDGELINE_POLAR enDir, long Thresh,BOOL bForward)
{
	long		i, j, k;
	long		*fvalue;
	int			ret = -1;
	long		sum, max = 0, min = 0;
	long		val;	

	fvalue = new long[Width];
	ZeroMemory(fvalue,sizeof(long)*Width);	

	int			filterWidth;
	int			*mask;

	filterWidth = 2;
	mask = (int*)malloc( sizeof(int) * ((filterWidth*2)+1) );

	for(i=0; i<(filterWidth*2)+1; i++)
	{
		if(i < filterWidth)
		{
			mask[i] = -1;
		}
		else if( i == filterWidth)
		{
			mask[i] = 0;
		}
		else
		{
			mask[i] = 1;
		}
	}

	for(i=nStart+filterWidth; i<nEnd - filterWidth-1; i++)
	{
		sum = 0;
		for(j=0, k=-filterWidth; j<(filterWidth*2)+1; j++, k++)
		{
			sum += src[i+k].f * mask[j];
		}

		fvalue[i] = sum / ((Height+1)*filterWidth);  		
	}

	if(bForward == TRUE)
	{
		for(i=nStart; i<nEnd; i++)
		{
			if(enDir == POLAR_BTOW)
			{
				if(fvalue[i] >= Thresh)
				{
					if(fvalue[i] >= max)
					{
						max = fvalue[i];
						ret = src[i].x;
					}

				}
			}
			else if(enDir == POLAR_WTOB)
			{
				val = fvalue[i]*-1;

				if(val >= Thresh)		
				{
					if(val >= max)
					{
						max = val;
						ret = src[i].x;
					}
				}
			}
			else if(enDir == POLAR_ANY)
			{
				val = abs(fvalue[i]);

				if(val >= Thresh)
				{
					if(val >= max)
					{
						max = val;
						ret = src[i].x;
					}

				}
			}
		}
	}
	else
	{
		for(i=nEnd-1; i>=nStart; i--)
		{
			if(enDir == POLAR_BTOW)
			{
				if(fvalue[i] >= Thresh)
				{
					if(fvalue[i] >= max)
					{
						max = fvalue[i];
						ret = src[i].x;
					}

				}
			}
			else if(enDir == POLAR_WTOB)
			{
				val = fvalue[i]*-1;

				if(val >= Thresh)		
				{
					if(val >= max)
					{
						max = val;
						ret = src[i].x;
					}
				}
			}
			else if(enDir == POLAR_ANY)
			{
				val = abs(fvalue[i]);

				if(val >= Thresh)
				{
					if(val >= max)
					{
						max = val;
						ret = src[i].x;
					}

				}
			}
		}
	}

	delete[] fvalue;
	if(mask) free(mask);

	return ret;
}

int CEdgeFind::FindMaxContrast(CSISBuffer &bufferOrg,CRect rect,BOOL bHor,int &nMaxDiff,BOOL bForward)
{
	int			nPos = -1;
	int			i,j,nCnt,iLoop;
	int			*pVal = NULL;	
	int			nMaxVal = 0;
	int			nDiff;

	nMaxDiff = 0;
	if(bHor == TRUE)
	{
		pVal = new int[rect.Width()+1];
		nCnt = rect.Width()+1;
		ZeroMemory(pVal,sizeof(int)*nCnt);
		for(i=rect.top;i<rect.bottom;i++)
		{
			iLoop = 0;
			for(j=rect.left;j<=rect.right-1;j++,iLoop++)
			{
				nDiff = abs(*bufferOrg.GetDataAddress(j,i)-*bufferOrg.GetDataAddress(j+1,i));
				pVal[iLoop] += nDiff;
				if(nDiff > nMaxDiff)
					nMaxDiff = nDiff;
			}
		}

		for(i=0;i<nCnt;i++)
		{
			if(nMaxVal < pVal[i])
			{
				nMaxVal = pVal[i];
				nPos = i+rect.left+1;
			}
		}
	}
	else
	{
		pVal = new int[rect.Height()+1];
		nCnt = rect.Height()+1;
		ZeroMemory(pVal,sizeof(int)*nCnt);
		if(bForward == TRUE)
		{
			for(i=rect.left;i<rect.right;i++)
			{
				iLoop = 0;			
				for(j=rect.top;j<=rect.bottom-1;j++,iLoop++)
				{
					nDiff = abs(*bufferOrg.GetDataAddress(i,j)-*bufferOrg.GetDataAddress(i,j+1));;
					pVal[iLoop] += nDiff;
					if(nDiff > nMaxDiff)
						nMaxDiff = nDiff;
				}
			}

			for(i=0;i<nCnt;i++)
			{
				if(nMaxVal < pVal[i])
				{
					nMaxVal = pVal[i];
					nPos = i+rect.top+1;
				}
			}
		}
		else
		{
			for(i=rect.left;i<rect.right;i++)
			{
				iLoop = 0;
				for(j=rect.bottom;j>=rect.top+1;j--,iLoop++)
				{
					nDiff = abs(*bufferOrg.GetDataAddress(i,j)-*bufferOrg.GetDataAddress(i,j-1));
					pVal[iLoop] += nDiff;
					if(nDiff > nMaxDiff)
						nMaxDiff = nDiff;
				}
			}	

			for(i=0;i<nCnt;i++)
			{
				if(nMaxVal < pVal[i])
				{
					nMaxVal = pVal[i];
					nPos = rect.bottom-i-1;
				}
			}
		}	
	}	

	if(pVal != NULL)
		delete[] pVal, pVal=NULL;

	return nPos;
}

int CEdgeFind::FindFirstEdge(IMPROJ* src, int nStart,int nEnd, long Width, long Height, EDGELINE_POLAR enDir, long Thresh,BOOL bForward)
{
	long		i, j, k;
	long		*fvalue;
	int			ret = -1;
	long		sum;
	long		max=0, max_index=0;
	int			filterWidth;
	int			*mask;

	filterWidth = 2;
	mask = (int*)malloc( sizeof(int) * ((filterWidth*2)+1) );

	for(i=0; i<(filterWidth*2)+1; i++)
	{
		if(i < filterWidth)
		{
			mask[i] = -1;
		}
		else if( i == filterWidth)
		{
			mask[i] = 0;
		}
		else
		{
			mask[i] = 1;
		}
	}

	if(filterWidth == 0) return -2;

	fvalue = new long[Width];
	ZeroMemory(fvalue,sizeof(long)*Width);		

	if(bForward == TRUE)
	{
		for(i=nStart+filterWidth; i<nEnd - filterWidth-1; i++)
		{
			sum = 0;
			for(j=0, k=-filterWidth; j<(filterWidth*2)+1; j++, k++)
			{
				sum += src[i+k].f * mask[j];
			}

			fvalue[i] = sum / ((Height+1)*filterWidth);  		
		}

		for(i=nStart; i<nEnd; i++)
		{
			if(enDir == POLAR_BTOW)
			{
				if(fvalue[i] > Thresh)
				{
					for(int j=0; j<filterWidth+1; j++)
					{
						if(fvalue[i+j] > max)
						{
							max = fvalue[i+j];
							max_index = j;
						}
					}

					ret = src[i].x + max_index;
					break;
				}
			}
			else if(enDir == POLAR_WTOB)
			{
				if(fvalue[i]*-1 > Thresh)
				{
					for(int j=0; j<filterWidth+1; j++)
					{
						if(fvalue[i+j]*-1 > max)
						{
							max = fvalue[i+j];
							max_index = j;
						}
					}

					ret = src[i].x + max_index;
					break;
				}
			}
			else if(enDir == POLAR_ANY)
			{
				if(abs(fvalue[i]) > Thresh)
				{
					for(int j=0; j<filterWidth+1; j++)
					{
						if(abs(fvalue[i+j]) > max)
						{
							max = fvalue[i+j];
							max_index = j;
						}
					}

					ret = src[i].x + max_index;
					break;
				}
			}
		}
	}
	else
	{
		for(i=nEnd - filterWidth-1; i>=nStart+filterWidth; i--)
		{
			sum = 0;
			for(j=0, k=filterWidth; j<(filterWidth*2)+1; j++, k--)
			{
				sum += src[i+k].f * mask[j];
			}

			fvalue[i] = sum / ((Height+1)*filterWidth);  		
		}

		for(i=nEnd-1; i>=nStart; i--)
		{
			if(enDir == POLAR_BTOW)
			{
				if(fvalue[i] > Thresh)
				{
					for(int j=0; j<filterWidth+1; j++)
					{
						if(fvalue[i+j] > max)
						{
							max = fvalue[i+j];
							max_index = j;
						}
					}

					ret = src[i].x + max_index;
					break;
				}
			}
			else if(enDir == POLAR_WTOB)
			{
				if(fvalue[i]*-1 > Thresh)
				{
					for(int j=0; j<filterWidth+1; j++)
					{
						if(fvalue[i+j]*-1 > max)
						{
							max = fvalue[i+j];
							max_index = j;
						}
					}

					ret = src[i].x + max_index;
					break;
				}
			}
			else if(enDir == POLAR_ANY)
			{
				if(abs(fvalue[i]) > Thresh)
				{
					for(int j=0; j<filterWidth+1; j++)
					{
						if(abs(fvalue[i+j]) > max)
						{
							max = fvalue[i+j];
							max_index = j;
						}
					}

					ret = src[i].x + max_index;
					break;
				}
			}
		}
	}

	delete[] fvalue;
	if(mask) free(mask);

	return ret;
}

double CEdgeFind::FindLineSubPixel(LPBYTE pImg,CSize szImg,CRect &rectIns,int nPosiThres,int nNegaThres,EDGELINE_DIR enDir,EdgeSearchType enSearchType,EdgeSignalType enSignalType,int nKernelSize)
{
	if(pImg ==  NULL)
		return -1;

	CRect		rect = rectIns;		
	double		dAvgPos = -1;	

	AssertOnFrameRect(rect,szImg);

	if(CalculateImageValue(enDir,pImg,szImg.cx,szImg.cy,rect,szImg.cx,m_vectorImageData) == FALSE)
		return dAvgPos;

	if(CalculateEdgeValue(m_vectorImageData,m_vectorEdgeData,m_vectorEdgeType,nPosiThres,nNegaThres,nKernelSize) == FALSE)
		return dAvgPos;

	CalculateEdgePosition(SubPixelQuadratic, nPosiThres, nNegaThres);

	// get left position
	double dLeftPos = 9999.0;
	if (!GetEdgeLeftPosition(enSignalType, enSearchType, 0, dLeftPos))
	{
		return dAvgPos;
	}

	if(enDir == DIR_HORIZONTAL)
		dAvgPos = rect.left + dLeftPos;
	else
		dAvgPos = rect.top + dLeftPos;

	return dAvgPos;
}

BOOL CEdgeFind::CalculateImageValue(EDGELINE_DIR nDirection, BYTE *pImage, int nWidth, int nHeight, CRect &rect, int nStep, VectorDouble& vectorImageData)
{
	vectorImageData.clear();

	if (pImage==NULL) return FALSE;

	double dValue = 0.0;

	switch (nDirection)
	{
	case DIR_HORIZONTAL:
		for (int j=rect.left; j<rect.right; j++)
		{
			dValue = 0.0;
			for (int i=rect.top; i<rect.bottom; i++)
			{
				dValue += pImage[(i*nStep)+j];
			}
			dValue /= double(rect.Height());
			vectorImageData.push_back(dValue);
		}
		break;

	case DIR_VERTICAL:
		for (int i=rect.top; i<rect.bottom; i++)
		{	
			dValue = 0.0;
			for (int j=rect.left; j<rect.right; j++)
			{
				dValue += UCHAR(pImage[(i*nStep)+j]);
			}
			dValue /= double(rect.Width());
			vectorImageData.push_back(dValue);
		}
		break;
	}

	return TRUE;
}

BOOL CEdgeFind::CalculateEdgeValue(EDGELINE_DIR nDirection, short *pImage, int nWidth, int nHeight, int nStep, VectorDouble& vectorEdgeData, VectorInteger& vectorEdgeType, double dPositiveThres, double dNegativeThres)
{
	vectorEdgeData.clear();
	vectorEdgeType.clear();

	if (pImage==NULL) return FALSE;

	double dValue = 0.0;
	int nType = EdgeTypeNone;

	switch (nDirection)
	{
	case DIR_VERTICAL:
		for (int j=0; j<nWidth; j++)
		{
			dValue = 0.0;
			nType = EdgeTypeNone;

			for (int i=0; i<nHeight; i++)
			{
				dValue += pImage[(i*nStep)+j];
			}
			dValue /= double(nHeight);

			if (dValue >= dPositiveThres)
			{
				nType = EdgeTypePositive;
			}
			else if (dValue <= dNegativeThres )
			{
				nType = EdgeTypeNegative;
			}

			vectorEdgeType.push_back(nType);
			vectorEdgeData.push_back(dValue);
		}
		break;

	case DIR_HORIZONTAL:
		for (int i=0; i<nHeight; i++)
		{	
			dValue = 0.0;
			nType = EdgeTypeNone;

			for (int j=0; j<nWidth; j++)
			{
				dValue += UCHAR(pImage[(i*nStep)+j]);
			}
			dValue /= double(nWidth);

			if (dValue >= dPositiveThres)
			{
				nType = EdgeTypePositive;
			}
			else if (dValue <= dNegativeThres )
			{
				nType = EdgeTypeNegative;
			}

			vectorEdgeData.push_back(dValue);
			vectorEdgeType.push_back(nType);
		}
		break;
	}

	return TRUE;
}

BOOL CEdgeFind::CalculateEdgeValue(const VectorDouble& vectorImageData, VectorDouble& vectorEdgeData, int nKernelSize)
{	
	if (nKernelSize<2 || (nKernelSize%2)!=0) return FALSE;

	if (vectorImageData.size()<nKernelSize) return FALSE;

	vectorEdgeData.clear();

	double dLeft	= 0.0;
	double dRight	= 0.0;
	double dValue	= 0.0;

	UINT nPitchSize = nKernelSize/2;

	// push first pitch
	for (UINT i=0; i<nPitchSize; i++)
	{
		vectorEdgeData.push_back(0.0);
	}

	// push center pitch
	for (UINT i=0; i<vectorImageData.size()-(nKernelSize); i++)
	{
		dLeft = dRight = 0.0;
		for (UINT j=0; j<nPitchSize; j++)
		{
			dLeft	+= vectorImageData[i+j];
			dRight	+= vectorImageData[i+j+nPitchSize];
		}
		dLeft /= double(nPitchSize);
		dRight /= double(nPitchSize);

		dValue = dRight - dLeft;
		vectorEdgeData.push_back(dValue);
	}

	// push last pitch
	for (UINT i=0; i<nPitchSize; i++)
	{
		vectorEdgeData.push_back(0.0);
	}

	return TRUE;
}

BOOL CEdgeFind::CalculateEdgeValue(const VectorDouble& vectorImageData, VectorDouble& vectorEdgeData, VectorInteger& vectorEdgeType, double dPositiveThres, double dNegativeThres, int nKernelSize)
{	
	vectorEdgeData.clear();
	vectorEdgeType.clear();

	if (nKernelSize<2 || (nKernelSize%2)!=0) return FALSE;
	if (vectorImageData.size()<nKernelSize) return FALSE;

	int nType		= EdgeTypeNone;
	double dLeft	= 0.0;
	double dRight	= 0.0;
	double dValue	= 0.0;

	UINT nPitchSize = nKernelSize/2;

	// push first pitch
	for (UINT i=0; i<nPitchSize; i++)
	{
		vectorEdgeData.push_back(0.0);
		vectorEdgeType.push_back(EdgeTypeNone);
	}

	// push center pitch
	for (UINT i=0; i<vectorImageData.size()-(nKernelSize); i++)
	{
		dLeft = dRight = 0.0;
		nType = EdgeTypeNone;

		for (UINT j=0; j<nPitchSize; j++)
		{
			dLeft	+= vectorImageData[i+j];
			dRight	+= vectorImageData[i+j+nPitchSize];
		}
		dLeft /= double(nPitchSize);
		dRight /= double(nPitchSize);

		dValue = dRight - dLeft;
		if (dValue >= dPositiveThres)
		{
			nType = EdgeTypePositive;
		}
		else if (dValue <= dNegativeThres )
		{
			nType = EdgeTypeNegative;
		}

		vectorEdgeData.push_back(dValue);
		vectorEdgeType.push_back(nType);
	}

	// push last pitch
	for (UINT i=0; i<nPitchSize; i++)
	{
		vectorEdgeData.push_back(0.0);
		vectorEdgeType.push_back(EdgeTypeNone);
	}

	return TRUE;
}

void CEdgeFind::CalculateEdgePosition(int nSubPixelType, double dPosiThres, double dNegaThres)
{
	m_vectorEdgeResult.clear();

	int nEdgeIndex = 0;
	int nEdgePosition = 0;
	int nEdgeType = EdgeTypeNone;
	double dEdgeValue = 0.0;
	double dEdgeThres = 0.0;

	if (nSubPixelType==SubPixelLinear)
	{
		for (UINT i=1; i<m_vectorEdgeType.size()-1; i++)
		{
			if (m_vectorEdgeType[i-1] == m_vectorEdgeType[i]) continue;

			switch(m_vectorEdgeType[i])
			{
			case EdgeTypeNone:
				nEdgePosition = i-1;
				nEdgeType = m_vectorEdgeType[nEdgePosition];
				dEdgeThres = (m_vectorEdgeType[nEdgePosition]==EdgeTypePositive) ? dPosiThres: dNegaThres;
				dEdgeValue = m_vectorEdgeData[nEdgePosition];
				break;
			case EdgeTypeNegative:
				nEdgePosition = i;
				nEdgeType = EdgeTypeNegative;
				dEdgeThres = dNegaThres;
				dEdgeValue = m_vectorEdgeData[i];
				break;
			case EdgeTypePositive:
				nEdgePosition = i;
				nEdgeType = EdgeTypePositive;
				dEdgeThres = dPosiThres;
				dEdgeValue = m_vectorEdgeData[i];
				break;
			} // end switch

			if (nEdgeType==EdgeTypeNone) continue;

			CEdgeResult edgeResult(nEdgeIndex, nEdgeType, nEdgePosition, dEdgeValue);

			if (CalculateInterpolateLinear(edgeResult, dEdgeThres))
			{
				if(edgeResult.dPosition >= 0 && edgeResult.dPosition <= m_vectorEdgeType.size()-1)
				{
					m_vectorEdgeResult.push_back(edgeResult);
					nEdgeIndex++;
				}
			}

		} // end for
	}
	else
	{
		for (UINT i=1; i<m_vectorEdgeType.size()-1; i++)
		{
			nEdgeType = EdgeTypeNone;

			switch(m_vectorEdgeType[i])
			{
			case EdgeTypePositive:
				{
					nEdgeType		= EdgeTypePositive;
					nEdgePosition	= i;
					dEdgeValue		= m_vectorEdgeData[i];

					for (UINT j=i+1; j<m_vectorEdgeType.size()-1; j++)
					{
						if (m_vectorEdgeType[j] != EdgeTypePositive) break;

						if (dEdgeValue < m_vectorEdgeData[j])
						{
							nEdgePosition	= j;
							dEdgeValue		= m_vectorEdgeData[j];
						}
						i = j;
					}
				}
				break;

			case EdgeTypeNegative:
				{
					nEdgeType		= EdgeTypeNegative;
					nEdgePosition	= i;
					dEdgeValue		= m_vectorEdgeData[i];

					for (UINT j=i+1; j<m_vectorEdgeType.size()-1; j++)
					{
						if (m_vectorEdgeType[j] != EdgeTypeNegative) break;

						if (dEdgeValue > m_vectorEdgeData[j])
						{
							nEdgePosition	= j;
							dEdgeValue		= m_vectorEdgeData[j];
						}
						i = j;
					}

				}
				break;
			} // end switch

			if (nEdgeType==EdgeTypeNone) continue;

			CEdgeResult edgeResult(nEdgeIndex, nEdgeType, nEdgePosition, dEdgeValue);

			switch(nSubPixelType)
			{
			case SubPixelQuadratic:
				if (CalculateInterpolateQuadratic(edgeResult))
				{
					m_vectorEdgeResult.push_back(edgeResult);
					nEdgeIndex++;
				}
				break;

			case SubPixelRegression:
				if (CalculateInterpolateRegression(edgeResult))
				{
					m_vectorEdgeResult.push_back(edgeResult);
					nEdgeIndex++;
				}
				break;
			} // end switch

		} // end for 
	}

}

BOOL CEdgeFind::CalculateInterpolateQuadratic(CEdgeResult& edgeResult)
{
	if (m_vectorEdgeData.size()<1) return FALSE;

	UINT i = 0;

	for (i=edgeResult.nEdgePosition-1; i>0; i--)
	{
		if (m_vectorEdgeType[i]!=edgeResult.nSignal) break;
		edgeResult.nLeftPosition = i;
	}

	for (i=edgeResult.nEdgePosition+1; i<m_vectorEdgeType.size(); i++)
	{
		if (m_vectorEdgeType[i]!=edgeResult.nSignal) break;
		edgeResult.nRightPosition = i;
	}

	// coef
	if (edgeResult.nLeftPosition==edgeResult.nEdgePosition) 
		edgeResult.nLeftPosition = edgeResult.nEdgePosition - 1;

	if (edgeResult.nRightPosition==edgeResult.nEdgePosition) 
		edgeResult.nRightPosition = edgeResult.nEdgePosition + 1;

	edgeResult.nLeftPosition = edgeResult.nEdgePosition - 1;
	edgeResult.nRightPosition = edgeResult.nEdgePosition + 1;

	// set 3 point
	VectorDouble vectorX; // x point
	vectorX.push_back(double(edgeResult.nLeftPosition));
	vectorX.push_back(double(edgeResult.nEdgePosition));
	vectorX.push_back(double(edgeResult.nRightPosition));

	VectorDouble vectorY; // y point
	vectorY.push_back(m_vectorEdgeData[edgeResult.nLeftPosition]);
	vectorY.push_back(m_vectorEdgeData[edgeResult.nEdgePosition]);
	vectorY.push_back(m_vectorEdgeData[edgeResult.nRightPosition]);

	// for debug
	/*	double vect[3][2];
	vect[0][0] = vectorX[0];
	vect[1][0] = vectorX[1];
	vect[2][0] = vectorX[2];
	vect[0][1] = vectorY[0];
	vect[1][1] = vectorY[1];
	vect[2][1] = vectorY[2];
	*/	
	ListPolynomial listPolynomial; // result polynomial

	// Lagrange equation
	if (!CalculateLagrange(vectorX, vectorY, listPolynomial))
	{
		return FALSE;
	}

	// get coef
	double a=0., b=0., c=0.;
	for (ListPolynomialIt it=listPolynomial.begin(); it!=listPolynomial.end(); it++)
	{
		CPolynomial *pCurrent = *it;

		if (pCurrent->dCoef!=0.0)
		{
			switch(pCurrent->nDegree)
			{
			case 2:
				a = pCurrent->dCoef;
				break;

			case 1:
				b = pCurrent->dCoef;
				break;

			case 0:
				c = pCurrent->dCoef;
				break;
			}
		}
	}

	//	PrintGraph(listPolynomial, edgeResult.nLeftPosition - edgeResult.nEdgePosition, edgeResult.nRightPosition - edgeResult.nEdgePosition);

	// remove polynomial
	RemovePolynomial(listPolynomial);

	// ¿ø·¡ À§Ä¡ º¹±Í.
	edgeResult.dPosition	= (-1.0 * b) / (2.0 * a);
	edgeResult.dStrength	= -1.0 * ( ( (b*b) - (4.0 * a * c) ) / (4.0 * a) );

	return TRUE;
}

BOOL CEdgeFind::CalculateInterpolateRegression(CEdgeResult& edgeResult)
{
	if (m_vectorEdgeData.size()<1) return FALSE;

	UINT i = 0;

	for (i=edgeResult.nEdgePosition-1; i>0; i--)
	{
		if (m_vectorEdgeType[i]!=edgeResult.nSignal) break;
		edgeResult.nLeftPosition = i;
	}

	for (i=edgeResult.nEdgePosition+1; i<m_vectorEdgeType.size(); i++)
	{
		if (m_vectorEdgeType[i]!=edgeResult.nSignal) break;
		edgeResult.nRightPosition = i;
	}

//	if ((edgeResult.nRightPosition-edgeResult.nLeftPosition)<2) return FALSE;

	VectorDouble srcX, srcY;
	for (i=(UINT)edgeResult.nLeftPosition; i<(UINT)edgeResult.nRightPosition+1; i++)
	{
		srcX.push_back(double(i));
		srcY.push_back(m_vectorEdgeData[i]);
	}

	double c, b, a;
	if (!QuadraticRegression(srcX, srcY, c, b, a))
	{
		return FALSE;
	}

	edgeResult.dPosition	= (-1.0 * b) / (2.0 * a);
	edgeResult.dStrength	= -1.0 * ( ( (b*b) - (4.0 * a * c) ) / (4.0 * a) );

	return TRUE;
}

BOOL CEdgeFind::CalculateInterpolateLinear(CEdgeResult& edgeResult, double dEdgeThreshold)
{
	UINT i = 0;

	int nPosition = edgeResult.nEdgePosition-1;
	double dPositionValue = m_vectorEdgeData[edgeResult.nEdgePosition-1];
	double dValue = m_vectorEdgeData[edgeResult.nEdgePosition];

	VectorDouble vectorX; // x point
	vectorX.push_back(double(edgeResult.nEdgePosition-1));
	vectorX.push_back(double(edgeResult.nEdgePosition));

	VectorDouble vectorY; // y point
	vectorY.push_back(m_vectorEdgeData[edgeResult.nEdgePosition-1]);
	vectorY.push_back(m_vectorEdgeData[edgeResult.nEdgePosition]);

	ListPolynomial listPolynomial; // result polynomial

	// Lagrange equation
	if (!CalculateLagrange(vectorX, vectorY, listPolynomial))
	{
		return FALSE;
	}

	// coef
	double a=0., b=0.;
	for (ListPolynomialIt it=listPolynomial.begin(); it!=listPolynomial.end(); it++)
	{
		CPolynomial *pCurrent = *it;

		if (pCurrent->dCoef!=0.0)
		{
			switch(pCurrent->nDegree)
			{
			case 1:
				a = pCurrent->dCoef;
				break;

			case 0:
				b = pCurrent->dCoef;
				break;
			}
		}
	}

	// remove polynomial
	RemovePolynomial(listPolynomial);

	if (edgeResult.nSignal==EdgeTypeNegative)
	{
		dEdgeThreshold *= -1.0;
	}

	edgeResult.dPosition	= (dEdgeThreshold-b) / a;
	edgeResult.dStrength	= dEdgeThreshold;

	return TRUE;
}

BOOL CEdgeFind::CalculateLagrange(VectorDouble& vectorX, VectorDouble& vectorY, ListPolynomial& listPolynomial)
{
	if (vectorX.size()<2) return FALSE;

	if (vectorX.size()!=vectorY.size()) return FALSE;

	int n = int(vectorX.size());

	int i, j;

	int sign;

	double coef, temp;

	for (i=0; i<n; i++)
	{
		if (!vectorY[i]) continue;

		coef = vectorY[i];

		for (j=0; j<n; j++)
		{
			if (i==j) continue;

			if (vectorX[i]==vectorX[j])
			{
				RemovePolynomial(listPolynomial);
				return FALSE;
			}

			coef /= vectorX[i] - vectorX[j];

		}

		temp = vectorX[i];
		vectorX[i] = 0;

		for (j=0; j<n; j++)
		{
			if (j%2)
			{
				sign = -1;
			}
			else
			{
				sign = 1;
			}

			InsertPolynomial(listPolynomial, n-j-1, sign*coef*Combi(vectorX, vectorY, n, j));
		}

		vectorX[i] = temp;
	}

	return TRUE;

}

void CEdgeFind::InsertPolynomial(ListPolynomial &listPolynomial, int degree, double coef)
{
	if (coef==0.0) return;

	CPolynomial *pNewPoly = new CPolynomial(degree, coef);

	BOOL bAdded = FALSE;

	for(ListPolynomialIt it=listPolynomial.begin(); it!= listPolynomial.end(); it++)
	{
		CPolynomial *pCurrent = *it;

		if (pCurrent->nDegree == pNewPoly->nDegree)
		{
			// ÇöÀç ³ëµå¿Í Â÷¼ö °°À¸¸é ÇöÀç ³ëµå¿¡ °è¼ö¸¦ ´õÇÏ°í, »ý¼º³ëµå´Â »èÁ¦ÇÑ´Ù.
			pCurrent->dCoef += pNewPoly->dCoef;
			delete pNewPoly;
			bAdded = TRUE;
			break;
		}
		else if (pCurrent->nDegree < pNewPoly->nDegree)
		{
			// ÇöÀç ¾Õ¿¡ »ðÀÔÇÑ´Ù.
			listPolynomial.push_front(pNewPoly);
			bAdded = TRUE;
			break;
		}
	}

	// ¾Õ¿¡¼­ Ãß°¡°¡ ¾ÈµÇ¾úÀ¸¸é, ¸ÇµÚ¿¡ »ðÀÔÇÑ´Ù.
	if (!bAdded)
	{
		listPolynomial.push_back(pNewPoly);
		return;
	}
}

void CEdgeFind::RemovePolynomial(ListPolynomial& listPolynomial)
{
/*	for(ListPolynomialIt it=listPolynomial.begin(); it!= listPolynomial.end(); it++)
	{
		CPolynomial *pNode = *it;

		//listPolynomial.erase(it);
		delete pNode;
	}
	listPolynomial.clear();	
*/

	ListPolynomialIt it = listPolynomial.begin();
	while (it != listPolynomial.end()) 
	{
		CPolynomial *pNode = *it;
		delete pNode;
		listPolynomial.erase(it++);
	}
	listPolynomial.clear();	
}

double CEdgeFind::Combi(VectorDouble& vectorX, VectorDouble& vectorY, int n, int r)
{
	int i;
	double result = 1;

	if (n<0 || r<0 || n<r) return 0.0;

	if (n==r)
	{
		for(i=0; i<n; i++)
		{
			result *= vectorX[i];
		}
		return result;
	}

	if (r!=0) 
	{
		return vectorX[n-1]*Combi(vectorX, vectorY, n-1, r-1)+Combi(vectorX, vectorY, n-1, r);
	}

	return 1.0;
}

BOOL CEdgeFind::QuadraticRegression(VectorDouble& vectorX, VectorDouble& vectorY, double& a0, double& a1, double& a2)
{
	double Y = std::accumulate(vectorY.begin(), vectorY.end(), 0.0);
	double X = std::accumulate(vectorX.begin(), vectorX.end(), 0.0);
	double X2 = std::accumulate(vectorX.begin(), vectorX.end(), 0.0, Square);
	double X3 = std::accumulate(vectorX.begin(), vectorX.end(), 0.0, Cubic);
	double X4 = std::accumulate(vectorX.begin(), vectorX.end(), 0.0, ForthPower);

	double K = 0.0;
	double L = 0.0;

	int i = 0;
	int n = (int)vectorX.size();

	for(i = 0; i<n; i++)
	{
		K += (vectorY[i] * vectorX[i] * vectorX[i]);
		L += (vectorY[i] * vectorX[i]);
	}

	double denominator = -n*X4*X2 + X4*X*X + X2*X2*X2 + X3*X3*n - 2*X3*X*X2;
	double b0p = -(Y*X4*X2 - Y*X3*X3 - X*L*X4 + X*X3*K - X2*X2*K + X2*X3*L);
	double b1p = X*Y*X4 - X*K*X2 - L*n*X4 + X3*n*K - Y*X2*X3 + X2*X2*L;
	double b2p = -(K*n*X2 - K*X*X - X2*X2*Y - X3*n*L + X3*X*Y + X*X2*L);

	a0 = b0p/denominator;
	a1 = b1p/denominator;
	a2 = b2p/denominator;

	return TRUE;
}

double CEdgeFind::Square(double init, double x)
{
	return init + x*x;
}

double CEdgeFind::Cubic(double init, double x)
{
	return init + x*x*x;
}

double CEdgeFind::ForthPower(double init, double x)
{
	return init + x*x*x*x;
}

double CEdgeFind::AbsSum(double init, double x)
{
	x = (x>0) ? x: -x;
	return init + x;
}

double CEdgeFind::Sum(double init, double x)
{
	return init + x;
}

BOOL CEdgeFind::GetEdgeLeftPosition(int nEdgeType, int nSearchType, int nStartPos, double& dPosition)
{
	if (m_vectorEdgeResult.size()<1) return FALSE;

	BOOL	bReturn		= FALSE;
	UINT	nWidth		= (UINT)m_vectorImageData.size();
	double	dValue		= -9999.0;
	int		nIndex		= -1;

	UINT i = 0;
	switch(nSearchType)
	{
	case SearchTypeOut2In:
		dPosition = 9999.;
		for (i=0; i<m_vectorEdgeResult.size(); i++)
		{
			if (m_vectorEdgeResult[i].nSignal != nEdgeType) continue;
			if (m_vectorEdgeResult[i].dPosition < nStartPos) continue;	

			if (m_vectorEdgeResult[i].dPosition < dPosition)
			{
				dValue		= m_vectorEdgeResult[i].dStrength;
				dPosition	= m_vectorEdgeResult[i].dPosition;
				bReturn		= TRUE;
				nIndex		= i;				
			}
		}
		break;

	case SearchTypeIn2Out:
		dPosition = -9999.;
		for (i=0; i<m_vectorEdgeResult.size(); i++)
		{
			if (m_vectorEdgeResult[i].nSignal != nEdgeType) continue;
			if (m_vectorEdgeResult[i].dPosition < nStartPos) continue;	

			if (m_vectorEdgeResult[i].dPosition > dPosition)
			{
				dValue		= m_vectorEdgeResult[i].dStrength;
				dPosition	= m_vectorEdgeResult[i].dPosition;
				bReturn		= TRUE;
				nIndex		= i;				
			}
		}
		break;

	case SearchTypeMinMax:
		dValue = 0.;
		for (i=0; i<m_vectorEdgeResult.size(); i++)
		{
			if (m_vectorEdgeResult[i].nSignal != nEdgeType) continue;
			if (m_vectorEdgeResult[i].dPosition < nStartPos) continue;	

			if ( fabs(dValue) < fabs(m_vectorEdgeResult[i].dStrength))
			{
				dValue		= m_vectorEdgeResult[i].dStrength;
				dPosition	= m_vectorEdgeResult[i].dPosition;
				bReturn		= TRUE;
				nIndex		= i;
			}
		}
		break;

	default:
		return FALSE;
	}

	if (nIndex!=-1)
		m_vectorEdgeResult[nIndex].nEdgeType = EdgeResultLeft;

	return bReturn;
}

BOOL CEdgeFind::GetEdgeRightPosition(int nEdgeType, int nSearchType, int nStartPos, double& dPosition)
{
	if (m_vectorEdgeResult.size()<1) return FALSE;

	BOOL	bReturn		= FALSE;
	UINT	nWidth		= (UINT)m_vectorImageData.size();
	double	dValue		= -9999.0;
	int		nIndex		= -1;

	UINT i = 0;
	switch(nSearchType)
	{
	case SearchTypeOut2In:
		dPosition = -9999.;
		for (i=0; i<m_vectorEdgeResult.size(); i++)
		{
			if (m_vectorEdgeResult[i].nSignal != nEdgeType) continue;
			if (m_vectorEdgeResult[i].dPosition < nStartPos) continue;	

			if (m_vectorEdgeResult[i].dPosition > dPosition)
			{
				dValue		= m_vectorEdgeResult[i].dStrength;
				dPosition	= m_vectorEdgeResult[i].dPosition;
				bReturn		= TRUE;
				nIndex		= i;
			}
		}
		break;

	case SearchTypeIn2Out:
		dPosition = 9999.;
		for (i=0; i<m_vectorEdgeResult.size(); i++)
		{
			if (m_vectorEdgeResult[i].nSignal != nEdgeType) continue;
			if (m_vectorEdgeResult[i].dPosition < nStartPos) continue;	

			if (m_vectorEdgeResult[i].dPosition < dPosition)
			{
				dValue		= m_vectorEdgeResult[i].dStrength;
				dPosition	= m_vectorEdgeResult[i].dPosition;
				bReturn		= TRUE;
				nIndex		= i;
			}
		}
		break;

	case SearchTypeMinMax:
		dValue = 0;
		for (i=0; i<m_vectorEdgeResult.size(); i++)
		{
			if (m_vectorEdgeResult[i].nSignal != nEdgeType) continue;
			if (m_vectorEdgeResult[i].dPosition < nStartPos) continue;	

			if ( fabs(dValue) < fabs(m_vectorEdgeResult[i].dStrength))
			{
				dValue		= m_vectorEdgeResult[i].dStrength;
				dPosition	= m_vectorEdgeResult[i].dPosition;
				bReturn		= TRUE;
				nIndex		= i;
			}
		}
		break;

	default:
		return FALSE;
	}

	if (nIndex!=-1)
		m_vectorEdgeResult[nIndex].nEdgeType = EdgeResultRight;

	return bReturn;
}