#include "StdAfx.h"
#include "mg/Tolerance.h"
#include "mg/Straight.h"
#include "topo/Loop.h"
#include "Tl2/TL2parameter.h"
#include "Tl2/TL2Triangles.h"
#include "Tl2/TL2LPlines.h"

#if defined(_DEBUG)
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/****************************************************************/
/*   Copyright (c) 2018 by System fugen G.K.                    */
/*                       All rights reserved.                   */
/****************************************************************/

//Nullify this.
void mgTL2LPlines::setNull(){
	for(int i=0; i<MAX_LINE_NUM; i++)
		m_plines[i].setNull();
	m_nlines=0;
}

//Test if the vertex vid is loosely flat(true), or not.
bool mgTL2LPlines::isLooselyFlatOrConcaveVertex(int vid)const{
	double concav=getVertexConcavity(vid);
	return isLooselyFlatOrConcave(concav);
}

//Test if the edge eid is concave or not.
bool mgTL2LPlines::isConcaveEdge(int eid)const{
	double concavEid=m_plines[eid].getConcavity();
	return concavEid>=STRICT_CONCAVITY;
}

//Compare vid1's and vid2's openess(concavity),
//then if vid1's is more open, return true.
bool mgTL2LPlines::isMoreOpen(int vid1, int vid2)const{
	double concav1=getVertexConcavity(vid1), concave2=getVertexConcavity(vid2);
	return concav1>concave2;
}

///Get concavity at the vertex vid, which is not edge's concavity.
///That is, the concavity is obtained from the difference of two vectors
///at the edge id vid's start point and at the previous edge's end point.
//Concavity's value is from -2 to 2. 2 is most concave, and
// -2 means 180 degree convex(most convex), -1:90 degree convex, 0:flat
// 1:90 degree concave, 2:180 degree concave.
//Concavity's value is from -2 to 2. 2 is most concave, and
// -2 means 180 degree convex(most convex), -1:90 degree convex, 0:flat
// 1:90 degree concave, 2:180 degree concave.
double mgTL2LPlines::getVertexConcavity(int vid)const{
	double& concav=m_concavity[vid];
	if(isUndefinedConcav(vid)){//If not obtained yet.
		int nlines=getNumberOfLines();
		int preID=(vid+nlines-1)%nlines;
		const mgTL2LPline& preL=m_plines[preID];
		int nPre=preL.number_of_points();
		const mgTL2LPline& currentL=m_plines[vid];

		MGPosition Pvid=currentL.uv(0);
		MGVector Tpre=Pvid-preL.uv(nPre-2);
		MGVector Tnow=currentL.uv(1)-Pvid;
		concav=concavityTl2D(Tpre,Tnow);
	}
	return concav;
}

//Obtain minimum and maximum concavity vertex id.
void mgTL2LPlines::computeMinMaxConcav()const{
	int nlines=getNumberOfLines();
	double minConcav=NotObtainedConcav, maxConcav=-NotObtainedConcav;
	for(int i=0; i<nlines; i++){
		double concav=getVertexConcavity(i);
		if(concav<minConcav){
			minConcav=concav;
			m_minConcav=i;
		}
		if(concav>maxConcav){
			maxConcav=concav;
			m_maxConcav=i;
		}
	}
}

//Get the vertx id of minimum concavity.
int mgTL2LPlines::getMinimumConcavID()const{
	if(m_minConcav==-1){
		computeMinMaxConcav();
	}
	return m_minConcav;
}

//Get the vertx id of maximum concavity.
int mgTL2LPlines::getMaximumConcavID()const{
	if(m_maxConcav==-1){
		computeMinMaxConcav();
	}
	return m_maxConcav;
}

///Check the concavities of all the vertices, concavity or sharp angle.
///Function's return value is SHARPorCONCAVE:
//       CONCAVE if concavity found.
///      SHARP if sharp angle found.
///      OTHER if both concavity ro sharp angle not found.
///concaveVID and convexVid are always returned regardless of functon's return value.
mgTL2LPlines::SHARPorCONCAVE mgTL2LPlines::analyzeConcavity(
	int& concaveVID,//most concave vertex id returned,
	int& convexVid	//most convex vertex id returned.
)const{
	SHARPorCONCAVE retval=OTHER;
	concaveVID=getMaximumConcavID();
	convexVid=getMinimumConcavID();
	if(isConcave(m_concavity[concaveVID])){
		retval=CONCAVE;
	}else if(isSharp(m_concavity[convexVid])){
		retval=SHARP;
	}
	return retval;
}

