Bonjour tlm
Je cherche à optimiser l'algorithme Quick Hull pour déterminer l'enveloppe convexe de N points à coordonnées entières dans un plan.
Au lancement de QuickHull(...)les points sont triés dans une liste simplement chaînée par ordre d'abscisse croissante.
Voici la portion de code qui m'intéresse et qui doit être sujette à modification:
void QuickHull(Point A,Point B,Liste *lPtr)
{
int airemax=0; // correspond au point le plus loin
int otes=0; // le nombre de points à l'intérieur d'un triangle
Point plusloin; // le point le plus éloigné ( en terme d'aire )
TrouverPlusLoin(A,B,&plusloin,*lPtr,&airemax);
Supprimer(A,B,plusloin,lPtr,&otes);// enlève ce qu'il y a à l'intérieur du triangle ABplusloin
if(otes!=0) // si on a enlevé des points il faut continuer
{ // nouveau sous-régionnement en 2 régions
QuickHull(A,plusloin,lPtr);
QuickHull(plusloin,B,lPtr);
}// sinon on s'arrête
}
void Supprimer(Point A,Point B,Point H,Liste *lPtr,int *otesPtr)
{ // on supprime ceux qui sont dans le triangle (on regarde si les points sont à gauche des 3 segmennts)
Liste courant=(*lPtr); // élément courant
Liste suivant=(*lPtr);
while(estListeVide(courant)==FAUX) // pour supprimer les points à l'intérieur
{
suivant=courant->lien;
if(EstAGauche(courant->p,H,A)==VRAI && EstAGauche(courant->p,B,H)==VRAI && EstAGauche(courant->p,A,B)==VRAI)
{
(*lPtr)=delister(*lPtr,courant->p);// OPTIMISATION :le délistage pourrait reprendre la liste non pas depuis le début mais depuis le point précédent
(*otesPtr)++; // pour cela la fonction de délistage doit être modifiée ( un paramètre de plus: l'endroit de la liste où commence le délistage )
}
courant=suivant;
}
}
Liste delister(Liste l, Point pt)
{
Liste ptrCourant=l;
Liste ptrPred=ptrCourant; // l'Element précédent
if (estListeVide(l)==VRAI)
return l; // si la liste est vide... on ne touche à rien
if (((l->p).abs==pt.abs) && ((l->p).ord==pt.ord)) // si c'est le premier qu'on vire
{
l=l->lien; // l pointe vers le suivant
free(ptrCourant); // on libère la mémoire
return l;
}
ptrCourant=ptrCourant->lien; // sinon on passe au 2eme element
while (estListeVide(ptrCourant)==FAUX) // tant que c'est pas le bon
{
if (((ptrCourant->p).abs==pt.abs) && ((ptrCourant->p).ord==pt.ord))
{
ptrPred->lien=ptrCourant->lien;// on saute l'Element délisté
free(ptrCourant);
return l;
}
ptrPred=ptrCourant;// sinon on passe au suivant
ptrCourant=ptrCourant->lien;
}
return l;
}
Ceux qui liront attentivement jusque là ( donc susceptibles de m'aider ! ) remarqueront que ce code marche parfaitement. Mais à chaque délistage, la fonction ( delister ) reprend la lecture de la liste chaînée depuis le début alors que l'on pourrait gagner en performance en reprenant le parcours de la liste depuis le point précedent puisque la liste est TRIEE. Il faudrait donc changer la fonction delister en ajoutant un parametre du genre Liste courant. J'ai essayé mais je n'y arrive pas. SI qqun pouvait m'aider ce serait vraiment sympa
Merci d'avance