//-------------------------------------------------------------------------------------------------------+
// Copyright (C), 1998-2007, Beijing Tangent Software Co. Ltd.
// = FileName	:   TGPolygon2D 类
// = Version	:   ver2.0
// = Author		:   wlw
// = CreateDate	:   2002-09-09
// = Description:   TGPolygon2D 定义
// = Maintainers: 
//                  
//-------------------------------------------------------------------------------------------------------+
#include "StdAfx.h"
#include "TGPolygon2D.h"
#include "TGPolygonEx2D.h"
#include "TPtGraph.h"
#include "TPtList.h"
#include "TPtList2.h"
#include "TPDList.h"
#include "TGPoint2D.h"
#include "TGNPolygon2D.h"

IMPLEMENT_RUN_TIME_CLASS1(TGPolygon2D,"TGPolygon2D",TGRegion2D)

TGPolygon2D::TGPolygon2D(long vertexNum):mLine(vertexNum,true)
{

}

TGPolygon2D::TGPolygon2D(const TGMLine2D& ml,bool bCheck):mLine(ml)
{
	if (bCheck && mLine.IsClockwise())
	{
		mLine.Reverse();
	}
}

TGPolygon2D::~TGPolygon2D()
{

}

TGMLine2D&  TGPolygon2D::Outline() const
{
	return (TGMLine2D& )mLine;
}

bool TGPolygon2D::IsConcave() const
{
	return mLine.IsConcave();
}

TPGeCurve2D* TGPolygon2D::GetBoundary(long i) const
{
	return (TPGeCurve2D*)& mLine;
}

bool TGPolygon2D::IsValid() const
{
	return mLine.IsValid() && mLine.IsClosed() && !mLine.IsClockwise() && !mLine.IsSelfCross();
}

TGObject* TGPolygon2D::Clone() const
{
	return new TGPolygon2D(*this);
}

bool TGPolygon2D::Inter(const TGRegion2D&face,TGObjectList&res) const
{
	if (IS_TYPE(&face,TGPolygon2D))
	{
		return Inter((const TGPolygon2D&)face,res);
	}
	else
	{
		return face.Inter(*this,res);
	}
}

bool TGPolygon2D::Inter(const TGPolygon2D&poly,TGObjectList&res) const
{
	const TGMLine2D& mLine1 = poly.Outline();
	TPtGraph g;
	if (g.CreatePtGraphC(mLine,mLine1))
	{
		TPDList<TPtList> interList;
		g.MakeListIn(interList);
		if (!interList.IsEmpty())
		{
			for (interList.MoveToFirst();!interList.IsOut();interList.MoveToNext())
			{
				res << interList.GetCurData()->NewPolygon2D();
			}
			return true;
		}
	}

	for (long i = 0;i<mLine.GetVertexNum();i++)
	{
		GRelation r = mLine1.HitTest(mLine.GetVertex(i));
		if (r.Is(GR_INSIDE))
		{
			res << new TGPolygon2D(*this);
			return true;
		}
		else if (r.Is(GR_OUTSIDE))
		{
			break;
		}
	}
	if (i == mLine.GetVertexNum())
	{
		res << new TGPolygon2D(*this);
		return true;
	}

	for (i = 0;i<mLine1.GetVertexNum();i++)
	{
		GRelation r = mLine.HitTest(mLine1.GetVertex(i));
		if (r.Is(GR_INSIDE))
		{
			res << new TGPolygon2D(poly);
			return true;
		}
		else if (r.Is(GR_OUTSIDE))
		{
			break;
		}
	}
	if (i == mLine1.GetVertexNum())
	{
		res << new TGPolygon2D(poly);
		return true;
	}

	return false;
}

TGRegion2D* TGPolygon2D::Union(const TGRegion2D&face) const
{
	if (IS_TYPE(&face,TGPolygon2D))
	{
		return Union((const TGPolygon2D&)face);
	}
	else
	{
		return face.Union(*this);
	}
}