//Obtain from point to subdivide.
//When nlines is 2 or 3, there must be no 2 point edges.
//When nlinesis 4, 2point edge number is at most 1.
mgTLEdgePoint mgTL2LPlines::getFromPointToSubdivide(
	const int eids[5]
		//Following data are input(that are obtained by analyzePointNumber):
		//eids[0]:num of 2 point edges,
		//eids[1], [2];//minimum number of vertices and the edge id
		//eids[3], [4];//Maximum vertex number and the edge id
)const{
	mgTLEdgePoint from; //(eid=edge id, vid=point id) is returned, 
	int& eidFrom=from.m_edgeID;
	int nlines=getNumberOfLines();
	if(nlines==5){
		eidFrom=getMostOpenVid();
	}else{
		const int& eidMin=eids[2];
		const int& eidMax=eids[4];
		eidFrom=eidMax;
		if(nlines==4){
			assert(eids[0]<=1);//2point edge number must be at most 1.
			int eidOpo=(eidMax+2)%4;
			if(eids[0]==1){//When only one of the edges has only 2 vertices.
				if(eidMin==eidOpo){//When the oposite edge has only 2points.
					//We avoid 2points edge's opposite one to divide.
					eidFrom=(eidMax+1)%4, eidOpo=(eidMax+3)%4;
				}
			}else{
				double spanLen[4];//each span length of edge i.
				MGPosition uv[4];//vertex i's (u,v) data.
				uv[0]=m_plines[0].uv(0);
				for(int i=0; i<3; i++){
					uv[i+1]=m_plines[i+1].uv(0);
					MGVector Vi=uv[i+1]-uv[i];
					int nspani=m_plines[i].number_of_points()-1;
					spanLen[i]=Vi%Vi/(nspani*nspani);//square of the length.
				}
				MGVector V3=uv[0]-uv[3];
				int nspan3=m_plines[3].number_of_points()-1;
				spanLen[3]=V3%V3/(nspan3*nspan3);//square of the length.
				const double MAX_RATIO=9.;//=3*3.
				int iTooLarge=0;
				for(; iTooLarge<4; iTooLarge++){
					int iOpo=(iTooLarge+2)%4;
					if(spanLen[iTooLarge]>spanLen[iOpo]*MAX_RATIO)
						break;
				}
				if(iTooLarge<4){
					eidFrom=(iTooLarge+1)%4, eidOpo=(iTooLarge+3)%4;
				}
			}
			if(numberOfPointsLine(eidFrom)>numberOfPointsLine(eidOpo))
				eidFrom=eidOpo;
		}
		from.m_pointID=numberOfPointsLine(eidFrom)/2;
	}
	return from;
}

//Normalize the point id epid(eid, Pid), i.e. 
//if is the end point id, change it to the start point id of the next side.
void mgTL2LPlines::normalizePointID(
	mgTLEdgePoint& epid
)const{
	int& eid=epid.m_edgeID;
	int& Pid=epid.m_pointID;
	if(m_plines[eid].isEndPoint(Pid)){
		int nlines=getNumberOfLines();
		//normalize.
		eid=(eid+1)%nlines;
		Pid=0;
	}
}

//Return true if epid is the next point of epid2 around this closed polygon.
bool mgTL2LPlines::isNextPoint(
	const mgTLEdgePoint& epid, const mgTLEdgePoint& epid2
)const{
	mgTLEdgePoint epidTemp=increment(epid2);
	return (epid==epidTemp);
}

//Return true if epid is the previous point of epid2 around this closed polygon.
bool mgTL2LPlines::isPrePoint(
	const mgTLEdgePoint& epid, const mgTLEdgePoint& epid2
)const{
	mgTLEdgePoint epidTemp=increment(epid);
	return (epidTemp==epid2);
}

