enum FaceLabel{ UndoneFace, FixedFace, MovedFace, DividedFace };
enum RenewResult{ RenewDone, RenewSuccess, RenewFailure };
enum FaceLocation{ InfrontApart, InfrontContact, Across, BehindContact, BehindApart }; // used in sorting faces for proper drawing

class Face{
public:
	int          birthStage;
	int          faceGroupID;
	class Edge **edge;
	int          vertexSize;
	FaceLabel    label;
	class Edge  *newEdge;
	class Face  *parent;
	class Face  *children[2];

	Vertex *vertex( int i ){ return edge[i]->primaryVertex( *this ); }
	Vector normal(){ Vector n; n.normal( this->vertex( 2 )->position, this->vertex( 1 )->position, this->vertex( 0 )->position ); return n; }
	Face *connectFace( int i ){ return edge[i]->connectFace( *this ); }

	Face( FILE *fp ){
		birthStage = 0;
		faceGroupID = 0;

		// load vertex positions
		if(!fscanf_s( fp, "%d", &vertexSize )){ printf("Error in file read\n"); exit(1); }
		Vector  position[64];
		int i;
		for( i=0; i<vertexSize; i++ ){
			if(!fscanf_s( fp, "%lf%lf", &position[i].x, &position[i].y )){ printf("Error in file read\n"); exit(1); }
			position[i].z = 0.0;
		}
		// calculate texture coordinates
		Vector2D texcoord[64]; // The number of vertices of a single face must be less than 64
		double xmin, xmax, ymin, ymax;
		xmin = xmax = position[0].x;
		ymin = ymax = position[0].y;
		for( i=1; i<vertexSize; i++ ){
			if     ( position[i].x < xmin ) xmin = position[i].x;
			else if( position[i].x > xmax ) xmax = position[i].x;
			if     ( position[i].y < ymin ) ymin = position[i].y;
			else if( position[i].y > ymax ) ymax = position[i].y;
		}
		for( i=0; i<vertexSize; i++ ){
			texcoord[i].x = ( position[i].x - xmin )/( xmax - xmin );
			texcoord[i].y = ( position[i].y - ymin )/( ymax - ymin );
		}

		edge = new Edge *[vertexSize];
		for( i=0; i<vertexSize; i++ ){
			edge[i] = new Edge();
			edge[i]->face[0] = this;
			edge[i]->vertex[0] = new Vertex( position[i], texcoord[i] );
		}
		for( i=0; i<vertexSize; i++ ){
			edge[i]->vertex[1] = edge[(i+1)%vertexSize]->vertex[0];
		}
		newEdge = NULL;
		parent = children[0] = children[1] = NULL;
	}

	void closestVertex( Line &line, Vertex * &closest, double &distance ){
		closest=NULL;
		distance = DBL_MAX;
		for( int i=0; i<vertexSize; i++ ){
			double d = line.distance( this->vertex( i )->position );
			if( d < distance ){
				closest = this->vertex( i );
				distance = d;
			}
		}
	}
	void labelPickedCandidate( Vector &position ){ for( int i=0; i<vertexSize; i++ ) this->vertex( i )->labelPickedCandidate( position ); }

	void closestVertex( Vector &position, Vertex * &closest, double &distance ){
		closest=NULL;
		distance = DBL_MAX;
		for( int i=0; i<vertexSize; i++ ){
			double d = position.distance( this->vertex( i )->position );
			if( d < distance ){
				closest = this->vertex( i );
				distance = d;
			}
		}
	}

	void closestVertex( Line &line, Vertex * &closest, double &distance, Vector &except, double apartMargin=1.0 ){
		closest=NULL;
		distance = DBL_MAX;
		for( int i=0; i<vertexSize; i++ ){
			double d = line.distance( this->vertex( i )->position );
			if( d < distance && this->vertex( i )->position.distance( except ) > apartMargin ){
				closest = this->vertex( i );
				distance = d;
			}
		}
	}

