/*
VOIR A PARTIR DE LIGNE 830

J'ai remplacé taille par *taille dans toutes les fonctions

FONCTION insertion_triangles marche à condition qu'index < taille 
(voir dans le main en bas)-->normalement index vaut 2 au départ et on augmente 
index de 2 à chaque insertion

Il reste (pour la version sur terminal) à :

--> déterminer les 2 points communs entre 2 triangles
--> faire les flips (calcul des longueurs des 2 diagos dans le quadrilatère
formé par 2 triangles voisins ---> garder la + petite diago-->faire les modifs nécessaires dans la liste des triangles) à chaque insertion


*/





int coordonnees_barycentrique(Point p, Point p1, Point p2){
	int coord;

	coord = (p1.x - p.x) * (p2.y - p.y) - (p2.x - p.x) * (p1.y - p.y);
	
	return coord;
}




int localiser_triangle(Point p, Triangle_p liste, int taille){
	assert(NULL != liste);

	int i;
	int alpha, beta, gamma;


	for (i = 0; i < taille; i++){
		alpha = coordonnees_barycentrique(p, liste[i].sommet[2], liste[i].sommet[1]);
		beta = coordonnees_barycentrique(p, liste[i].sommet[1], liste[i].sommet[0]);
		gamma = coordonnees_barycentrique(p, liste[i].sommet[0], liste[i].sommet[2]);

		if ( (alpha >= 0) && (beta >= 0) && (gamma >= 0) ){
			/*printf("Positif :\nalpha-->%d\nbeta-->%d\ngamma-->%d\n\n",alpha,beta,gamma);*/
			return i;
		}

		else if ( (alpha <= 0) && (beta <= 0) && (gamma <= 0) ) {
			alpha = (- 1) * alpha  ;
			beta = (- 1) * beta  ;
			gamma = (- 1) * gamma ;
			/*printf("Negatif :\nalpha-->%d\nbeta-->%d\ngamma-->%d\n\n",alpha,beta,gamma);*/
			return i;		
		}
		
	}
	return -1;
}




int distance(Point a, Point b){
	int d;

	d = sqrt( (b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y) );
	return d;
}




int min(int n1, int n2){
	assert(n1 >= 0);
	assert(n2 >= 0);

	if (n1 <= n2){
		return n1;
	}

	return n2;
}




void insertion_triangles(Point p, Triangle_p tab, int *taille, int *index){
	Triangle_p tmp;
	Triangle t1, t2, t3;
	int indice_triangle;
	int taille_realloc;

	taille_realloc = *taille * 2;

	if ((*index) == (*taille) - 1 ){
		tmp = (Triangle_p)realloc(tab,sizeof(Triangle) * taille_realloc);

		if (NULL == tmp){
			exit(EXIT_FAILURE);
		}
		*taille = taille_realloc;
		tab = tmp;
	}

	indice_triangle = localiser_triangle(p, tab, taille);

	if (indice_triangle == -1){
		printf("Erreur dans la localisation d'indice de la liste des triangles\n");
		exit(EXIT_FAILURE);
	}

	t1.sommet[0] = tab[indice_triangle].sommet[0];
	t1.sommet[1] = p;
	t1.sommet[2] = tab[indice_triangle].sommet[2];

	t2.sommet[0] = tab[indice_triangle].sommet[0];
	t2.sommet[1] = tab[indice_triangle].sommet[1];
	t2.sommet[2] = p;

	t3.sommet[0] = p;
	t3.sommet[1] = tab[indice_triangle].sommet[1];
	t3.sommet[2] = tab[indice_triangle].sommet[2];

	/*Ancien triangle remplacé par un des 3 nouveaux(le 1er ici)*/
	tab[indice_triangle] = t1;

	/*Insertion des 2 autres triangles*/
	tab[*index] = t2;
	tab[(*index) + 1] = t3;
}



/*TEST DE LA FONCTION insertion_triangles dans Main.c*/
int main(int argc, char *argv[]){

	Triangle_p liste;
	Point p;
	int taille = 3;
	int index = 2;
	int recup;

	p.x = 10;
	p.y = 415;



	liste = creation_triangle(&taille);
	recup = localiser_triangle(p, liste, &taille);
	
	afficher(liste, &taille);
	printf("Indice du triangle trouvé: %d\n",recup);
	
	insertion_triangles(p, liste, &taille, &index);
	afficher(liste,&taille);
	
	liberation(&liste);
	


	return 0;
}






int points_similaires(Triangle_p tab, Triangle t){
	int i = 0, ok = 1;
	while (ok){
		if (t.sommet[0] == tab[i].sommet[0] &&
		    t.sommet[1] == tab[i].sommet[1] &&
		    t.sommet[2] == tab[i].sommet[2])
		    continue;
		
		else if (((t.sommet[0] == tab[i].sommet[0] ||
		    t.sommet[0] == tab[i].sommet[1] ||
		    t.sommet[0] == tab[i].sommet[2])&&
		    
		    
		    ((t.sommet[1] == tab[i].sommet[0] ||
		    t.sommet[1] == tab[i].sommet[1] ||
		    t.sommet[1] == tab[i].sommet[2])||
		    
		    (t.sommet[2] == tab[i].sommet[0] ||
		    t.sommet[2] == tab[i].sommet[1] ||
		    t.sommet[2] == tab[i].sommet[2])))||
		    
		    
		    
		    ((t.sommet[2] == tab[i].sommet[0] ||
		    t.sommet[2] == tab[i].sommet[1] ||
		    t.sommet[2] == tab[i].sommet[2])&&
		    
		    (t.sommet[1] == tab[i].sommet[0] ||
		    t.sommet[1] == tab[i].sommet[1] ||
		    t.sommet[1] == tab[i].sommet[2])))
		    	ok = 0;
		i++;
	}
	return --i;
}



