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

IMPLEMENT_RUN_TIME_CLASS1(TGPolygonEx2D,"TGPolygonEx2D",TGPolygon2D)

TGPolygonEx2D::TGPolygonEx2D(long vertexNum):TGPolygon2D(vertexNum)
{

}

TGPolygonEx2D::TGPolygonEx2D(const TGMLine2D&ml,bool bCheck/* = true*/):TGPolygon2D(ml,bCheck)
{

}

TGPolygonEx2D::TGPolygonEx2D(const TGPolygon2D&poly):TGPolygon2D(poly)
{

}

TGPolygonEx2D::~TGPolygonEx2D()
{

}

TGMLine2D& TGPolygonEx2D::Hole(long i) const
{
	return (TGMLine2D&)(*hole.GetAt(i));
}

void TGPolygonEx2D::DelHole(long i)
{
	hole.Del(i);
}

TGMLine2D* TGPolygonEx2D::FetchHole(long i)
{
	return hole.Fetch(i);
}

void TGPolygonEx2D::ClearHole()
{
	hole.Clear();
}

TPGeCurve2D* TGPolygonEx2D::GetBoundary(long i) const
{
	return (TPGeCurve2D*)(i == 0?&mLine:hole.GetAt(i-1));
}

long TGPolygonEx2D::GetBoundaryNum() const
{
	return hole.GetLength()+1;
}

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

bool TGPolygonEx2D::IsValid() const
{	
	if (!TGPolygon2D::IsValid())
	{
		return false;
	}

	if (!IsHoleExist())
	{
		return true;
	}
	
	TGObjectList holes;
	for (long i = 0;i<hole.GetLength();i++)
	{
		if (hole.IsEmptyData(i))
		{
			return false;
		}

		const TGMLine2D*pHole = hole.GetAt(i);
		if (!pHole->IsValid() || !pHole->IsClosed() || pHole->IsSelfCross() || !pHole->IsClockwise())
		{
			return false;
		}

		if (!TGPolygon2D::IsInclude(*pHole))
		{
			return false;
		}

		TGPolygon2D*pPoly = new TGPolygon2D(*pHole,false);
		pPoly->Outline().Reverse();
		holes << pPoly;
	}

	
	TGObjectList buf;
	while(holes.GetLength() > 1)
	{
		TGRegion2D *pFirst = (TGRegion2D*)(holes.Fetch(0));
		buf << pFirst;
		for (holes.MoveToFirst();!holes.IsOut();holes.MoveToNext())
		{
			if (pFirst->Inter((const TGRegion2D&)(holes.GetCurPData()),buf))
			{
				return false;
			}
		}
	}
	return IsAllowBoundaryInter()?true:!IsBoundaryInter();
}

bool TGPolygonEx2D::AppendHole(TGMLine2D *pMl,bool bCheck)
{
	if (bCheck)
	{
		if (!IsAllowBoundaryInter())
		{
			TGObjectList oList;
			for (long i = 0;i<GetBoundaryNum();i++)
			{
				if (GetBoundary(i)->Intersect(*pMl,oList))
				{
					delete pMl;
					return false;
				}
			}
		}
		if (pMl->IsClockwise())
		{
			pMl->Reverse();
		}
		if (!IsInclude(TGPolygon2D(*pMl,false)))
		{
			delete pMl;
			return false;
		}
		pMl->Reverse();
	}
	hole.AddTail(pMl);
	return true;
}

TGPolygonEx2D::TGPolygonEx2D(const TGPolygonEx2D& poly):TGPolygon2D(poly)
{
	long num = poly.GetHoleNum();
	for (long i = 0;i<num;i++)
	{
		hole.AddTail((TGMLine2D*)poly.Hole(i).Clone());
	}
}

bool TGPolygonEx2D::Inter(const TGRegion2D&face,TGObjectList&res) const
{
	switch(face.GetClassID())
	{
	case CID_GPolygon2D:
		return Inter((const TGPolygon2D&)face,res);
	case CID_GPolygonEx2D:
		return Inter((const TGPolygonEx2D&)face,res);
	default:
		return TGRegion2D::Inter(face,res);
	}
}

bool TGPolygonEx2D::Inter(const TGPolygon2D&poly,TGObjectList&res) const
{
	if (!IsHoleExist())
	{
		return TGPolygon2D::Inter(poly,res);
	}

	TGObjectList buf;
	if (!TGPolygon2D::Inter(poly,buf))
	{
		return false;
	}

	TGObjectList holes,buf1;
	for (long i = 0;i<GetHoleNum();i++)
	{
		holes << new TGPolygon2D(Hole(i),false);
		holes.GetCurRegion2D().Outline().Reverse();
	}
	for (buf.MoveToFirst();!buf.IsOut();buf.MoveToNext())
	{
		buf.GetCurRegion2D().SubtractBy(holes,buf1);
	}

	if (buf1.IsEmpty())
	{
		return false;
	}
	else
	{
		res.Conbine(buf1);
		return true;
	}
}

