358 lines
9.1 KiB
C
358 lines
9.1 KiB
C
#include "agglo.h"
|
|
|
|
|
|
ErrEnum initAgglo(Agglomerat* a,Point* pts, uint32_t taille)
|
|
{
|
|
a->agglo=calloc(taille, sizeof(Point*));
|
|
if (a->agglo==NULL)
|
|
{
|
|
fprintf(stderr, "%s\n", strerror(errno));
|
|
return ALLOCATION_FAILURE;
|
|
}
|
|
|
|
a->nbPts=taille;
|
|
|
|
a->moy.lat=0;
|
|
a->moy.lon=0;
|
|
for (uint32_t i=0; i<taille;i++)
|
|
{
|
|
pts[i].type=AGGLOMERAT;
|
|
a->agglo[i]=&pts[i];
|
|
a->moy.lat+=pts[i].pos.lat;
|
|
a->moy.lon+=pts[i].pos.lon;
|
|
}
|
|
|
|
a->moy.lat/=a->nbPts;
|
|
a->moy.lon/=a->nbPts;
|
|
|
|
a->aSupprimer = false;
|
|
|
|
return SUCCESS;
|
|
}
|
|
|
|
void libereAgglo(Agglomerat *const a)
|
|
{
|
|
free(a->agglo);
|
|
a->agglo=NULL;
|
|
}
|
|
|
|
Agglomerat fusionAgglo(Agglomerat const* const a1, Agglomerat const* const a2)
|
|
{
|
|
/*Pour que les agglomérats soient dans l'ordre chronologique*/
|
|
if (a1->agglo[0]->date > a2->agglo[0]->date)
|
|
return fusionAgglo(a2,a1);
|
|
|
|
|
|
Agglomerat retour;
|
|
|
|
retour.agglo=calloc(a1->nbPts+a2->nbPts, sizeof(Point*));
|
|
|
|
if (retour.agglo==NULL)
|
|
{
|
|
fprintf(stderr, "%s\n", strerror(errno));
|
|
return (Agglomerat){(Coordonnees){0.0, 0.0}, (sfVector2f){0.0, 0.0}, NULL, 0, {NULL, NULL}, 0.0, 0.0, false};
|
|
}
|
|
|
|
/*Définition des valeurs du nouvel agglomérat*/
|
|
|
|
retour.nbPts=a1->nbPts+a2->nbPts;
|
|
retour.moy.lat=(a1->moy.lat+a2->moy.lat)/2;
|
|
retour.moy.lon=(a1->moy.lon+a2->moy.lon)/2;
|
|
|
|
/*Concaténation des points dans le nouvel agglomérat*/
|
|
|
|
for(uint32_t i=0; i<a1->nbPts;i++)
|
|
{
|
|
retour.agglo[i]=a1->agglo[i];
|
|
}
|
|
|
|
for(uint32_t i=0; i<a2->nbPts;i++)
|
|
{
|
|
retour.agglo[i+a1->nbPts]=a2->agglo[i];
|
|
}
|
|
|
|
retour.aSupprimer = false;
|
|
|
|
return retour;
|
|
}
|
|
|
|
uint32_t ecartTemps(Agglomerat const* const a1, Agglomerat const* const a2)
|
|
{
|
|
if (a1->agglo[0]->date > a2->agglo[0]->date)
|
|
return ecartTemps(a2,a1);
|
|
|
|
return a2->agglo[0]->date - a1->agglo[a1->nbPts -1]->date;
|
|
}
|
|
|
|
ErrEnum repereAgglo(Point* points, uint32_t tailleP, Agglomerat** agglos, uint32_t* tailleA)
|
|
{
|
|
uint32_t periode=points[1].date - points[0].date;
|
|
*tailleA=0;
|
|
Agglomerat** agglosTmp=calloc(tailleP/2, sizeof(Agglomerat*));
|
|
if (agglosTmp==NULL)
|
|
{
|
|
fprintf(stderr, "%s\n", strerror(errno));
|
|
return ALLOCATION_FAILURE;
|
|
}
|
|
Agglomerat* tmp=NULL,* entre=NULL,*fusionIntermediaire=NULL;
|
|
uint32_t debut,fin,finPrec,t;
|
|
|
|
for(uint32_t i=1; i<tailleP; i++)
|
|
{
|
|
/*debut et fin représentent les index entre lesquels sont compris les
|
|
points du potentiel futur agglomérat*/
|
|
debut=i-1;
|
|
fin=i;
|
|
|
|
while(fin<tailleP &&
|
|
distance(&(points[fin].pos),&(points[fin-1].pos)) / periode <= VMIN*MARGE)
|
|
/*Tant que la personne n'est pas en dessous d'une certaine vitesse
|
|
(et qu'on est pas à la fin du tableau) */
|
|
{
|
|
fin++;
|
|
}
|
|
if ((fin-debut)*periode>=DUREEMINI)
|
|
/*Si les points couvrent plus que la durée minimum d'un agglomérat
|
|
on crée un agglomérat à partir de ces points*/
|
|
{
|
|
t=*tailleA;
|
|
|
|
if ((agglosTmp[t]=calloc(1, sizeof(Agglomerat)))==NULL)
|
|
{
|
|
fprintf(stderr, "%s\n", strerror(errno));
|
|
return ALLOCATION_FAILURE;
|
|
}
|
|
|
|
if(initAgglo(agglosTmp[t], points + debut,fin-debut)==ALLOCATION_FAILURE)
|
|
{
|
|
return ALLOCATION_FAILURE;
|
|
}
|
|
|
|
if(t!=0 && (ecartTemps(agglosTmp[t-1],agglosTmp[t])<DIFTMINI
|
|
|| (distance(&agglosTmp[t]->moy, &agglosTmp[t-1]->moy)<DISTMINI
|
|
&& percentPointsInCercle(points+finPrec, debut-finPrec, &agglosTmp[t-1]->moy, 60) >= 0.60)))
|
|
/*Si l'agglomérat construit est proche en distance ou en temps de l'agglomérat
|
|
précédent on les fusionne*/
|
|
{
|
|
if ((tmp=calloc(1,sizeof(Agglomerat)))==NULL)
|
|
{
|
|
fprintf(stderr, "%s\n", strerror(errno));
|
|
return ALLOCATION_FAILURE;
|
|
}
|
|
if (debut-finPrec>0)
|
|
{
|
|
/*On inclut les points entre les deux agglomérats dans la fusion.
|
|
Pour cela, on créée un troisième agglomérat contenant ces points
|
|
et on fusionne cet agglomérat avec les autres ensuite*/
|
|
if ((entre=calloc(1,sizeof(Agglomerat)))==NULL)
|
|
{
|
|
fprintf(stderr, "%s\n", strerror(errno));
|
|
return ALLOCATION_FAILURE;
|
|
}
|
|
|
|
if(initAgglo(entre,points+finPrec,debut-finPrec)==ALLOCATION_FAILURE)
|
|
{
|
|
return ALLOCATION_FAILURE;
|
|
}
|
|
|
|
if ((fusionIntermediaire=calloc(1,sizeof(Agglomerat)))==NULL)
|
|
{
|
|
fprintf(stderr, "%s\n", strerror(errno));
|
|
return ALLOCATION_FAILURE;
|
|
}
|
|
|
|
/*Fusionne les trois agglomérats agglosTmp[t-1] agglosTmp[t] et entre*/
|
|
*fusionIntermediaire=fusionAgglo(agglosTmp[t-1],entre);
|
|
*tmp=fusionAgglo(fusionIntermediaire,agglosTmp[t]);
|
|
if (fusionIntermediaire->nbPts==0 || tmp->nbPts==0)
|
|
{
|
|
return ALLOCATION_FAILURE;
|
|
}
|
|
|
|
libereAgglo(fusionIntermediaire);
|
|
libereAgglo(entre);
|
|
free(fusionIntermediaire);
|
|
free(entre);
|
|
}
|
|
else
|
|
{
|
|
*tmp=fusionAgglo(agglosTmp[t-1],agglosTmp[t]);
|
|
}
|
|
|
|
libereAgglo(agglosTmp[t-1]);
|
|
libereAgglo(agglosTmp[t]);
|
|
free(agglosTmp[t-1]);
|
|
free(agglosTmp[t]);
|
|
|
|
agglosTmp[t]=NULL;
|
|
agglosTmp[t-1]=tmp;
|
|
tmp=NULL;
|
|
}
|
|
else
|
|
{
|
|
(*tailleA)++;
|
|
}
|
|
finPrec=fin;
|
|
}
|
|
i=fin;
|
|
}
|
|
|
|
if ((*agglos=calloc(*tailleA, sizeof(Agglomerat)))==NULL)
|
|
{
|
|
fprintf(stderr, "%s\n", strerror(errno));
|
|
return ALLOCATION_FAILURE;
|
|
}
|
|
|
|
for(uint32_t i=0; i<*tailleA; i++)
|
|
{
|
|
agglos[0][i]=*agglosTmp[i];
|
|
free(agglosTmp[i]);
|
|
}
|
|
free(agglosTmp);
|
|
|
|
for(uint32_t j = 0; j < *tailleA; ++j)
|
|
{
|
|
for(uint32_t k = 0; k < (*agglos)[j].nbPts; ++k)
|
|
{
|
|
(*agglos)[j].agglo[k]->ptOnStructure = (*agglos)+j;
|
|
}
|
|
}
|
|
return SUCCESS;
|
|
}
|
|
|
|
|
|
ErrEnum assemblageGlobalAgglo(Agglomerat *tabAgglo, const uint32_t tailleA, AgglomeratGlobal **tabAggloGlobal, uint32_t *tailleAGlobal)
|
|
{
|
|
//Allocation tmp. On suppose que tous les agglos ne sont pas assemblables.
|
|
AgglomeratGlobal *tmp = calloc(tailleA, sizeof(Agglomerat));
|
|
if(tmp == NULL)
|
|
{
|
|
fprintf(stderr, "%s\n", strerror(errno));
|
|
return ALLOCATION_FAILURE;
|
|
}
|
|
|
|
uint32_t i = 0, numAggloGlobal = 0;
|
|
int32_t aggloAAssembler[tailleA]; //Retient les indices d'agglo à assembler
|
|
*tailleAGlobal = 0;
|
|
|
|
bool aggloDone[tailleA]; //Permet de vérifier si un agglo a déjà été traité ou non
|
|
for(uint32_t m = 0; m < tailleA; ++m)
|
|
aggloDone[m] = false;
|
|
|
|
while(i < tailleA)
|
|
{
|
|
if(aggloDone[i] == true) //Si l'agglo est déjà assemblé tu passes au suivant
|
|
{
|
|
++i;
|
|
continue;
|
|
}
|
|
|
|
if(i == tailleA-1) //Si on est sur dernier agglo de la liste, on le met direct dans un Global tout seul
|
|
{
|
|
//Allocation du tableau de pointeur de l'assemblage
|
|
tmp[numAggloGlobal].assemblage = calloc(1, sizeof(Agglomerat*));
|
|
if(tmp[numAggloGlobal].assemblage == NULL)
|
|
{
|
|
fprintf(stderr, "%s\n", strerror(errno));
|
|
return ALLOCATION_FAILURE;
|
|
}
|
|
tmp[numAggloGlobal].assemblage[0] = &tabAgglo[i];
|
|
tmp[numAggloGlobal].nbAgglo = 1;
|
|
tmp[numAggloGlobal].moy = tabAgglo[i].moy;
|
|
|
|
++numAggloGlobal;
|
|
}
|
|
|
|
else
|
|
{
|
|
uint32_t j = i+1, l = 1; //l = 1 car aggloAAssembler[0] sera forcément pris par i
|
|
|
|
for(uint32_t m = 0; m < tailleA; ++m) //Réinitialisation du tableau
|
|
aggloAAssembler[m] = -1;
|
|
aggloAAssembler[0] = i;
|
|
|
|
while(j < tailleA) //Compte le nombre d'agglo à assembler pour l'indice AgglomeratGlobal[numAggloGlobal]
|
|
{
|
|
if(aggloDone[j] != true && distance(&tabAgglo[i].moy, &tabAgglo[j].moy) <= ASSEMBLAGEAGGLOTOL)
|
|
{
|
|
aggloAAssembler[l] = j;
|
|
++l;
|
|
}
|
|
++j;
|
|
}
|
|
|
|
//Allocation du tableau de pointeur de l'assemblage
|
|
tmp[numAggloGlobal].assemblage = calloc(l, sizeof(Agglomerat*));
|
|
if(tmp[numAggloGlobal].assemblage == NULL)
|
|
{
|
|
fprintf(stderr, "%s\n", strerror(errno));
|
|
return ALLOCATION_FAILURE;
|
|
}
|
|
tmp[numAggloGlobal].nbAgglo = l;
|
|
|
|
l = 1;
|
|
//Ajouter le premier agglo pour commencer
|
|
tmp[numAggloGlobal].moy = tabAgglo[aggloAAssembler[0]].moy;
|
|
tmp[numAggloGlobal].nbPtsGlobal = tabAgglo[aggloAAssembler[0]].nbPts;
|
|
tmp[numAggloGlobal].assemblage[0] = &tabAgglo[aggloAAssembler[0]];
|
|
while(aggloAAssembler[l] != -1 && l < tailleA)
|
|
{
|
|
tmp[numAggloGlobal].moy.lat = (tmp[numAggloGlobal].nbPtsGlobal * tmp[numAggloGlobal].moy.lat
|
|
+ tabAgglo[aggloAAssembler[l]].nbPts * tabAgglo[aggloAAssembler[l]].moy.lat)
|
|
/ (tmp[numAggloGlobal].nbPtsGlobal + tabAgglo[aggloAAssembler[l]].nbPts);
|
|
|
|
tmp[numAggloGlobal].moy.lon = (tmp[numAggloGlobal].nbPtsGlobal * tmp[numAggloGlobal].moy.lon
|
|
+ tabAgglo[aggloAAssembler[l]].nbPts * tabAgglo[aggloAAssembler[l]].moy.lon)
|
|
/ (tmp[numAggloGlobal].nbPtsGlobal + tabAgglo[aggloAAssembler[l]].nbPts);
|
|
|
|
tmp[numAggloGlobal].nbPtsGlobal += tabAgglo[aggloAAssembler[l]].nbPts;
|
|
|
|
tmp[numAggloGlobal].assemblage[l] = &tabAgglo[aggloAAssembler[l]];
|
|
aggloDone[aggloAAssembler[l]] = true;
|
|
++l;
|
|
}
|
|
++numAggloGlobal;
|
|
}
|
|
++i;
|
|
}
|
|
|
|
// Réallocation finale
|
|
*tailleAGlobal = numAggloGlobal;
|
|
*tabAggloGlobal = NULL;
|
|
if(*tailleAGlobal != 0)
|
|
{
|
|
*tabAggloGlobal = realloc(tmp, *tailleAGlobal*sizeof(AgglomeratGlobal));
|
|
if(*tabAggloGlobal == NULL)
|
|
{
|
|
fprintf(stderr, "%s\n", strerror(errno));
|
|
return ALLOCATION_FAILURE;
|
|
}
|
|
}
|
|
|
|
return SUCCESS;
|
|
}
|
|
|
|
|
|
ErrEnum pointageSurRoute(Agglomerat *tabAgglo, const uint32_t tailleA, Route *tabRoute, const uint32_t tailleR)
|
|
{
|
|
uint32_t l = 0;
|
|
|
|
for(uint32_t i = 0; i < tailleA; ++i)
|
|
{
|
|
for(uint32_t j = 0; j < tailleR; ++j)
|
|
{
|
|
for(uint32_t k = 0; k < 2; ++k)
|
|
{
|
|
if(tabRoute[j].ptAgglo[k] == &tabAgglo[i])
|
|
{
|
|
tabAgglo[i].ptRoute[l] = &tabRoute[j];
|
|
++l;
|
|
}
|
|
}
|
|
|
|
}
|
|
l = 0;
|
|
}
|
|
return SUCCESS;
|
|
}
|