int triangle_existe(Triangle t, Triangle_p liste, int *index){
	int i;

	for (i = 0; i < *index; i++){
		if( (	( (t.sommet[0].x == liste[i].sommet[0].x)  && (t.sommet[0].y == liste[i].sommet[0].y) ) 

			|| ( (t.sommet[0].x == liste[i].sommet[1].x)  && (t.sommet[0].y == liste[i].sommet[1].y) ) 

			|| ( (t.sommet[0].x == liste[i].sommet[2].x) && (t.sommet[0].y == liste[i].sommet[2].y) ) )

			&&

			(	( (t.sommet[1].x == liste[i].sommet[0].x)  && (t.sommet[1].y == liste[i].sommet[0].y) ) 

				|| ( (t.sommet[1].x == liste[i].sommet[1].x)  && (t.sommet[1].y == liste[i].sommet[1].y) ) 

				|| ( (t.sommet[1].x == liste[i].sommet[2].x)  && (t.sommet[1].y == liste[i].sommet[2].y) ) )

			&&

			(	( (t.sommet[2].x == liste[i].sommet[0].x)  && (t.sommet[2].y == liste[i].sommet[0].y)) 

				|| ( (t.sommet[2].x == liste[i].sommet[1].x)  && (t.sommet[2].y == liste[i].sommet[1].y) ) 

				|| ( (t.sommet[2].x == liste[i].sommet[2].x)  && (t.sommet[2].y == liste[i].sommet[2].y) ) ) )

			{

				return 1;
			}
	}

	return 0;
}


int* points_similaires(Triangle_p tab, Triangle t, int *index){
	int i = 0, j, ok = 0, tab_tr[3];
	
	for (j=0; j<3; j++)
		tab_tr[j] = -1;

	while (ok != 3 && i<*index){
		if (t.sommet[0].x == tab[i].sommet[0].x &&
		    t.sommet[0].y == tab[i].sommet[0].y &&

		    t.sommet[1].x == tab[i].sommet[1].x &&
		    t.sommet[1].y == tab[i].sommet[1].y &&

		    t.sommet[2].x == tab[i].sommet[2].x &&
		    t.sommet[2].y == tab[i].sommet[2].y)

		    continue;
		
		else if 
		
		(((t.sommet[0].x == tab[i].sommet[0].x) && 
		(t.sommet[0].y == tab[i].sommet[0].y))|| 

		    ((t.sommet[0].x == tab[i].sommet[1].x) && 
		    (t.sommet[0].y == tab[i].sommet[1].y)) ||

		    ((t.sommet[0].x == tab[i].sommet[2].x) && 
		    (t.sommet[0].y == tab[i].sommet[2].y)) &&
		    
		    
		    ((t.sommet[1].x == tab[i].sommet[0].x) && 
		    (t.sommet[1].y == tab[i].sommet[0].y)) 

		    ((t.sommet[1].x == tab[i].sommet[1].x) && 
		    (t.sommet[1].y == tab[i].sommet[1].y)) 

		    ((t.sommet[1].x == tab[i].sommet[2].x) && 
		    (t.sommet[1].y == tab[i].sommet[2].y))


		    ((t.sommet[2].x == tab[i].sommet[0].x) && 
		    (t.sommet[2].y == tab[i].sommet[0].y))

		    ((t.sommet[2].x == tab[i].sommet[1].x) && 
		    (t.sommet[2].y == tab[i].sommet[1].y)) 

		    ((t.sommet[2].x == tab[i].sommet[2].x) && 
		    (t.sommet[2].y == tab[i].sommet[2].y))		

		    
    
		    
		    ((t.sommet[2].x == tab[i].sommet[0].x) && 
		    (t.sommet[2].y == tab[i].sommet[0].y))

		    ((t.sommet[2].x == tab[i].sommet[1].x) &&
		    (t.sommet[2].y == tab[i].sommet[1].y)) 

		    ((t.sommet[2].x == tab[i].sommet[2].x) && 
		    (t.sommet[2].y == tab[i].sommet[2].y))	



		    ((t.sommet[1].x == tab[i].sommet[0].x) &&
		    (t.sommet[1].y == tab[i].sommet[0].y)) 
		    
		    ((t.sommet[1].x == tab[i].sommet[1].x) &&
		    (t.sommet[1].y == tab[i].sommet[1].y)) 

		    ((t.sommet[1].x == tab[i].sommet[2].x) && 
		    (t.sommet[1].y == tab[i].sommet[2].y))){
		    	tab_tr[ok] = i;
		    	ok++;
		    	}
		i++;
	}
	return tab_tr;
}



/*DANS Main.c*/

int main(int argc, char *argv[]){

	Triangle_p liste;

	Triangle t_test;
	Triangle t_commun;

	Point p;
	Point p_deux;

	int taille = 3;
	int index = 2;
	int recup;

	p.x = 10;
	p.y = 415;

	p_deux.x = 500;
	p_deux.y = 3;

	t_commun.sommet[0].x = 0; t_commun.sommet[0].y = 0;
	t_commun.sommet[1].x = 10; t_commun.sommet[1].y = 415;
	t_commun.sommet[2].x = 0; t_commun.sommet[2].y = 511;


	t_test.sommet[0].x = 0;	t_test.sommet[0].y = 0;
	t_test.sommet[1].x = 10; t_test.sommet[1].y = 415;
	t_test.sommet[2].x = 0;	t_test.sommet[2].y = 511;


	liste = creation_triangle(&taille);

	recup = localiser_triangle(p_deux, liste, &index);
	printf("Triangle existence ---> %d\n",triangle_existe(t_test, liste, &index) );
	afficher(liste, &index);
	printf("Indice du triangle trouvé: %d\n",recup);
	
	insertion_triangles(p, liste, &taille, &index);
	printf("Triangle existence ---> %d\n",triangle_existe(t_test, liste, &index) );
	afficher(liste,&index);

	insertion_triangles(p_deux, liste, &taille, &index);
	printf("Triangle existence ---> %d\n",triangle_existe(t_test, liste, &index) );
	afficher(liste,&index);

	

	

	int *b;

	b = points_similaires(liste,t_commun,&index);
	

	printf("1er--> %d\n2eme--> %d\n3ème--> %d\n",b[0],b[1],b[2]);
	
	liberation(&liste);

	return 0;
}