bool TGPolygonEx2D::Inter(const TGPolygonEx2D&poly,TGObjectList&res) const
{
	if (!IsHoleExist())
	{
		return poly.Inter(((const TGPolygon2D&)(*this)),res);
	}

	TGObjectList buf;
	if (!poly.Inter(((const TGPolygon2D&)(*this)),buf))
	{
		return false;
	}

	TGObjectList holes,buf1;
	for (long i = 0;i<GetHoleNum();i++)
	{
		holes << new TGPolygon2D(Hole(i),false);
		holes.GetCurRegion2D().Outline().Reverse();
	}

	for (buf.MoveToFirst();!buf.IsOut();buf.MoveToNext())
	{
		buf.GetCurRegion2D().SubtractBy(holes,buf1);
	}

	if (buf1.IsEmpty())
	{
		return false;
	}
	else
	{
		res.Conbine(buf1);
		return true;
	}
}

TGRegion2D* TGPolygonEx2D::Union(const TGRegion2D&face) const
{
	switch(face.GetClassID())
	{
	case CID_GPolygon2D:
		return Union((const TGPolygon2D&)face);
	case CID_GPolygonEx2D:
		return Union((const TGPolygonEx2D&)face);
	default:
		return TGRegion2D::Union(face);
	}
}

TGRegion2D * TGPolygonEx2D::Union(const TGPolygon2D&poly) const
{
	if (!IsHoleExist())
	{
		return TGPolygon2D::Union(poly);
	}

	TGRegion2D *pU0 = TGPolygon2D::Union(poly);
	if (pU0 == NULL)
	{
		return NULL;
	}

	TGObjectList holes;
	for (long i = 0;i<GetHoleNum();i++)
	{	
		TGPolygon2D* pHole = new TGPolygon2D(Hole(i),false);
		pHole->Outline().Reverse();
		pHole->SubtractBy(poly,holes);
		delete pHole;
	}
	
	if (holes.IsEmpty())
	{
		return pU0;
	}
	else
	{
		TGPolygonEx2D*pU1;
		if (pU0->GetClassID() == CID_GPolygonEx2D)
		{
			pU1 = (TGPolygonEx2D*)pU0;
		}
		else
		{
			pU1 = new TGPolygonEx2D((const TGPolygon2D&)(*pU0));
			delete pU0;
		}

		for (holes.MoveToFirst();!holes.IsOut();holes.MoveToNext())
		{
			TGPolygon2D*pHole = (TGPolygon2D*)(holes.GetCurData());
			if (pHole->IsHoleExist())
			{
				delete pU1;
				return NULL;
			}

			TGMLine2D*pMLine = new TGMLine2D(pHole->Outline());
			pMLine->Reverse();
			pU1->AppendHole(pMLine,false);
		}
		return pU1;
	}
}

TGRegion2D * TGPolygonEx2D::Union(const TGPolygonEx2D&poly) const
{
	if (!IsHoleExist())
	{
		return poly.Union((const TGPolygon2D&)(*this));
	}
	else if (!poly.IsHoleExist())
	{
		return Union((const TGPolygon2D&)(poly));
	}

	TGRegion2D *pU0 = TGPolygon2D::Union((const TGPolygon2D&)poly);
	if (pU0 == NULL)
	{
		return NULL;
	}

	TGObjectList holes;
	for (long i = 0;i<GetHoleNum();i++)
	{	
		TGPolygon2D* pHole = new TGPolygon2D(Hole(i),false);
		pHole->Outline().Reverse();
		pHole->SubtractBy(poly,holes);
		delete pHole;
	}

	for (i = 0;i<poly.GetHoleNum();i++)
	{	
		TGPolygon2D* pHole = new TGPolygon2D(poly.Hole(i),false);
		pHole->Outline().Reverse();
		pHole->SubtractBy(*this,holes);
		delete pHole;
	}
	
	if (holes.IsEmpty())
	{
		return pU0;
	}
	else
	{
		holes.RemoveSubObj();

		TGPolygonEx2D*pU1;
		if (pU0->GetClassID() == CID_GPolygonEx2D)
		{
			pU1 = (TGPolygonEx2D*)pU0;
		}
		else
		{
			pU1 = new TGPolygonEx2D((const TGPolygon2D&)(*pU0));
			delete pU0;
		}

		for (holes.MoveToFirst();!holes.IsOut();holes.MoveToNext())
		{
			TGPolygon2D*pHole = (TGPolygon2D*)(holes.GetCurData());
			if (pHole->IsHoleExist())
			{
				delete pU1;
				return NULL;
			}
			TGMLine2D*pMLine = new TGMLine2D(pHole->Outline());
			pMLine->Reverse();
			pU1->AppendHole(pMLine,false);
		}
		return pU1;
	}
}