	Edge *closestEdge( double &distance, Vector &p0, Vector &p1 ){
		Edge *closest=NULL;
		distance = DBL_MAX;
		for( int i=0; i<vertexSize; i++ ){
			double d = edge[i]->distance( p0, p1 );
			if( d < distance ){
				closest = edge[i];
				distance = d;
			}
		}
		return closest;
	}

	// renew
	VertexLabels labelVertices( Fold &fold ){
		int m, b, f;
		m = b = f = 0;
		for( int i=0; i<vertexSize; i++ ){
			switch( this->vertex( i )->setLabel( fold ) ){
				case MovedCandidate: m++;break;
				case Fixed:          f++;break;
				case OnAxis:         b++;break;
			}
		}
		if( (b+f) == 0 )  return AllMoved;
		else if( m == 0 ) return AllFixed;
		else              return MovedAndFixed;
	}

	void clearEdgeAndFaceLabels(){ label = UndoneFace; for( int i=0; i<vertexSize; i++ ) edge[i]->label = UndoneEdge; }
	Edge *neighborEdge( Vertex &vertex, int select ){ for( int i=0; i<vertexSize; i++ ) if( this->vertex( i ) == &vertex ) return edge[(i-1+vertexSize+select)%vertexSize]; return NULL; }
	int include( Vertex &vertex ){ for( int i=0; i<vertexSize; i++ ) if( this->vertex( i ) == &vertex ) return 1; return 0; }

	Face( Face &parentFace, int birthStage  ){
		this->birthStage = birthStage;
		edge = new Edge *[parentFace.vertexSize+1];
		this->vertexSize = 0;
		faceGroupID = parentFace.faceGroupID;
		newEdge = NULL;
		parent = &parentFace;
		children[0] = children[1] = NULL;
	}

	void setBoundary( Plane *boundary ){ // used in overlap() only
		Vector faceNormal;
		faceNormal.normal( this->vertex( 0 )->position, this->vertex( 1 )->position, this->vertex( 2 )->position );
		for( int i=0; i<vertexSize; i++ ){
			Vector edge;
			edge.subtract( this->vertex( (i+1)%vertexSize )->position, this->vertex( i )->position );
			boundary[i].normal.exterior( faceNormal, edge );
			boundary[i].normal.normalize();
			boundary[i].passage = this->vertex( (i+1)%vertexSize )->position;
		}
	}

	int ifIncluded( Plane *boundary, int boundarySize, double margin=0.1 ){ // used in overlap() only
		Vector gravity( 0.0, 0.0, 0.0 );
		int i;
		for( i=0; i<vertexSize; i++ ) gravity += this->vertex( i )->position;
		gravity /= double( vertexSize );
		for( i=0; i<boundarySize; i++ ) if( boundary[i].signedDistance( gravity ) <= margin ) return 0;
		return 1;
	}

	int overlap( Face &face, double margin=0.1 ){
	Plane *boundary[2];
		this->setBoundary( 	boundary[0] = new Plane[vertexSize] );
		face.setBoundary( boundary[1] = new Plane[face.vertexSize] );
		// One polygon includes the center of gravity of the other polygon.
		if( this->ifIncluded( boundary[1], face.vertexSize ) ) return 1;
		if( face.ifIncluded( boundary[0], vertexSize ) ) return 1;
		// One of lines of one polygon intersects with that of the other polygon.
		for( int j=0; j<face.vertexSize; j++ ){
			for( int i=0; i<vertexSize; i++ ){
				double distance[4];
				distance[0] = boundary[0][i].signedDistance( face.vertex( j )->position );
				distance[1] = boundary[0][i].signedDistance( face.vertex( (j+1)%face.vertexSize )->position );
				distance[2] = boundary[1][j].signedDistance( this->vertex( i )->position );
				distance[3] = boundary[1][j].signedDistance( this->vertex( (i+1)%vertexSize )->position );
				int intersect = 1;
				if( distance[0]*distance[1] >= 0.0 ) intersect = 0;
				if( fabs(distance[0]) < margin ) intersect = 0;
				if( fabs(distance[1]) < margin ) intersect = 0;
				if( distance[2]*distance[3] >= 0.0 ) intersect = 0;
				if( fabs(distance[2]) < margin ) intersect = 0;
				if( fabs(distance[3]) < margin ) intersect = 0;
				if( intersect ) return 1;
			}
		}
		return 0;
	}