src/Triangulation.c:301:20: error: expected ‘;’ before ‘)’ token
  for (j=0, j<3, j++)
                    ^
src/Triangulation.c:301:20: error: expected expression before ‘)’ token
src/Triangulation.c:332:7: error: called object is not a function or function pointer
       ((t.sommet[1].x == tab[i].sommet[1].x) && 
       ^
src/Triangulation.c:375:2: warning: function returns address of local variable [-Wreturn-local-addr]
  return tab_tr;
  ^






int* points_similaires(Triangle_p tab, Triangle t, int *index){
	int i = 0, ok = 0, tab_tr[3];
	int j;

	int *p_t;

	for (j=0; j<3; j++)
		tab_tr[j] = -1;


	while (ok != 3 && i<*index){
		if (t.sommet[0].x == tab[i].sommet[0].x &&
		    t.sommet[0].y == tab[i].sommet[0].y &&

		    t.sommet[1].x == tab[i].sommet[1].x &&
		    t.sommet[1].y == tab[i].sommet[1].y &&

		    t.sommet[2].x == tab[i].sommet[2].x &&
		    t.sommet[2].y == tab[i].sommet[2].y)

		    continue;
		
		else if 
		
		(((t.sommet[0].x == tab[i].sommet[0].x) && 
		(t.sommet[0].y == tab[i].sommet[0].y))|| 

		    ((t.sommet[0].x == tab[i].sommet[1].x) && 
		    (t.sommet[0].y == tab[i].sommet[1].y)) ||

		    ((t.sommet[0].x == tab[i].sommet[2].x) && 
		    (t.sommet[0].y == tab[i].sommet[2].y)) &&
		    
		    
		    ((t.sommet[1].x == tab[i].sommet[0].x) && 
		    (t.sommet[1].y == tab[i].sommet[0].y)) 

		    ((t.sommet[1].x == tab[i].sommet[1].x) && 
		    (t.sommet[1].y == tab[i].sommet[1].y)) 

		    ((t.sommet[1].x == tab[i].sommet[2].x) && 
		    (t.sommet[1].y == tab[i].sommet[2].y))


		    ((t.sommet[2].x == tab[i].sommet[0].x) && 
		    (t.sommet[2].y == tab[i].sommet[0].y))

		    ((t.sommet[2].x == tab[i].sommet[1].x) && 
		    (t.sommet[2].y == tab[i].sommet[1].y)) 

		    ((t.sommet[2].x == tab[i].sommet[2].x) && 
		    (t.sommet[2].y == tab[i].sommet[2].y))		

		    
    
		    
		    ((t.sommet[2].x == tab[i].sommet[0].x) && 
		    (t.sommet[2].y == tab[i].sommet[0].y))

		    ((t.sommet[2].x == tab[i].sommet[1].x) &&
		    (t.sommet[2].y == tab[i].sommet[1].y)) 

		    ((t.sommet[2].x == tab[i].sommet[2].x) && 
		    (t.sommet[2].y == tab[i].sommet[2].y))	



		    ((t.sommet[1].x == tab[i].sommet[0].x) &&
		    (t.sommet[1].y == tab[i].sommet[0].y)) 
		    
		    ((t.sommet[1].x == tab[i].sommet[1].x) &&
		    (t.sommet[1].y == tab[i].sommet[1].y)) 

		    ((t.sommet[1].x == tab[i].sommet[2].x) && 
		    (t.sommet[1].y == tab[i].sommet[2].y))){
		    	tab_tr[ok] = i;
		    	ok++;
		    	}
		i++;
	}
	p_t = tab_tr;
	/*return tab_tr;*/
	return p_t;
}










src/Triangulation.c: In function ‘points_similaires’:
src/Triangulation.c:333:7: error: called object is not a function or function pointer
       ((t.sommet[1].x == tab[i].sommet[1].x) && 
       ^
make: *** [bin/Triangulation.o] Erreur 1


((t.sommet[1].x == tab[i].sommet[1].x) && 












/*mettre en paramètre le tableau ou malloc*/

int *points_similaires(Triangle_p tab, Triangle t, int *index, int tab_tr[3]){
	int i, ok;
	int j;

	i = 0;
	ok = 0;

	for (j = 0; j < 3; j++){
		tab_tr[j] = -1;
	}	

	while (ok != 3 && i < *index){
		if (
			(t.sommet[0].x == tab[i].sommet[0].x) 
			&& (t.sommet[0].y == tab[i].sommet[0].y)
			&& (t.sommet[1].x == tab[i].sommet[1].x)
			&& (t.sommet[1].y == tab[i].sommet[1].y)
			&& (t.sommet[2].x == tab[i].sommet[2].x) 
			&& (t.sommet[2].y == tab[i].sommet[2].y)
			)
		    ;
		
		else if (((
			((t.sommet[0].x == tab[i].sommet[0].x) && (t.sommet[0].y == tab[i].sommet[0].y))
			|| ((t.sommet[0].x == tab[i].sommet[1].x) && (t.sommet[0].y == tab[i].sommet[1].y))
			|| ((t.sommet[0].x == tab[i].sommet[2].x) && (t.sommet[0].y == tab[i].sommet[2].y))  )

		    &&
		    
		    
		    ((
		    	((t.sommet[1].x == tab[i].sommet[0].x) && (t.sommet[1].y == tab[i].sommet[0].y))
		    	|| ((t.sommet[1].x == tab[i].sommet[1].x) && (t.sommet[1].y == tab[i].sommet[1].y))
		    	|| ((t.sommet[1].x == tab[i].sommet[2].x) && (t.sommet[1].y == tab[i].sommet[2].y))
		    	)

		    ||
		    
		    (
		    	((t.sommet[2].x == tab[i].sommet[0].x) && (t.sommet[2].y == tab[i].sommet[0].y))
		    	|| ((t.sommet[2].x == tab[i].sommet[1].x) && (t.sommet[2].y == tab[i].sommet[1].y))
		    	|| ((t.sommet[2].x == tab[i].sommet[2].x) && (t.sommet[2].y == tab[i].sommet[2].y))
		    	)))

			||
		    
		    
		    
		    ((
		    	((t.sommet[2].x == tab[i].sommet[0].x) && (t.sommet[2].y == tab[i].sommet[0].y)) 
		    	|| ((t.sommet[2].x == tab[i].sommet[1].x) && (t.sommet[2].y == tab[i].sommet[1].y))
		    	|| ((t.sommet[2].x == tab[i].sommet[2].x) && (t.sommet[2].y == tab[i].sommet[2].y))
		    )

		    &&
		    
		    (
		    	((t.sommet[1].x == tab[i].sommet[0].x) && (t.sommet[1].y == tab[i].sommet[0].y))
		    	|| ((t.sommet[1].x == tab[i].sommet[1].x) && (t.sommet[1].y == tab[i].sommet[1].y))
		    	|| ((t.sommet[1].x == tab[i].sommet[2].x) && (t.sommet[1].y == tab[i].sommet[2].y))

		    )))

		    {
		    	tab_tr[ok] = i;
		    	ok++;
		    }

		i++;
	}

	return tab_tr;
}

/*Compte le nombre de -1 dans le tableau quand on appelle points_similaires*/
int nb_moins_un(int tab_tr[3]){
	int cpt, i;

	cpt = 0;

	for (i = 0; i < 3; i++){
		if (tab_tr[i] == -1){
			cpt++;
		}
	}
	return cpt;
}



/*reste à traiter les cas où il y a 1 ou 2 triangle(s) voisin(s) */
Point *points_diagos(Triangle_p tab, Triangle t, int *liste_indices, int *index){
	Point *points;
	int triangles_similaires[3]; 
	int nb;
	int taille; /*taille du tableau de points (en fonction du nb de -1)*/
	int i;

	liste_indices = points_similaires(tab, t, index, triangles_similaires);
	nb = nb_moins_un(liste_indices);
	
	taille = 3 - nb;

	if (taille == 0){
		return NULL;
	}

	points = (Point *) malloc (sizeof (Point) * taille);

	if(NULL == points){
		exit(EXIT_FAILURE);
	}

	switch(taille){
		
		case 3: /*cas où il y a 3 triangles voisins */
			for (i = 0; i < taille; i++){
				if((
					((t.sommet[0].x == tab[liste_indices[i]].sommet[0].x)
					&& (t.sommet[0].y == tab[liste_indices[i]].sommet[0].y)

					&& (t.sommet[1].y == tab[liste_indices[i]].sommet[2].y)
					&& (t.sommet[1].y == tab[liste_indices[i]].sommet[2].y))

					||

					((t.sommet[1].x == tab[liste_indices[i]].sommet[0].x)
					&& (t.sommet[1].y == tab[liste_indices[i]].sommet[0].y)

					&& (t.sommet[2].y == tab[liste_indices[i]].sommet[2].y)
					&& (t.sommet[2].y == tab[liste_indices[i]].sommet[2].y))

					||

					((t.sommet[0].x == tab[liste_indices[i]].sommet[0].x)
					&& (t.sommet[0].y == tab[liste_indices[i]].sommet[0].y)

					&& (t.sommet[2].y == tab[liste_indices[i]].sommet[2].y)
					&& (t.sommet[2].y == tab[liste_indices[i]].sommet[2].y))


					||

					((t.sommet[1].x == tab[liste_indices[i]].sommet[0].x)
					&& (t.sommet[1].y == tab[liste_indices[i]].sommet[0].y)

					&& (t.sommet[0].y == tab[liste_indices[i]].sommet[2].y)
					&& (t.sommet[0].y == tab[liste_indices[i]].sommet[2].y))

					||

					((t.sommet[2].x == tab[liste_indices[i]].sommet[0].x)
					&& (t.sommet[2].y == tab[liste_indices[i]].sommet[0].y)

					&& (t.sommet[1].y == tab[liste_indices[i]].sommet[2].y)
					&& (t.sommet[1].y == tab[liste_indices[i]].sommet[2].y))

					||

					((t.sommet[2].x == tab[liste_indices[i]].sommet[0].x)
					&& (t.sommet[2].y == tab[liste_indices[i]].sommet[0].y)

					&& (t.sommet[0].y == tab[liste_indices[i]].sommet[2].y)
					&& (t.sommet[0].y == tab[liste_indices[i]].sommet[2].y)))	

					)

					{
						points[i].x = tab[liste_indices[i]].sommet[1].x;
						points[i].y = tab[liste_indices[i]].sommet[1].y;
					}


				else if((
					((t.sommet[0].x == tab[liste_indices[i]].sommet[0].x)
					&& (t.sommet[0].y == tab[liste_indices[i]].sommet[0].y)

					&& (t.sommet[1].y == tab[liste_indices[i]].sommet[1].y)
					&& (t.sommet[1].y == tab[liste_indices[i]].sommet[1].y))

					||

					((t.sommet[1].x == tab[liste_indices[i]].sommet[0].x)
					&& (t.sommet[1].y == tab[liste_indices[i]].sommet[0].y)

					&& (t.sommet[2].y == tab[liste_indices[i]].sommet[1].y)
					&& (t.sommet[2].y == tab[liste_indices[i]].sommet[1].y))

					||

					((t.sommet[0].x == tab[liste_indices[i]].sommet[0].x)
					&& (t.sommet[0].y == tab[liste_indices[i]].sommet[0].y)

					&& (t.sommet[2].y == tab[liste_indices[i]].sommet[1].y)
					&& (t.sommet[2].y == tab[liste_indices[i]].sommet[1].y))


					||

					((t.sommet[1].x == tab[liste_indices[i]].sommet[0].x)
					&& (t.sommet[1].y == tab[liste_indices[i]].sommet[0].y)

					&& (t.sommet[0].y == tab[liste_indices[i]].sommet[1].y)
					&& (t.sommet[0].y == tab[liste_indices[i]].sommet[1].y))

					||

					((t.sommet[2].x == tab[liste_indices[i]].sommet[0].x)
					&& (t.sommet[2].y == tab[liste_indices[i]].sommet[0].y)

					&& (t.sommet[1].y == tab[liste_indices[i]].sommet[1].y)
					&& (t.sommet[1].y == tab[liste_indices[i]].sommet[1].y))

					||

					((t.sommet[2].x == tab[liste_indices[i]].sommet[0].x)
					&& (t.sommet[2].y == tab[liste_indices[i]].sommet[0].y)

					&& (t.sommet[0].y == tab[liste_indices[i]].sommet[1].y)
					&& (t.sommet[0].y == tab[liste_indices[i]].sommet[1].y)))	

					)

					{
						points[i].x = tab[liste_indices[i]].sommet[2].x;
						points[i].y = tab[liste_indices[i]].sommet[2].y;
					}

				else if((
					((t.sommet[0].x == tab[liste_indices[i]].sommet[1].x)
					&& (t.sommet[0].y == tab[liste_indices[i]].sommet[1].y)

					&& (t.sommet[1].y == tab[liste_indices[i]].sommet[2].y)
					&& (t.sommet[1].y == tab[liste_indices[i]].sommet[2].y))

					||

					((t.sommet[1].x == tab[liste_indices[i]].sommet[1].x)
					&& (t.sommet[1].y == tab[liste_indices[i]].sommet[1].y)

					&& (t.sommet[2].y == tab[liste_indices[i]].sommet[2].y)
					&& (t.sommet[2].y == tab[liste_indices[i]].sommet[2].y))

					||

					((t.sommet[0].x == tab[liste_indices[i]].sommet[1].x)
					&& (t.sommet[0].y == tab[liste_indices[i]].sommet[1].y)

					&& (t.sommet[2].y == tab[liste_indices[i]].sommet[2].y)
					&& (t.sommet[2].y == tab[liste_indices[i]].sommet[2].y))


					||

					((t.sommet[1].x == tab[liste_indices[i]].sommet[1].x)
					&& (t.sommet[1].y == tab[liste_indices[i]].sommet[1].y)

					&& (t.sommet[0].y == tab[liste_indices[i]].sommet[2].y)
					&& (t.sommet[0].y == tab[liste_indices[i]].sommet[2].y))

					||

					((t.sommet[2].x == tab[liste_indices[i]].sommet[1].x)
					&& (t.sommet[2].y == tab[liste_indices[i]].sommet[1].y)

					&& (t.sommet[1].y == tab[liste_indices[i]].sommet[2].y)
					&& (t.sommet[1].y == tab[liste_indices[i]].sommet[2].y))

					||

					((t.sommet[2].x == tab[liste_indices[i]].sommet[1].x)
					&& (t.sommet[2].y == tab[liste_indices[i]].sommet[1].y)

					&& (t.sommet[0].y == tab[liste_indices[i]].sommet[2].y)
					&& (t.sommet[0].y == tab[liste_indices[i]].sommet[2].y)))	

					)

					{
						points[i].x = tab[liste_indices[i]].sommet[0].x;
						points[i].y = tab[liste_indices[i]].sommet[0].y;
					}
			}		
	}

	return points;
	
}



















/*MODIFS DU VENDREDI 12 JANVIER 2018 */


int coordonnees_barycentrique(Point p, Point p1, Point p2){
	int coord;

	coord = (p1.x - p.x) * (p2.y - p.y) - (p2.x - p.x) * (p1.y - p.y);
	
	return coord;
}




int localiser_triangle(Point p, Triangle_p tab, int *index){
	int i;
	int alpha, beta, gamma;


	for (i = 0; i < *index; i++){
		alpha = coordonnees_barycentrique(p, tab[i].sommet[2], tab[i].sommet[1]);
		beta = coordonnees_barycentrique(p, tab[i].sommet[1], tab[i].sommet[0]);
		gamma = coordonnees_barycentrique(p, tab[i].sommet[0], tab[i].sommet[2]);

		if ( (alpha >= 0) && (beta >= 0) && (gamma >= 0) ){
			return i;
		}

		else if ( (alpha <= 0) && (beta <= 0) && (gamma <= 0) ) {
			alpha = (- 1) * alpha  ;
			beta = (- 1) * beta  ;
			gamma = (- 1) * gamma ;
			return i;		
		}
		
	}
	return -1;
}




int distance(Point a, Point b){
	int d;

	d = sqrt( (b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y) );
	return d;
}




int min(int d1, int d2){
	if (d1 <= d2){
		return d1;
	}

	return d2;
}




void triangles_similaires(Triangle_p tab, Triangle t, int *index, int *liste_indices){
	int i, ok;
	int j;

	i = 0;
	ok = 0;


	for (j = 0; j < 3; j++){
		liste_indices[j] = -1;
	}	


	while (ok != 3 && i < *index){
		if (
			/*(t.sommet[0].x == tab[i].sommet[0].x) 
			&& (t.sommet[0].y == tab[i].sommet[0].y)
			&& (t.sommet[1].x == tab[i].sommet[1].x)
			&& (t.sommet[1].y == tab[i].sommet[1].y)
			&& (t.sommet[2].x == tab[i].sommet[2].x) 
			&& (t.sommet[2].y == tab[i].sommet[2].y)*/
			t.indice == tab[i].indice
			)
		    ;
		
		else if (((
			((t.sommet[0].x == tab[i].sommet[0].x) && (t.sommet[0].y == tab[i].sommet[0].y))
			|| ((t.sommet[0].x == tab[i].sommet[1].x) && (t.sommet[0].y == tab[i].sommet[1].y))
			|| ((t.sommet[0].x == tab[i].sommet[2].x) && (t.sommet[0].y == tab[i].sommet[2].y)))

		    &&
		    
		    
		    ((
		    	((t.sommet[1].x == tab[i].sommet[0].x) && (t.sommet[1].y == tab[i].sommet[0].y))
		    	|| ((t.sommet[1].x == tab[i].sommet[1].x) && (t.sommet[1].y == tab[i].sommet[1].y))
		    	|| ((t.sommet[1].x == tab[i].sommet[2].x) && (t.sommet[1].y == tab[i].sommet[2].y))
		    	)

		    ||
		    
		    (
		    	((t.sommet[2].x == tab[i].sommet[0].x) && (t.sommet[2].y == tab[i].sommet[0].y))
		    	|| ((t.sommet[2].x == tab[i].sommet[1].x) && (t.sommet[2].y == tab[i].sommet[1].y))
		    	|| ((t.sommet[2].x == tab[i].sommet[2].x) && (t.sommet[2].y == tab[i].sommet[2].y))
		    	)))

			||
		    
		    
		    
		    ((
		    	((t.sommet[2].x == tab[i].sommet[0].x) && (t.sommet[2].y == tab[i].sommet[0].y)) 
		    	|| ((t.sommet[2].x == tab[i].sommet[1].x) && (t.sommet[2].y == tab[i].sommet[1].y))
		    	|| ((t.sommet[2].x == tab[i].sommet[2].x) && (t.sommet[2].y == tab[i].sommet[2].y))
		    )

		    &&
		    
		    (
		    	((t.sommet[1].x == tab[i].sommet[0].x) && (t.sommet[1].y == tab[i].sommet[0].y))
		    	|| ((t.sommet[1].x == tab[i].sommet[1].x) && (t.sommet[1].y == tab[i].sommet[1].y))
		    	|| ((t.sommet[1].x == tab[i].sommet[2].x) && (t.sommet[1].y == tab[i].sommet[2].y))

		    )))

		    {
		    	liste_indices[ok] = i;
		    	ok++;
		    }

		i++;
	}

}




void points_diagos(Triangle_p tab, Triangle t, int *liste_indices, Point *tab_points_diagos){

	int i, j;

	i = 0;

	while ( i < 3 && liste_indices[i] != -1 ){
		for(j = 0; j < 3; j++)
			if (!(tab[liste_indices[i]].sommet[j].x == t.sommet[0].x &&
				tab[liste_indices[i]].sommet[j].y == t.sommet[0].y)||

				(tab[liste_indices[i]].sommet[j].x == t.sommet[1].x &&
				tab[liste_indices[i]].sommet[j].y == t.sommet[1].y)||

				(tab[liste_indices[i]].sommet[j].x == t.sommet[2].x &&
				tab[liste_indices[i]].sommet[j].y == t.sommet[2].y))
			
				break;
		tab_points_diagos[i].x = tab[liste_indices[i]].sommet[j].x;
		tab_points_diagos[i].y = tab[liste_indices[i]].sommet[j].y;
		i++;

	}
}




void afficher_liste_indices_points(int *liste_indices){
	int i ;

	for (i = 0; i< 3; i++){
		if (liste_indices[i] == -1){
			break;
		}
		printf("%d\n",liste_indices[i] );
	}
}




void afficher_liste_points(Point *tab_points_diagos, int *liste_indices){
	int i;

	for (i = 0; i < 3; i++){
		if (liste_indices[i] == -1){
			break;
		}
		printf("(%d,%d)\n", tab_points_diagos[i].x, tab_points_diagos[i].y);
	}
}




int *insertion_triangles(Point p, Triangle_p tab, int *taille, int *index, int *tab_triangles_internes){
	Triangle_p tmp;
	Triangle t1, t2, t3;

	int indice_triangle;
	int taille_realloc;

	taille_realloc = *taille * 2;

	if ((*index) == (*taille) - 2 ){
		tmp = (Triangle_p)realloc(tab,sizeof(Triangle) * taille_realloc);

		if (NULL == tmp){
			exit(EXIT_FAILURE);
		}
		*taille = taille_realloc;
		tab = tmp;
	}

	indice_triangle = localiser_triangle(p, tab, index);

	if (indice_triangle == -1){
		printf("Erreur dans la localisation d'indice de la liste des triangles\n");
		exit(EXIT_FAILURE);
	}

	t1.sommet[0] = tab[indice_triangle].sommet[0];
	t1.sommet[1] = p;
	t1.sommet[2] = tab[indice_triangle].sommet[2];

	t2.sommet[0] = tab[indice_triangle].sommet[0];
	t2.sommet[1] = tab[indice_triangle].sommet[1];
	t2.sommet[2] = p;

	t3.sommet[0] = p;
	t3.sommet[1] = tab[indice_triangle].sommet[1];
	t3.sommet[2] = tab[indice_triangle].sommet[2];

	/*Ancien triangle remplacé par un des 3 nouveaux(le 1er ici)*/
	t1.indice = tab[indice_triangle].indice;
	tab[indice_triangle] = t1;

	/*Insertion des 2 autres triangles*/
	t2.indice = tab[*index].indice;
	tab[*index] = t2;

	t3.indice = tab[(*index) + 1].indice;
	tab[(*index) + 1] = t3;


	tab_triangles_internes[0] = t1.indice;
	tab_triangles_internes[1] = t2.indice;
	tab_triangles_internes[2] = t3.indice;

	*index += 2;

	return tab_triangles_internes;
}




int bon_indice(Triangle_p tab, Point a, Point b, Point c, int *tab_triangles_internes){
	int i;
	for (i = 0; i < 3; i++){
		 if ((((tab[tab_triangles_internes[i]].sommet[0].x == a.x) && (tab[tab_triangles_internes[i]].sommet[0].y == a.y)) ||
		    ((tab[tab_triangles_internes[i]].sommet[0].x == b.x) && (tab[tab_triangles_internes[i]].sommet[0].y == b.y)) ||
		    ((tab[tab_triangles_internes[i]].sommet[0].x == c.x) && (tab[tab_triangles_internes[i]].sommet[0].y == c.y)))

			&&

			(((tab[tab_triangles_internes[i]].sommet[1].x == a.x) && (tab[tab_triangles_internes[i]].sommet[1].y == a.y)) ||
		    ((tab[tab_triangles_internes[i]].sommet[1].x == b.x) && (tab[tab_triangles_internes[i]].sommet[1].y == b.y)) ||
		    ((tab[tab_triangles_internes[i]].sommet[1].x == c.x) && (tab[tab_triangles_internes[i]].sommet[1].y == c.y)))

			&&

			(((tab[tab_triangles_internes[i]].sommet[2].x == a.x) && (tab[tab_triangles_internes[i]].sommet[2].y == a.y)) ||
		    ((tab[tab_triangles_internes[i]].sommet[2].x == b.x) && (tab[tab_triangles_internes[i]].sommet[2].y == b.y)) ||
		    ((tab[tab_triangles_internes[i]].sommet[2].x == c.x) && (tab[tab_triangles_internes[i]].sommet[2].y == c.y))))
			
			{
				return i;
			}

	}

}




void flip(Point p, Triangle_p tab, int *tab_indices, Point *tab_points_diagos, int *tab_triangles_internes){
	int d1, d2;
	int i , j;
	Point tmp1, tmp2;

	i = 0;

	while (tab_indices[i] != -1 && i < 3){

		for (j = 0; j < 3; j++){
			if (tab[tab_indices[i]].sommet[j].x != tab_points_diagos[i].x &&
				tab[tab_indices[i]].sommet[j].y != tab_points_diagos[i].y){

				tmp1.x = tab[tab_indices[i]].sommet[j].x;
				tmp1.y = tab[tab_indices[i]].sommet[j].y;
				break;
			}
		}
		for (j = 0; j < 3; j++){
			if ((tab[tab_indices[i]].sommet[j].x != tab_points_diagos[i].x &&
				tab[tab_indices[i]].sommet[j].y != tab_points_diagos[i].y)&&

				(tab[tab_indices[i]].sommet[j].x != tmp1.x &&
				tab[tab_indices[i]].sommet[j].y != tmp1.y))

			{

				tmp2.x = tab[tab_indices[i]].sommet[j].x;
				tmp2.y = tab[tab_indices[i]].sommet[j].y;
				break;
			}
		}


		d1 = distance(p, tab_points_diagos[i]);
		d2 = distance(tmp1, tmp2);

		if (d2 == min(d1,d2))
			break;

		j = bon_indice(tab, p, tmp1, tmp2, tab_triangles_internes);

		tab[j].sommet[0].x = p.x;
		tab[j].sommet[0].y = p.y;

		tab[j].sommet[1].x = tmp1.x;
		tab[j].sommet[1].y = tmp1.y;

		tab[j].sommet[2].x = tab_points_diagos[i].x;
		tab[j].sommet[2].y = tab_points_diagos[i].y;


		tab[tab_indices[i]].sommet[0].x = p.x;
		tab[tab_indices[i]].sommet[0].y = p.y;


		tab[tab_indices[i]].sommet[1].x = tmp2.x;
		tab[tab_indices[i]].sommet[1].y = tmp2.y;

		tab[tab_indices[i]].sommet[2].x = tab_points_diagos[i].x;
		tab[tab_indices[i]].sommet[2].y = tab_points_diagos[i].y;
		
	}
	
}







void flip(Point p, Triangle_p tab, int *tab_indices, Point *tab_points_diagos, int *tab_triangles_internes){
	int d1, d2;
	int i , j;
	Point tmp1, tmp2;

	i = 0;

	while (tab_indices[i] != -1 && i < 3){

		for (j = 0; j < 3; j++){
			if (tab[tab_indices[i]].sommet[j].x != tab_points_diagos[i].x &&
				tab[tab_indices[i]].sommet[j].y != tab_points_diagos[i].y){

				tmp1.x = tab[tab_indices[i]].sommet[j].x;
				tmp1.y = tab[tab_indices[i]].sommet[j].y;
				break;
			}
		}
		for (j = 0; j < 3; j++){
			if ((tab[tab_indices[i]].sommet[j].x != tab_points_diagos[i].x &&
				tab[tab_indices[i]].sommet[j].y != tab_points_diagos[i].y)&&

				(tab[tab_indices[i]].sommet[j].x != tmp1.x &&
				tab[tab_indices[i]].sommet[j].y != tmp1.y))

			{

				tmp2.x = tab[tab_indices[i]].sommet[j].x;
				tmp2.y = tab[tab_indices[i]].sommet[j].y;
				break;
			}
		}


		d1 = distance(p, tab_points_diagos[i]);
		d2 = distance(tmp1, tmp2);

		if (d2 == min(d1,d2))
			break;

		j = bon_indice(tab, p, tmp1, tmp2, tab_triangles_internes);

		tab[j].sommet[0].x = p.x;
		tab[j].sommet[0].y = p.y;

		tab[j].sommet[1].x = tmp1.x;
		tab[j].sommet[1].y = tmp1.y;

		tab[j].sommet[2].x = tab_points_diagos[i].x;
		tab[j].sommet[2].y = tab_points_diagos[i].y;


		tab[tab_indices[i]].sommet[0].x = p.x;
		tab[tab_indices[i]].sommet[0].y = p.y;


		tab[tab_indices[i]].sommet[1].x = tmp2.x;
		tab[tab_indices[i]].sommet[1].y = tmp2.y;

		tab[tab_indices[i]].sommet[2].x = tab_points_diagos[i].x;
		tab[tab_indices[i]].sommet[2].y = tab_points_diagos[i].y;
		
	}
	
}


void points_diagos(Triangle_p tab, Triangle t, int *liste_indices, Point *tab_points_diagos){

	int i, j;

	i = 0;

	while ( i < 3 && liste_indices[i] != -1 ){
		for(j = 0; j < 3; j++)
			if (!(tab[liste_indices[i]].sommet[j].x == t.sommet[0].x &&
				tab[liste_indices[i]].sommet[j].y == t.sommet[0].y)||

				(tab[liste_indices[i]].sommet[j].x == t.sommet[1].x &&
				tab[liste_indices[i]].sommet[j].y == t.sommet[1].y)||

				(tab[liste_indices[i]].sommet[j].x == t.sommet[2].x &&
				tab[liste_indices[i]].sommet[j].y == t.sommet[2].y))
			
				break;
		tab_points_diagos[i].x = tab[liste_indices[i]].sommet[j].x;
		tab_points_diagos[i].y = tab[liste_indices[i]].sommet[j].y;
		i++;

	}
}





void triangles_similaires(Triangle_p tab, Triangle t, int *index, int *liste_indices){
	int i, ok;
	int j;

	i = 0;
	ok = 0;


	for (j = 0; j < 3; j++){
		liste_indices[j] = -1;
	}	


	while (ok != 3 && i < *index){
		if (
			/*(t.sommet[0].x == tab[i].sommet[0].x) 
			&& (t.sommet[0].y == tab[i].sommet[0].y)
			&& (t.sommet[1].x == tab[i].sommet[1].x)
			&& (t.sommet[1].y == tab[i].sommet[1].y)
			&& (t.sommet[2].x == tab[i].sommet[2].x) 
			&& (t.sommet[2].y == tab[i].sommet[2].y)*/
			t.indice == tab[i].indice
			)
		    ;
		
		else if (((
			((t.sommet[0].x == tab[i].sommet[0].x) && (t.sommet[0].y == tab[i].sommet[0].y))
			|| ((t.sommet[0].x == tab[i].sommet[1].x) && (t.sommet[0].y == tab[i].sommet[1].y))
			|| ((t.sommet[0].x == tab[i].sommet[2].x) && (t.sommet[0].y == tab[i].sommet[2].y)))

		    &&
		    
		    
		    ((
		    	((t.sommet[1].x == tab[i].sommet[0].x) && (t.sommet[1].y == tab[i].sommet[0].y))
		    	|| ((t.sommet[1].x == tab[i].sommet[1].x) && (t.sommet[1].y == tab[i].sommet[1].y))
		    	|| ((t.sommet[1].x == tab[i].sommet[2].x) && (t.sommet[1].y == tab[i].sommet[2].y))
		    	)

		    ||
		    
		    (
		    	((t.sommet[2].x == tab[i].sommet[0].x) && (t.sommet[2].y == tab[i].sommet[0].y))
		    	|| ((t.sommet[2].x == tab[i].sommet[1].x) && (t.sommet[2].y == tab[i].sommet[1].y))
		    	|| ((t.sommet[2].x == tab[i].sommet[2].x) && (t.sommet[2].y == tab[i].sommet[2].y))
		    	)))

			||
		    
		    
		    
		    ((
		    	((t.sommet[2].x == tab[i].sommet[0].x) && (t.sommet[2].y == tab[i].sommet[0].y)) 
		    	|| ((t.sommet[2].x == tab[i].sommet[1].x) && (t.sommet[2].y == tab[i].sommet[1].y))
		    	|| ((t.sommet[2].x == tab[i].sommet[2].x) && (t.sommet[2].y == tab[i].sommet[2].y))
		    )

		    &&
		    
		    (
		    	((t.sommet[1].x == tab[i].sommet[0].x) && (t.sommet[1].y == tab[i].sommet[0].y))
		    	|| ((t.sommet[1].x == tab[i].sommet[1].x) && (t.sommet[1].y == tab[i].sommet[1].y))
		    	|| ((t.sommet[1].x == tab[i].sommet[2].x) && (t.sommet[1].y == tab[i].sommet[2].y))

		    )))

		    {
		    	liste_indices[ok] = i;
		    	ok++;
		    }

		i++;
	}

}