//Increment (eid, Pid) for (eid2, Pid2) to point at the next num-th point around this.
mgTLEdgePoint mgTL2LPlines::increment(
	const mgTLEdgePoint& epid,//input the target point.
	int num
)const{
	const int& Pid=epid.m_pointID;
	const int& eid=epid.m_edgeID;

	mgTLEdgePoint epid2;
	int& eid2=epid2.m_edgeID;
	int& Pid2=epid2.m_pointID;
	int nlines=getNumberOfLines();
	Pid2=Pid+num;
	eid2=eid;
	int npim1=numberOfPointsLine(eid)-1;
	while(Pid2>=npim1){
		Pid2-=npim1;
		eid2=(eid2+1)%nlines;
		npim1=numberOfPointsLine(eid2)-1;
	}
	return epid2;
}

//Decrement (eid, Pid) for (eid2, Pid2) to point at the previous num-th point around this.
mgTLEdgePoint mgTL2LPlines::decrement(
	const mgTLEdgePoint& epid,//input mgTLEdgePoint to decrement.
	int num
)const{
	mgTLEdgePoint epid2;//decremented mgTLEdgePoint.
	int& eid2=epid2.m_edgeID;
	int& Pid2=epid2.m_pointID;

	const int& Pid=epid.m_pointID;
	const int& eid=epid.m_edgeID;
	int nlines=getNumberOfLines();
	Pid2=Pid-num;
	eid2=eid;
	while(Pid2<0){
		eid2=(eid2+nlines-1)%nlines;//previous edge.
		int npim1=numberOfPointsLine(eid2)-1;
		Pid2+=npim1;
	}
	return epid2;
}

//Obtain how many lines(m_plines[]) are effective.
int mgTL2LPlines::getNumberOfLinesSub()const{
	for(m_nlines=0; m_nlines<MAX_LINE_NUM; m_nlines++){
		if(m_plines[m_nlines].is_null())
			break;
	}
	return m_nlines;
}

//Obtain how many points are in this.
int mgTL2LPlines::getNumberOfPointsSub()const{
	m_npoints=0;
	for(int i=0; i<MAX_LINE_NUM; i++){
		const mgTL2LPline& pli=m_plines[i];
		if(pli.is_null())
			break;
		m_npoints+=short(pli.number_of_points()-1);
	}
	return m_npoints;
}

///get the (u,v) parameter box.
MGBox mgTL2LPlines::getUvBox()const{
	MGBox uvbox;
	int n=getNumberOfLines();
	for(int i=0; i<n; i++){
		const mgTL2LPline& pli=m_plines[i];
		if(pli.is_null())
			break;
		uvbox|=pli.getUvBox();
	}
	return uvbox;
}

///Analyze the numbers of this, getting the number of 2 point edge, maximum and
///minimum point number edges.
void mgTL2LPlines::analyzePointNumver(
	int eids[5]
		//Following data are output:
		//eids[0]:num of 2 point edges,
		//eids[1], [2];//minimum number of vertices and the edge id
		//eids[3], [4];//Maximum vertex number and the edge id
)const{
	int& num2=eids[0]=0;
	int &nMin=eids[1]=-1, &eidMin=eids[2]=0;//minimum number of vertices and the edge id will be stored.
	int &nMax=eids[3]=0, &eidMax=eids[4]=0;//Maximum vertex number and the id of m_plines[i] will be stored.
	m_npoints=0;
	int nLines=getNumberOfLines();
	for(int i=0; i<nLines; i++){
		int nVi=numberOfPointsLine(i);
		m_npoints+=short(nVi)-1;

		if(nVi==2)
			num2++;
		if(nMin<0 || nVi<nMin){
			nMin=nVi;
			eidMin=i;
		}
		if(nVi>nMax){
			nMax=nVi;
			eidMax=i;
		}
	}
	int nlm1=nLines-1;
	int nLast=numberOfPointsLine(nlm1);
	if(eidMin==0 && nLast==nMin)
		eidMin=nlm1;
	if(eidMax==0 && nLast==nMax)
		eidMax=nlm1;
}