	RenewResult Face::renew( int birthStage, int faceGroupID, Fold &fold ){
		if( label != UndoneFace ) return RenewDone;
		if( faceGroupID != this->faceGroupID ) return RenewFailure;

		for( int i=0; i<vertexSize; i++ ) vertex( i )->renew( birthStage, fold );
		for( int i=0; i<vertexSize; i++ ) edge[i]->renew( birthStage, fold );
		//create child faces
		int m=0, f=0;
		for( int i=0; i<vertexSize; i++ ){
			if(      vertex( i )->label == Moved ) m++;
			else if( vertex( i )->label == Fixed ) f++;
		}
		if( f == 0 ){
			label = MovedFace;
		}else if( m == 0 ){
			label = FixedFace;
		}else{
			label = DividedFace;
			children[0] = new Face( *this, birthStage );
			children[1] = new Face( *this, birthStage );
			newEdge = new Edge( children[0], children[1], birthStage );
			for( int i=0; i<vertexSize; i++ ){
				switch( edge[i]->label ){
				case MovedEdge:
					children[0]->edge[children[0]->vertexSize++] = edge[i];
					if( edge[(i+1)%vertexSize]->label == FixedEdge ){
						newEdge->vertex[0] = this->vertex( (i+1)%vertexSize );
						children[0]->edge[children[0]->vertexSize++] = newEdge;
					}
					break;
				case FixedEdge:
					children[1]->edge[children[1]->vertexSize++] = edge[i];
					if( edge[(i+1)%vertexSize]->label == MovedEdge ){
						newEdge->vertex[1] = this->vertex( (i+1)%vertexSize );
						children[1]->edge[children[1]->vertexSize++] = newEdge;
					}
					break;
				case DividedEdge:
					children[0]->edge[children[0]->vertexSize++] = edge[i]->children[0]->label == MovedEdge ? edge[i]->children[0] : edge[i]->children[1];
					children[1]->edge[children[1]->vertexSize++] = edge[i]->children[0]->label == FixedEdge ? edge[i]->children[0] : edge[i]->children[1];
					if( this->vertex( i )->label == Moved ){
						newEdge->vertex[0] = edge[i]->newVertex;
						children[0]->edge[children[0]->vertexSize++] = newEdge;
					}else{
						newEdge->vertex[1] = edge[i]->newVertex;
						children[1]->edge[children[1]->vertexSize++] = newEdge;
					}
					break;
				}
			}
		}
		for( int i=0; i<vertexSize; i++ ){
			if( edge[i]->label == MovedEdge || edge[i]->label == DividedEdge ){
				if( this->connectFace( i ) != NULL ){
					if( this->connectFace( i )->renew( birthStage, faceGroupID, fold ) == RenewFailure ) return RenewFailure;
				}
			}
		}
		return RenewSuccess;
	}

	void renewPointer( int faceGroupID ){ this->faceGroupID = faceGroupID; for( int i=0; i<vertexSize; i++ ) edge[i]->renewPointer(); }

	//reset
	void resetPointer( int deleteStage ){ for( int i=0; i<vertexSize; i++ ) edge[i]->resetPointer( deleteStage ); }
	~Face(){ if( newEdge != NULL ) delete newEdge; delete edge; }

	void reset( int deleteStage, int faceGroupID ){
		this->faceGroupID = faceGroupID;
		for( int i=0; i<vertexSize; i++ ) edge[i]->reset( deleteStage );
		if( children[0] != NULL ) { delete children[0]; children[0] = NULL; }
		if( children[1] != NULL ) { delete children[1]; children[1] = NULL; }
		if( newEdge != NULL ) { delete newEdge; newEdge = NULL; }
	}