void TGPolygonEx2D::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 TGPolygonEx2D::SubtractBy(const TGPolygon2D&poly,TGObjectList&res) const
{
	if (!IsHoleExist())
	{
		TGPolygon2D::SubtractBy(poly,res);
		return;
	}

	TGObjectList buf;
	TGPolygon2D::SubtractBy(poly,buf);
	if (buf.IsEmpty())
	{
		return;
	}

	TGObjectList holes;
	for (long i = 0;i<GetHoleNum();i++)
	{
		holes << new TGPolygon2D(Hole(i),false);
		holes.GetCurRegion2D().Outline().Reverse();
	}

	buf.MoveToFirst();
	if (buf.GetCurRegion2D().IsHoleExist())
	{
		holes.Union(poly);

		TGPolygonEx2D *pRes = (TGPolygonEx2D*)buf.FetchCur();
		pRes->ClearHole();
		for (holes.MoveToFirst();!holes.IsOut();holes.MoveToNext())
		{
			TGMLine2D* pMLine = (TGMLine2D*)(holes.GetCurRegion2D().Outline().Clone());
			pMLine->Reverse();
			pRes->AppendHole(pMLine,false);
		}
		res << pRes;
	}
	else
	{
		for (buf.MoveToFirst();!buf.IsOut();buf.MoveToNext())
		{
			buf.GetCurRegion2D().SubtractBy(holes,res);
		}
	}
}

void TGPolygonEx2D::SubtractBy(const TGPolygonEx2D&poly,TGObjectList&res) const
{
	if (!IsHoleExist())
	{
		TGPolygon2D::SubtractBy(poly,res);
		return;
	}

	TGObjectList buf;
	TGPolygon2D::SubtractBy(poly,buf);
	if (buf.IsEmpty())
	{
		return;
	}

	TGObjectList holes;
	for (long i = 0;i<GetHoleNum();i++)
	{
		holes << new TGPolygon2D(Hole(i),false);
		holes.GetCurRegion2D().Outline().Reverse();
	}
	for (buf.MoveToFirst();!buf.IsOut();buf.MoveToNext())
	{
		buf.GetCurRegion2D().SubtractBy(holes,res);
	}
}