///Let lpFrom=m_pline[eidFrom], lpTo=m_pline[idEdgeTo], then
///Subdivide this rectangle from the point PidFrom of lpFrom
///to the point PidTo of lpTo.
///Then generate the two subdivided rectangles LPlines1 and LPlines2.
///When nlines =1, PidFrom or PidTo must be 0.
void mgTL2LPlines::subdivideFromTo(
	const mgTLEdgePoint& from,//id of edge and point that indicates which edge be subdivided.
	const mgTLEdgePoint& to,//id of edge and point that indicates which edge be subdivided.
	mgTL2LPlines& LPlines1,//1st subdivided rectangle, that is the after part
		//of PidFrom. The 1st edge is eidFrom(or a part of it).
	mgTL2LPlines& LPlines2,//2nd subdivided rectangle, that is the previous part of PidFrom.
		//The 1st edge is eidFrom(if Pidfrom>0), or subdividing bridge(if PidFrom==0).
	std::unique_ptr<mgTL2Polyline>& bridge //input or output bridge. When bridge is null,
		//subdivideFromTo makes it to output.
)const{
	const int& eidFrom=from.m_edgeID;
	const int& PidFrom=from.m_pointID;
	int idEdgeTo=to.m_edgeID;
	int PidTo=to.m_pointID;
	assert(!m_plines[eidFrom].isEndPoint(PidFrom));

	int nlines=getNumberOfLines();
	if(m_plines[idEdgeTo].isEndPoint(PidTo)){
		idEdgeTo=(idEdgeTo+1)%nlines;
		PidTo=0;
	}
	const mgTL2LPline& lpFrom=m_plines[eidFrom];
	const mgTL2LPline& lpTo=m_plines[idEdgeTo];
	
	//Build bridge line.
	if(!bridge.get())
		bridge=lpFrom.polygonizeSL(lpTo,PidFrom,PidTo);

	mgTL2LPline saveToLp1;
	int id1=0, id2=0;//Used to count the LPlines1,2 area id.

	//build LPlines1,2
	if(PidFrom){
		lpFrom.subdivide(PidFrom,LPlines2[id2++],LPlines1[id1++]);
		LPlines2.m_concavity[0]=m_concavity[eidFrom];
	}else if(eidFrom!=idEdgeTo){
		LPlines1[id1++]=lpFrom;
	}

	LPlines2[id2++]=mgTL2LPline(bridge.get());
	if(PidTo){
		lpTo.subdivide(PidTo,saveToLp1,LPlines2[id2++]);
	}else
		LPlines2[id2++]=lpTo;

	//Complete LPlines2.
	for(int idE=(idEdgeTo+1)%nlines;idE!=eidFrom; idE=(idE+1)%nlines){
		LPlines2[id2]=m_plines[idE];
		LPlines2.m_concavity[id2++]=m_concavity[idE];
	}

	//build LPlines1.
	if(eidFrom!=idEdgeTo){
		for(int idE=(eidFrom+1)%nlines;idE!=idEdgeTo; idE=(idE+1)%nlines){
			LPlines1[id1]=m_plines[idE];
			LPlines1.m_concavity[id1++]=m_concavity[idE];
		}
	}
	if(PidTo){
		LPlines1[id1]=saveToLp1;
		LPlines1.m_concavity[id1++]=m_concavity[idEdgeTo];
	}
	LPlines1[id1]=mgTL2LPline(bridge.get());
	LPlines1[id1++].reverse();

	assert(id1<=MAX_LINE_NUM && id2<=MAX_LINE_NUM);
	if(LPlines1.getNumberOfLines()<=2 || LPlines2.getNumberOfLines()<=2){
		//This case occurs when illegal boudary data, which is neglected.
		LPlines1.setNull();
		LPlines2.setNull();
	}
}