	//draw
	FaceLocation whichSide( Plane &plane, double margin=0.01 ){
		int before=0, behind=0, onIntersection=0;
		for( int i=0; i<vertexSize; i++ ){
			double d = plane.signedDistance( this->vertex( i )->position );
			if( d > margin ) before = 1;
			else if( d < -margin ) behind = 1;
			else onIntersection = 1;
		}
		if     ( before == 1 && behind == 0 ) return onIntersection ? InfrontContact : InfrontApart;
		else if( before == 0 && behind == 1 ) return onIntersection ? BehindContact  : BehindApart;
		else return Across;
	}

	void draw( int faceNumber, FaceProperty &faceProperty ){
		if( faceProperty.type[faceNumber] == ColorFace ){
			faceProperty.glColor(faceNumber);
			glBegin(GL_POLYGON);
			for(int i=0;i<vertexSize;i++) this->vertex(i)->glVertex();
			glEnd();
		}else{
			glEnable(GL_TEXTURE_2D);
			faceProperty.glTexture(faceNumber);
			glBegin(GL_POLYGON);
			for(int i=0;i<vertexSize;i++){
				this->vertex(i)->glTexCoord();
				this->vertex(i)->glVertex();
			}
			glEnd();
		}
	}

	void draw( Vector &frontNormal, FaceProperty &faceProperty ){
		Vector n = this->normal();
		if( frontNormal * n > 0 ) this->draw(0, faceProperty );
		else                      this->draw(1, faceProperty );
		// draw face border
		faceProperty.glColor(2);
		glBegin(GL_LINE_LOOP);
		for(int i=0;i<vertexSize;i++) this->vertex(i)->glVertex();
		glEnd();
	}

	void print(){
		printf( "birthStage %d\n", birthStage );
		printf( "faceGroupID %d\n", faceGroupID );
		printf( "vertexSize %d\n", vertexSize );
		switch( label ){
			case MovedFace  : printf( "label MovedFace\n" ); break;
			case FixedFace  : printf( "label FixedFace\n" ); break;
			case DividedFace: printf( "label DividedFace\n" ); break;
			case UndoneFace:  printf( "label UndoneFace\n" ); break;
		}
		for( int i=0; i<vertexSize; i++ ){
			switch( this->vertex(i)->label ){
			case Moved:  printf( "MovedVertex " ); break;
			case Fixed:  printf( "FixedVertex " ); break;
			case OnAxis: printf( "OnAxis      " ); break;
			}
			this->vertex(i)->position.print();
		}
	}
};

// ------------------------- other classes member functions -----------------------------------------
bool Fold::setPick(Face &face){
	for( int i=0; i<face.vertexSize; i++ ){
		if( face.vertex( i )->label == PickedCandidate ){
			vertex = face.vertex( vertexID = i );
			return true;
		}
	}
	return false;
}



Vertex *Edge::primaryVertex( class Face &face ){ return &face == this->face[0] || face.parent == this->face[0] || face.children[0] == this->face[0] || face.children[1] == this->face[0] ? vertex[0] : vertex[1]; }

void Edge::renewPointer(){
	for( int i=0; i<2; i++ ){
		if( vertex[i]->child !=NULL ) vertex[i] = vertex[i]->child;
		if( face[i] != NULL && face[i]->children[0] !=NULL ){
			if( label == MovedEdge ) face[i] = face[i]->children[0];
			else face[i] = face[i]->children[1];
		}
	}
}

void Edge::resetPointer( int deleteStage ){
	for( int i=0; i<2; i++ ){
		if( vertex[i]->birthStage == deleteStage ) vertex[i] = vertex[i]->parent;
		if( face[i] != NULL && face[i]->birthStage == deleteStage ) face[i] = face[i]->parent;
	}
}