TGRegion2D* TGPolygon2D::Union(const TGPolygon2D&poly) const
{
	const TGMLine2D& mLine1 = poly.Outline();
	TPtGraph g;
	if (g.CreatePtGraphC(mLine,mLine1))
	{
		TPDList<TPtList> unionList;
		g.MakeListOut(unionList);
		if (unionList.GetLength() == 1)
		{
			return unionList(0).NewPolygon2D();
		}
		else if (unionList.GetLength()>1)
		{
			TGPolygonEx2D *pFace = new TGPolygonEx2D;
			int unclockCount = 0;
			for (long i = 0;i<unionList.GetLength();i++)
			{
				pFace->AppendHole(new TGMLine2D,false);
				long lastHole = pFace->GetHoleNum()-1;
				const TPtList*p = unionList[i];
				p->MakeMLine2D(pFace->Hole(lastHole));
				if (!pFace->Hole(lastHole).IsClockwise())
				{
					unclockCount++;
					if (unclockCount > 1)
					{
						delete pFace;
						return NULL;
					}
					pFace->DelHole(lastHole);
					p->MakeMLine2D(pFace->Outline());	
				}
			}
			return pFace;
		}
	}

	for (long i = 0;i<mLine.GetVertexNum();i++)
	{
		GRelation r = mLine1.HitTest(mLine.GetVertex(i));
		if (r.Is(GR_INSIDE))
		{
			return new TGPolygon2D(poly);
		}
		else if (r.Is(GR_OUTSIDE))
		{
			break;
		}
	}
	if (i == mLine.GetVertexNum())
	{
		return new TGPolygon2D(poly);
	}

	for (i = 0;i<mLine1.GetVertexNum();i++)
	{
		GRelation r = mLine.HitTest(mLine1.GetVertex(i));
		if (r.Is(GR_INSIDE))
		{
			return new TGPolygon2D(*this);
		}
		else if (r.Is(GR_OUTSIDE))
		{
			break;
		}
	}
	if (i == mLine1.GetVertexNum())
	{
		return new TGPolygon2D(*this);
	}

	return NULL;
}

void TGPolygon2D::SubtractBy(const TGRegion2D&face,TGObjectList&res) const
{
	switch(face.GetClassID())
	{
	case CID_GPolygon2D:
		SubtractBy((const TGPolygon2D&)face,res);
		break;
	case CID_GPolygonEx2D:
		SubtractBy((const TGPolygonEx2D&)face,res);
		break;
	default:
		TGRegion2D::SubtractBy(face,res);
	}
}

void TGPolygon2D::SubtractBy(const TGPolygon2D&poly,TGObjectList&res) const
{
	TPtGraph g;
	TGMLine2D mLine1 = poly.Outline();
	mLine1.Reverse();
	if (g.CreatePtGraphC(mLine,mLine1))
	{
		TPDList<TPtList> interList;
		g.MakeListIn(interList);
		if (!interList.IsEmpty())
		{
			if (interList.GetLength() != 2)
			{
				for (interList.MoveToFirst();!interList.IsOut();interList.MoveToNext())
				{
					res << interList.GetCurData()->NewPolygon2D();
				}
			}
			else
			{
				TGObjectList temp;
				for (interList.MoveToFirst();!interList.IsOut();interList.MoveToNext())
				{
					temp << interList.GetCurData()->NewPolygon2D();
				}
				
				temp.MoveToFirst();
				if (temp.GetCurRegion2D().Outline().IsClockwise())
				{
					TGPolygonEx2D *pFace = new TGPolygonEx2D(mLine,false);
					pFace->AppendHole(new TGMLine2D(mLine1),false);
					res << pFace;
					return;
				}

				temp.MoveToNext();
				if (temp.GetCurRegion2D().Outline().IsClockwise())
				{
					TGPolygonEx2D *pFace = new TGPolygonEx2D(mLine,false);
					pFace->AppendHole(new TGMLine2D(mLine1),false);
					res << pFace;
					return;
				}

				res.Conbine(temp);
			}
			return;
		}
	}

	for (long i = 0;i<mLine1.GetVertexNum();i++)
	{
		GRelation r = mLine.HitTest(mLine1.GetVertex(i));
		if (r.Is(GR_INSIDE))
		{
			TGPolygonEx2D *pFace = new TGPolygonEx2D(mLine,false);
			pFace->AppendHole(new TGMLine2D(mLine1),false);
			res << pFace;
			return;
		}
		else if (r.Is(GR_OUTSIDE))
		{
			break;
		}
	}

	for (long j = 0;j<mLine.GetVertexNum();j++)
	{
		GRelation r = mLine1.HitTest(mLine.GetVertex(j));
		if (r.Is(GR_INSIDE))
		{
			return;
		}
		else if (r.Is(GR_OUTSIDE))
		{
			break;
		}
	}

	if (i<mLine1.GetVertexNum() && j<mLine.GetVertexNum())
	{
		res << new TGPolygon2D(*this);
	}
}