//This is a proprietry func of getToPointToSubdivide, get to point to subdivide
//by isectSlTl.
//Functin's return value is true if obtained.
bool mgTL2LPlines::getToPointByIsect(
	const mgTLEdgePoint& from,//id of edge and point that indicates which edge be subdivided.
	mgTLEdgePoint& to//to point is output.
)const{
	const int& eidFrom=from.m_edgeID;
	const int& PidFrom=from.m_pointID;
	int nlines=getNumberOfLines();assert(nlines<=5);
	int eidNext=(eidFrom+1)%nlines;
	int eidOpo= nlines>=4 ? (eidFrom+2)%nlines : eidNext;
	int eidPre=(eidFrom+nlines-1)%nlines;
	const mgTL2LPline& lp=m_plines[eidFrom];
	const mgTL2LPline& lpPre=m_plines[eidPre];
	int nPre=lpPre.number_of_points();

	MGPosition P=lp.uv(PidFrom);
	MGPosition Ppre=(PidFrom==0 ? lpPre.uv(nPre-2):lp.uv(PidFrom-1));
	MGVector dir1=P-Ppre;
	MGVector dir2=lp.uv(PidFrom+1)-P;
	MGStraight slMid(dir1,dir2,P);//subdividing straight.
	bool fromIsBeforeMid = double(PidFrom)<double(lp.number_of_points())*0.5;
	int id[5]={eidNext, eidPre, eidOpo, eidFrom, eidFrom};//ordere from nearest edge.
	if(nlines<4)
		id[nlines-1]=eidFrom;
	else if(nlines==5){
		id[2]=(eidFrom+3)%nlines;id[3]=eidOpo;
	}

	//get a intersection with all sides of this polygon.
	int i=0;
	int& eidTo=to.m_edgeID;
	int& PidTo=to.m_pointID;
	for(; i<nlines; i++){
		eidTo=id[i];
		PidTo=m_plines[eidTo].isectSlTl(slMid, fromIsBeforeMid);
		if(PidTo>=0){
			normalizePointID(to);
			break;
		}
	}
	return i<nlines;
}

//Get the process code to update (eidTo, PidTo) data,
//We avoid an end point and the same edge of from edge as much as possible,
//instead use the neighbor inner point.
//Returned code is
// 0:no need to update (This is the normal case)
// 1:eidTo=eidNext;PidTo=1;
// 2:eidTo=eidOpo; PidTo=nOpo-2
// 3:eidTo=eidPre; PidTo=nPre-2;
// 4:eidTo=eidOpo; PidTo= nOpo>=3 ? 1:0;
// 5:if(nOpo>=3){eidTo=eidOpo;PidTo=nOpo-2;}else{eidTo=eidPre;PidTo=0;}
// 6:eidTo=eidOpo2;PidTo=nOpo2-2;
int mgTL2LPlines::getProcessCode(
	const mgTLEdgePoint& from,//id of edge and point that indicates which edge be subdivided.
	const mgTLEdgePoint& to,//id of edge and point that indicates which edge be subdivided.
	int& toKind //Point kind is returned.
)const{
	int nlines=getNumberOfLines();
	toKind=0;//the case that eidTo==eidFrom and PidFrom<PidTo.
	int processCode=0;//code of no need to update.

	const int& eidFrom=from.m_edgeID;
	const int& PidFrom=from.m_pointID;
	const int& eidTo=to.m_edgeID;
	const int& PidTo=to.m_pointID;
	if(eidTo==eidFrom){
		if(PidTo<PidFrom){
			processCode=(nlines==4) ? 5:3;
			switch(nlines){
				case 2 : toKind=PidTo ? 4:3; break;
				case 3 : toKind=PidTo ? 6:5; break;
				case 4 : toKind=PidTo ? 8:7; break;
			}
		}else{
			processCode= (nlines==4&&PidFrom) ? 4:1;
		}
	}else if(eidTo==(eidFrom+1)%nlines){//if next.
		toKind=PidTo ? 2:1;
		if(nlines<=3 || PidFrom==0){
			if(PidTo==0)
				processCode=1;
		}else if(nlines==4){
			processCode=4;
		}
	}else{//Here nlines==2 cases are exhausted.
		toKind=PidTo ? 4:3;
		if(nlines==3 && PidFrom==0)
			processCode=2;
		//Here nlines==3 cases are exhausted.
		else if(nlines>=4){
			//Here eidTo= opo, op2(when nlines==5), or pre.
			if(eidTo==(eidFrom+2)%nlines){//If opo.
				if(nlines==4 && PidFrom && PidTo==0)
					processCode=4;
			}else if(eidTo==(eidFrom+nlines-1)%nlines){//if eidTo==Pre.
				if(nlines==4){
					toKind=PidTo ? 6:5;
					processCode=PidFrom ? 5:2;
				}else{
					toKind=PidTo ? 8:7;
					processCode=6;
				}
			}
		}
	}
	return processCode;
}

