#include "StdAfx.h"
#include "TriangleCreator.h"
#include <float.h>
#include <math.h>

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
CBorder::CBorder()
{
	m_iTriangleIndex=-1;
	m_byteBorderIndex=255;
	m_byteFlag=0;
}
void CBorder::ClearFlag()
{
	m_byteFlag=0;
}
void CBorder::SetFlag(BYTE byteFlag)
{
	m_byteFlag=byteFlag;
}
BYTE CBorder::GetFlag()
{
	return m_byteFlag;
}
BOOL CBorder::IsValid()
{
	return m_iPointIndex0!=INT_MAX && m_iPointIndex1!=INT_MAX;
}
void CBorder::Reverse()
{
	int iPointIndex=m_iPointIndex0;
	m_iPointIndex0=m_iPointIndex1;
	m_iPointIndex1=iPointIndex;
}
int CBorder::GetPointIndex(BYTE byteIndex)
{
	if(byteIndex==0)
		return m_iPointIndex0;
	else
		return m_iPointIndex1;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
CTriangle::CTriangle()
{
	m_byteFlag=0;

}
void CTriangle::ClearNeighbors()
{
	m_Border[0].m_iTriangleIndex=-1;
	m_Border[1].m_iTriangleIndex=-1;
	m_Border[2].m_iTriangleIndex=-1;
}
void CTriangle::ClearNeighbor(BYTE byteBorderIndex)
{
	m_Border[byteBorderIndex].m_iTriangleIndex=-1;
}
void CTriangle::SetNeighbor(BYTE byteBorderIndex,int iNeighborTriangleIndex,BYTE byteNeighborBorderIndex1)
{
	m_Border[byteBorderIndex].m_iTriangleIndex=iNeighborTriangleIndex;
	m_Border[byteBorderIndex].m_byteBorderIndex=byteNeighborBorderIndex1;
}
BOOL CTriangle::IsSameBorder(BYTE byteBorderIndex,CTriangle& triangle,BYTE byteBorderIndex1)
{
	int i0,i1;
	GetBorderPointIndex(byteBorderIndex,i0,i1);

	int j0,j1;
	
	triangle.GetBorderPointIndex(byteBorderIndex1,j0,j1);

	ASSERT(!(i0==j0 && i1==j1));

	return i0==j1 && i1==j0;
}
void CTriangle::ClearBorderFlag()
{
	m_Border[0].ClearFlag();
	m_Border[1].ClearFlag();
	m_Border[2].ClearFlag();
}
void CTriangle::SetBorderFlag(BYTE byteBorderIndex,BYTE byteFlag)
{
	m_Border[byteBorderIndex].SetFlag(byteFlag);
}
BYTE CTriangle::GetBorderFlag(BYTE byteBorderIndex)
{
	return m_Border[byteBorderIndex].GetFlag();
}
CBorder* CTriangle::GetBorder(BYTE byteBorderIndex)
{
	return m_Border+byteBorderIndex;
}
void CTriangle::GetPointIndex(int* piPointIndex)
{
	piPointIndex[0]=m_Border[0].m_iPointIndex0;
	piPointIndex[1]=m_Border[1].m_iPointIndex0;
	piPointIndex[2]=m_Border[2].m_iPointIndex0;
}
int CTriangle::GetPointIndex(BYTE byteNodeIndex)
{
	return m_Border[byteNodeIndex].m_iPointIndex0;
}
void CTriangle::SetPointIndex(BYTE byteNodeIndex,int iPointIndex)
{
	m_Border[byteNodeIndex].m_iPointIndex0=iPointIndex;
	m_Border[(byteNodeIndex+2)%3].m_iPointIndex1=iPointIndex;
}
void CTriangle::GetBorderPointIndex(BYTE byteBorderIndex,int& iPointIndex0,int& iPointIndex1)
{
	iPointIndex0=m_Border[byteBorderIndex].m_iPointIndex0;
	iPointIndex1=m_Border[byteBorderIndex].m_iPointIndex1;
}
void CTriangle::GetNeighbor(BYTE byteBorderIndex,int& iNeighborTriangleIndex,BYTE& byteNeighborBorderIndex)
{
	iNeighborTriangleIndex=m_Border[byteBorderIndex].m_iTriangleIndex;
	byteNeighborBorderIndex=m_Border[byteBorderIndex].m_byteBorderIndex;
}
void CTriangle::SetFlag()
{
	m_byteFlag=1;
}
BOOL CTriangle::GetFlag()
{
	return m_byteFlag>0;
}
void CTriangle::ClearFlag()
{
	m_byteFlag=0;
}
void CTriangle::operator=(CTriangle& triangle)
{
	memcpy(this,&triangle,sizeof(CTriangle));
}

CTriangleCreator::CTriangleCreator()
{

}
CTriangleCreator::~CTriangleCreator()
{

}
void CTriangleCreator::AddPoint(double x,double y)
{
	WPOINT p;
	p.x=x;
	p.y=y;
	m_PointArray.Add(p);
}
int CTriangleCreator::GetPointCount()
{
	return (int)m_PointArray.GetCount();
}
WPOINT* CTriangleCreator::GetPointArray()
{
	return m_PointArray.GetData();
}
void CTriangleCreator::CreateTriangle(double dLimitAngle)
{
	m_TriangleArray.RemoveAll();

	WPOINT* pPointArray=m_PointArray.GetData();
	int iPointCount=(int)m_PointArray.GetSize();

	if(iPointCount<3)
		return;

	double dLimit=cos(dLimitAngle*3.1415926/180.0);

	for(int i=0;i<iPointCount;i++)
		pPointArray[i].flag=0;

	CBorder border;
	CTriangle triangle;

	int index0=-1;
	int index1=-1;

	double d=FLT_MAX;
	for(int i=0;i<iPointCount;i++)
	{
		int k; for(k=i+1;k<iPointCount;k++)
		{
			double dx=pPointArray[k].x-pPointArray[0].x;
			double dy=pPointArray[k].y-pPointArray[0].y;

			double dd=sqrt(dx*dx+dy*dy);
			if(dd<d)
			{
				d=dd;
				index0=i;
				index1=k;
			}
		}
	}

	//先構造一個初始的三角形
	triangle.SetPointIndex(0,index0);
	triangle.SetPointIndex(1,index1);
	triangle.SetPointIndex(2,index0);

	m_TriangleArray.SetSize(iPointCount);
	m_TriangleArray.RemoveAll();

	m_TriangleArray.Add(triangle);

	CArray<CBorder,CBorder> BorderIndexArray;

	border.m_iTriangleIndex=(int)m_TriangleArray.GetSize()-1;
	border.m_byteBorderIndex=0;
	border.m_iPointIndex0=index0;
	border.m_iPointIndex1=index1;
	BorderIndexArray.Add(border);

	border.m_iTriangleIndex=(int)m_TriangleArray.GetSize()-1;
	border.m_byteBorderIndex=1;
	border.m_iPointIndex0=index1;
	border.m_iPointIndex1=index0;
	BorderIndexArray.Add(border);

	WPOINT fp0,fp1;

	int iStartSearchIndex=0;

	//擴充輪廓 
	while(TRUE) 
	{
		int iBorderCount=(int)BorderIndexArray.GetSize();
		int iTriangleCount=(int)m_TriangleArray.GetSize();
		CBorder* pBorderArray=BorderIndexArray.GetData();
		CTriangle* pTriangleArray=m_TriangleArray.GetData();

		double dAngle=FLT_MAX;
		int iBorderIndex=-1;
		int iPointIndex=-1;//新找到的點序號
		int iPointIndex0,iPointIndex1;//原來的點序號

		if(iStartSearchIndex>=iBorderCount) iStartSearchIndex=0;
		int i; for(i=0;i<iBorderCount;i++)
		{
			int ii=i+iStartSearchIndex;
			if(ii>=iBorderCount) ii-=iBorderCount;

			if(pBorderArray[ii].GetFlag()) continue;

			border=pBorderArray[ii];

			pTriangleArray[border.m_iTriangleIndex].GetBorderPointIndex(border.m_byteBorderIndex,iPointIndex0,iPointIndex1);

			ASSERT(iPointIndex0>=0);
			ASSERT(iPointIndex1>=0);

			fp0=pPointArray[iPointIndex0];
			fp1=pPointArray[iPointIndex1];

			double dy=fp1.y-fp0.y;
			double dx=fp1.x-fp0.x;
			double xy=fp0.y*fp1.x-fp0.x*fp1.y;
			double cc=dx*dx+dy*dy;
			double c=sqrt(cc);

			dAngle=FLT_MAX;
			iPointIndex=-1;

			int j; 
			for(j=0;j<iPointCount;j++)
			{
				if(j==iPointIndex0 || j==iPointIndex1) continue;

				if(pPointArray[j].x==FLT_MAX) continue;
				if(pPointArray[j].flag!=0) continue;

				double d=dy*pPointArray[j].x-dx*pPointArray[j].y+xy;
				if(d>=-0.1) continue;//只考慮fp0,fp1左側的點

				double dxa=pPointArray[j].x-fp1.x;
				double dya=pPointArray[j].y-fp1.y;
				double aa=dxa*dxa+dya*dya;
				double a=sqrt(aa);

				double dxb=pPointArray[j].x-fp0.x;
				double dyb=pPointArray[j].y-fp0.y;
				double bb=dxb*dxb+dyb*dyb;
				double b=sqrt(bb);

				//				ASSERT(aa>0.0 && bb>0.0);

				double cosc;

				if(a==0.0 || b==0.0)
				{
					cosc=-1.0;
				}
				else
					cosc=(aa+bb-cc)/a/b/2.0;

				if(cosc<dAngle)