void TGPolygon2D::SubtractBy(const TGPolygonEx2D* pPoly,TGObjectList&res) const
{
	ASSERT(pPoly != NULL);

	if (!pPoly->IsHoleExist())
	{
		SubtractBy((const TGPolygon2D&)pPoly,res);
		return;
	}

	SubtractBy((const TGPolygon2D&)pPoly,res);

	for (long i = 0; i < pPoly->GetHoleNum();i++)
	{
		TGPolygon2D *pHole = new TGPolygon2D(pPoly->Hole(i),false);
		pHole->Outline().Reverse();
		Inter(*pHole,res);
		delete pHole;
	}
}

void TGPolygon2D::CutBy(const TPGeCurve2D&curve,TGObjectList&left,TGObjectList&right) const
{
	if (!IS_TYPE(&curve,TPGeGLine2D))
	{
		TGRegion2D::CutBy(curve,left,right);
		return;
	}

	const TPGeGLine2D& line = (const TPGeGLine2D&)curve;
	TPtList2 *p = new TPtList2(mLine);
	TPtList2 *p0 = p;
	TPDList<TPtList2> lList,rList,mList;
	long segNum = mLine.GetSegNum();
	TPGeGLineSeg2D seg;
	double pa;
	for (long i = 0;i<segNum;i++,p = p->Next())
	{
		mLine.GetSegment(i,seg);
		TGObjectList oList;
		if (seg.Intersect(line,oList))
		{
			if (oList(0).GetClassID() == CID_GPoint2D)
			{
				const TGPoint2D&pt = (const TGPoint2D&)(oList(0));
				if (pt == seg.GetStartPoint())
				{
					TPtList2*p1 = new TPtList2(pt);
					line.Pt2Pa(pt,pa);
					p->pa = p1->pa = pa;
					p1->CNNext(p->Next());
					p->DCNNext();
					p = p1;
					if (line.IsVectorLeft(seg))
					{
						lList << p;
					}
					else
					{
						rList << p;
					}
				}
				else if (pt != seg.GetEndPoint())
				{
					TPtList2 *p1 = new TPtList2(pt),*p2 = new TPtList2(pt);
					line.Pt2Pa(pt,pa);
					p2->pa = p1->pa = pa;
					p1->CNNext(p->Next());
					p->CNNext(p2);
					p = p1;
					if (line.IsVectorLeft(seg))
					{
						lList << p;
					}
					else
					{
						rList << p;
					}
				}
			}
			else
			{	
				GRelation r;
				if (i == 0)
				{
					r = line.HitTest(mLine.GetVertex(segNum-1));
				}
				else
				{
					r = line.HitTest(mLine.GetVertex(i-1));
				}
				if (r.IsNot(GR_IN))
				{
					TPtList2 *p1 = new TPtList2(mLine.GetVertex(i));
					p1->CNNext(p->Next());
					p->DCNNext();
					line.Pt2Pa(mLine.GetVertex(i),pa);
					p->pa = pa;
					p = p1;
					mList << p;
				}
			}
		}
	}
	if (rList.IsEmpty() && lList.IsEmpty())
	{
		if (line.HitTest(mLine.GetVertex(0)).Is(GR_LEFT))
		{
			lList << p0;
		}
		else
		{
			rList << p0;
		}
	}
	else
	{   
		TPDList<TPtList2> rList1,lList1;
		for (rList.MoveToFirst();!rList.IsOut();rList.MoveToNext())
		{
			rList1 << rList.GetCurData()->GetTail();
		}
		for (lList.MoveToFirst();!lList.IsOut();lList.MoveToNext())
		{
			lList1 << lList.GetCurData()->GetTail();
		}

		rList.Arrange();
		lList.Arrange();
		rList1.Arrange();
		lList1.Arrange();
		for (rList.MoveToFirst(),rList1.MoveToFirst();!rList.IsOut();rList.MoveToNext(),rList1.MoveToNext())
		{
			TPtList2 *p1 = rList1.FetchCur(),*p2 = rList.GetCurData();
			if (*p1 == *p2)
			{
				p1->CNNext(p2->Next());
				p2->DCNNext();
				delete p2;
				rList.SetCurData(p1);
			}
			else
			{
				p1->CNNext(p2);
			}
		}
		for (lList.MoveToFirst(),lList1.MoveToFirst();!lList.IsOut();lList.MoveToNext(),lList1.MoveToNext())
		{
			TPtList2 *p1 = lList1.FetchCur(),*p2 = lList.GetCurData();
			if (*p1 == *p2)
			{
				p1->CNNext(p2->Next());
				p2->DCNNext();
				delete p2;
				lList.SetCurData(p1);
			}
			else
			{
				p1->CNNext(p2);
			}
		}
	}

	for (rList.MoveToFirst();!rList.IsOut();rList.MoveToNext())
	{
		TPtList2 &pt = rList.GetCurPData();
		if (pt.Is(VISITED))
		{
			rList.FetchCur();
		}
		else
		{
			right << pt.NewPolygon2D();
			pt.SetAllFlag(VISITED);
		}
	}

	for (lList.MoveToFirst();!lList.IsOut();lList.MoveToNext())
	{
		TPtList2 &pt = lList.GetCurPData();
		if (pt.Is(VISITED))
		{
			lList.FetchCur();
		}
		else
		{
			left << pt.NewPolygon2D();
			pt.SetAllFlag(VISITED);
		}
	}
}