void TGPolygonEx2D::QuickCutBy(const TPGeGLine2D&line,TGObjectList&left,TGObjectList&right) const
{
	if (!IsHoleExist())
	{
		TGPolygon2D::CutBy(line,left,right);
		return;
	}

	TArray<TGMLine2D*> mLines;
	mLines.Realloc(GetHoleNum() + 1, false);
	mLines[0] = (TGMLine2D*)(&mLine);
	for (long i = 1;i<mLines.GetLength();i++)
	{
		mLines[i] = &(Hole(i - 1));
	}

	TPDList<TPtList2> lList,rList;
	TList<TGMLine2D*> lHoleList,rHoleList;
	TPGeGLineSeg2D seg;
	double pa;
	
	for (long lCount = 0;lCount<mLines.GetLength();lCount++)
	{
		
		TGMLine2D&ml = (*mLines[lCount]);
		TPtList2 *p = new TPtList2(ml);
		TPtList2 *p0 = p;
		TPDList<TPtList2> lList1,rList1,mList1;
		long segNum = ml.GetSegNum();
		for (long i = 0;i<segNum;i++,p = p->Next())
		{
			seg.SetPoint(p->Data(),p->Next()->Data());
			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))
						{
							lList1 << p;
						}
						else
						{
							rList1 << 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))
						{
							lList1 << p;
						}
						else
						{
							rList1 << p;
						}
					}
				}
				else
				{	
					GRelation r;
					if (i == 0)
					{
						r = line.HitTest(ml.GetVertex(segNum - 1));
					}
					else
					{
						r = line.HitTest(ml.GetVertex(i - 1));
					}
					if (r.IsNot(GR_IN))
					{
						TPtList2 *p1 = new TPtList2(ml.GetVertex(i));
						p1->CNNext(p->Next());
						p->DCNNext();
						line.Pt2Pa(ml.GetVertex(i),pa);
						p->pa = pa;
						p = p1;
						mList1 << p;
					}
				}
			}
		}
		if (rList1.IsEmpty()&&lList1.IsEmpty())
		{
			delete p0;
			GRelation r = GR_IN;
			for (long j = 0;r.Is(GR_IN);j++)
			{
				r = line.HitTest(ml.GetVertex(j));
			}
			if (lCount == 0)
			{
				if (r.Is(GR_LEFT))
				{
					left << new TGPolygonEx2D(*this);
				}
				else
				{
					right << new TGPolygonEx2D(*this);
				}
				return;
			}
			else
			{
				if (r.Is(GR_LEFT))
				{
					lHoleList << &ml;
				}
				else
				{
					rHoleList << &ml;
				}
			}
		}
		else if (mList1.IsEmpty())
		{
			if (rList1.IsEmpty())
			{
				if (lCount == 0)
				{
					left << new TGPolygonEx2D(*this);
					return;
				}
				else
				{
					lHoleList << &ml;
				}
			}
			else if (lList1.IsEmpty())
			{
				if (lCount == 0)
				{
					right << new TGPolygonEx2D(*this);
					return;
				}
				else
				{
					rHoleList << &ml;
				}
			}
			else
			{
				rList.Conbine(rList1);
				lList.Conbine(lList1);
			}
		}
		else
		{
			rList.Conbine(rList1);
			lList.Conbine(lList1);
		}
	}

	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
		{
			TGPolygonEx2D *pFace = pt.NewLFace2D();
			pt.SetAllFlag(VISITED);
			right << pFace;
			for (rHoleList.MoveToFirst();!rHoleList.IsOut();rHoleList.MoveToNext())
			{
				if (pFace->AppendHole(new TGMLine2D(*rHoleList.GetCurData())))
				{
					rHoleList.DelCur();
				}
			}
		}
	}
	for (lList.MoveToFirst();!lList.IsOut();lList.MoveToNext())
	{
		TPtList2 &pt = lList.GetCurPData();
		if (pt.Is(VISITED))
		{
			lList.FetchCur();
		}
		else
		{
			TGPolygonEx2D *pFace = pt.NewLFace2D();
			pt.SetAllFlag(VISITED);
			left << pFace;
			for (lHoleList.MoveToFirst();!lHoleList.IsOut();lHoleList.MoveToNext())
			{
				if (pFace->AppendHole(new TGMLine2D(*lHoleList.GetCurData())))
				{
					lHoleList.DelCur();
				}
			}
		}
	}
}

void TGPolygonEx2D::CutBy(const TPGeCurve2D&curve,TGObjectList&left,TGObjectList&right) const
{
	if (!IS_TYPE(&curve,TPGeGLine2D))
	{
		TGRegion2D::CutBy(curve,left,right);
	}
	else if (IsMayBoundaryInter())
	{
		TGObjectList lBuf,rBuf;
		TGPolygon2D::CutBy(curve,lBuf,rBuf);
		if (lBuf.IsEmpty())
		{
			right << new TGPolygonEx2D(*this);
		}
		else if (rBuf.IsEmpty())
		{
			left << new TGPolygonEx2D(*this);
		}
		else
		{
			TGObjectList lHole,rHole;
			for (long i = 0;i<GetHoleNum();i++)
			{
				TGPolygon2D poly(Hole(i),false);
				poly.Outline().Reverse();
				poly.CutBy(curve,lHole,rHole);
			}

			for (lBuf.MoveToFirst();!lBuf.IsOut();lBuf.MoveToNext())
			{
				lBuf.GetCurRegion2D().SubtractBy(lHole,left);
			}
			for (rBuf.MoveToFirst();!rBuf.IsOut();rBuf.MoveToNext())
			{
				rBuf.GetCurRegion2D().SubtractBy(rHole,right);
			}
		}
	}
	else
	{
		QuickCutBy((const TPGeGLine2D&)curve,left,right);
	}
}

bool TGPolygonEx2D::Explode(TGObjectList&res) const
{
	if (!IsHoleExist())
	{
		res << new TGPolygon2D(*this);
		return true;
	}

	TPGeGLine2D line;
	TGObjectList lBuf,rBuf;
	const TGMLine2D&ml = Hole(0);
	for (long i = 0;i<ml.GetSegNum();i++)
	{
		ml.GetSegment(i,line);
		CutBy(line,lBuf,rBuf);
		if (!lBuf.IsEmpty())
		{
			break;
		}
		else
		{
			rBuf.Clear();
		}
	}

	lBuf.Conbine(rBuf);
	for (lBuf.MoveToFirst();!lBuf.IsOut();lBuf.MoveToNext())
	{
		if (IS_TYPE(lBuf.GetCurData(),TGPolygonEx2D))
		{
			((TGPolygonEx2D*)lBuf.GetCurData())->Explode(res);
		}
		else
		{
			res << lBuf.FetchCur();
		}
	}
	return true;
}