//Get subdivide to-point, providing from point.
mgTLEdgePoint mgTL2LPlines::getToPointToSubdivide(
	const mgTLEdgePoint& from
	//indicates the edge and the point id where to subdivide,
)const{
	const int& eidFrom=from.m_edgeID;
	const int& PidFrom=from.m_pointID;
	int nlines=getNumberOfLines();assert(nlines<=5);
	int eidNext=(eidFrom+1)%nlines;
	int eidOpo= nlines>=4 ? (eidFrom+2)%nlines : eidNext;
	int eidOpo2= (eidFrom+3)%nlines;//valid only when nlines==5.
	int eidPre=(eidFrom+nlines-1)%nlines;

	int nNext=m_plines[eidNext].number_of_points();
	int nPre=m_plines[eidPre].number_of_points();
	int nOpo=m_plines[eidOpo].number_of_points();
	int nOpo2=m_plines[eidOpo2].number_of_points();

	assert(!(nlines==2 && PidFrom==0)); 
	assert(!(nlines==2 && nOpo<=2)); 
	assert(!(nlines==3 && PidFrom==0 && nOpo<=2)); 
	assert(!(nlines==5 && PidFrom)); 

	mgTLEdgePoint to;
	int& eidTo=to.m_edgeID;
	int& PidTo=to.m_pointID;
	if(!getToPointByIsect(from,to)){
		//This is a very illegal case, that logically does not take place.
		eidTo=eidOpo;
		if(nlines<=4){
			int nOpom2=nOpo-2;
			PidTo=(nOpom2<=PidFrom) ? nOpom2:PidFrom;
		}else
			PidTo=0;
		return to;
	}
	int toKind;
	int processCode=getProcessCode(from,to, toKind);

	//We avoid an end point and the same edge of from edge as much as possible,
	//instead use the neighbor inner point.
	switch(processCode){
	case(1): eidTo=eidNext; PidTo=1; break;
	case(2): eidTo=eidOpo; PidTo=nOpo-2; break;
	case(3): eidTo=eidPre; PidTo=nPre-2; break;
	case(4): eidTo=eidOpo; PidTo=nOpo>=3 ? 1:0; break;
	case(5):
		if(nOpo2>=3){
			eidTo=eidOpo; PidTo=nOpo-2;
		 }else{
			eidTo=eidPre; PidTo=0;
		 }
		 break;
	case(6): eidTo=eidOpo2; PidTo= nOpo2-2; break;
	default:;
	}
	return to;
}

//Subdivide at a point PidFrom of m_plines[eidFrom].
//Function's return value is mgTL2Polyline that subdivides this,
//which must exist until the tessellation is done.
std::unique_ptr<mgTL2Polyline> mgTL2LPlines::subdivideAtPoint(
	const mgTLEdgePoint& from,//Indicates the edge and the point id where to subdivide
	mgTL2LPlines& LPlines1,	//1st subdivided rectangle, that is the after part
		//of from. The 1st edge is from edge(or a part of it).
	mgTL2LPlines& LPlines2	//2nd subdivided rectangle, that is the previous part of from.
		//The 1st edge is from(if from.pid>0), or subdividing bridge(if from.pid==0).
)const{
	//int eidTo, PidTo;
	mgTLEdgePoint to=getToPointToSubdivide(from);
	std::unique_ptr<mgTL2Polyline> bridge;
	subdivideFromTo(from,to,LPlines1,LPlines2,bridge);
	return bridge;
}

///Debug Function
std::ostream& mgTL2LPlines::toString(std::ostream& ostrm)const{
	ostrm<<"mgTL2LPlines::"<<this;
	ostrm<<", m_polylines"<<std::endl;
	for(int i=0; i<MAX_LINE_NUM; i++){
		if(m_plines[i].is_null())
			break;
		ostrm<<"["<<i<<"]="<<m_plines[i];
	}	
	return ostrm;
}