bool TGPolygon2D::Explode(TGObjectList&oList) const
{
	if (mLine.GetSegNum() > 3)
	{
		TGVector2D vt1(mLine.GetVertex(mLine.GetVertexNum()-1),mLine.GetVertex(0));
		bool bUp = false,bDown = false;
		for (long i = 0;i<mLine.GetVertexNum();i++)
		{
			TGVector2D vt2(mLine.GetVertex(i),mLine.GetVertex((i+1)%mLine.GetVertexNum()));
			double temp = vt1*vt2;
			if (DOWN_ZERO(temp))
			{
				bDown = true;
			}
			else if (UP_ZERO(temp))
			{
				bUp = true;
			}
			if (bUp && bDown)
			{
				TPGeGLine2D line(vt1,mLine.GetVertex(i));
				TGObjectList buf;
				CutBy(line,buf,buf);
				for (buf.MoveToFirst();!buf.IsOut();buf.MoveToNext())
				{
					(const TGPolygon2D*)(buf.GetCurData())->Explode(oList);
				}
				return true;
			}
			vt1 = vt2;
		}
	}
	oList << new TGNPolygon2D(mLine,false);
	return true;
}

TGPoint TGPolygon2D::Center() const
{
	TGPoint pt;
	for (long i = 0;i<mLine.GetVertexNum();i++)
	{
		pt += mLine.GetVertex(i);
	}

	pt /= mLine.GetVertexNum();
	return pt;
}