123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576 |
- /*************************************/
- /* Auteur : Rémi Synave */
- /* Date de création : 05/01/08 */
- /* Date de modification : 15/03/15 */
- /* Version : 0.4 */
- /*************************************/
- /***************************************************************************/
- /* This file is part of a2ri. */
- /* */
- /* a2ri is free software: you can redistribute it and/or modify it */
- /* under the terms of the GNU Lesser General Public License as published */
- /* by the Free Software Foundation, either version 3 of the License, or */
- /* (at your option) any later version. */
- /* */
- /* a2ri is distributed in the hope that it will be useful, */
- /* but WITHOUT ANY WARRANTY; without even the implied warranty of */
- /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
- /* GNU Lesser General Public License for more details. */
- /* */
- /* You should have received a copy of the GNU Lesser General Public */
- /* License along with a2ri. */
- /* If not, see <http://www.gnu.org/licenses/>. */
- /***************************************************************************/
- #include "graph.h"
- /********** INTERMEDIATE TYPES AND FUNCTIONS **********/
- /* Les fonctions intermédiaires sont préfixées de IF */
- /* et les types intermédiaires de IT */
- int IFlist_edge_etape_tri_rapide (
- double *listlong,
- int *listnumedge,
- int min,
- int max)
- {
- double temp = listlong[max];
- int temp2 = listnumedge[max];
-
- while (max > min)
- {
-
- while (max > min && listlong[min] <= temp)
- min++;
-
- if (max > min)
- {
- listlong[max] = listlong[min];
- listnumedge[max] = listnumedge[min];
- max--;
-
- while (max > min && listlong[max] >= temp)
- max--;
-
- if (max > min)
- {
- listlong[min] = listlong[max];
- listnumedge[min] = listnumedge[max];
- min++;
- }
- }
- }
- listlong[max] = temp;
- listnumedge[max] = temp2;
- return (max);
- }
- void IFlist_edge_tri_rapide (
- double *listlong,
- int *listnumedge,
- int deb,
- int fin)
- {
- int mil;
-
- if (deb < fin)
- {
- mil = IFlist_edge_etape_tri_rapide (listlong, listnumedge, deb, fin);
- if (mil - deb > fin - mil)
- {
- IFlist_edge_tri_rapide (listlong, listnumedge, mil + 1, fin);
- IFlist_edge_tri_rapide (listlong, listnumedge, deb, mil - 1);
- }
- else
- {
- IFlist_edge_tri_rapide (listlong, listnumedge, deb, mil - 1);
- IFlist_edge_tri_rapide (listlong, listnumedge, mil + 1, fin);
- }
- }
- }
- void
- IFlist_edge_sort (
- double *listlong,
- int *listnumedge,
- int size)
- {
- IFlist_edge_tri_rapide (listlong, listnumedge, 0, size - 1);
- }
- /********** MAIN FUNCTIONS **********/
- /**
- Calcul du graphe Nearest Neighbour Graph (NNG)
- @param m le modele
- @return un modele contenant les aretes
- */
- vef_model *
- a2ri_vef_nearest_neighbour_graph (
- const vef_model * const m)
- {
- point3d p1,
- p2,
- ptmin,
- ptmax;
- double distmin;
- space_partition sp;
- vef_model *retour = (vef_model *) malloc (sizeof (vef_model));
- a2ri_erreur_critique_si (retour == NULL,
- "erreur allocation memoire pour retour\na2ri_vef_nearest_neighbour_graph");
- a2ri_vef_init (retour);
- for (int i = 0; i < m->nbvertex; i++)
- a2ri_vef_add_vertex (retour, m->ve[i].x, m->ve[i].y, m->ve[i].z);
- point3d_init (&ptmin, m->xmin, m->ymin, m->zmin);
- point3d_init (&ptmax, m->xmax, m->ymax, m->zmax);
- space_partition_new (&sp, &ptmin, &ptmax, 8, 8, 8);
- a2ri_vef_space_partition (m, &sp);
- retour->xmin = m->xmin;
- retour->xmax = m->xmax;
- retour->ymin = m->ymin;
- retour->ymax = m->ymax;
- retour->zmin = m->zmin;
- retour->zmax = m->zmax;
- for (int i = 0; i < m->nbvertex; i++)
- {
- point3d_init (&p1, m->ve[i].x, m->ve[i].y, m->ve[i].z);
- space_partition_nearest_point (&sp, &p1, &p2, &distmin,
- REJECT_ZERO_LENGTH);
- a2ri_vef_add_edge (retour, i, p2.att_int, 1);
- }
- space_partition_free (&sp);
- return retour;
- }
- /**
- Calcul du graphe Gabriel (GG)
- @param m le modele
- @return un modele contenant les aretes
- */
- vef_model *
- a2ri_vef_gabriel_graph (
- const vef_model * const m)
- {
- point3d p,
- centre;
- double distance;
- int alinterieur,
- k;
- vef_model *retour = (vef_model *) malloc (sizeof (vef_model));
- a2ri_erreur_critique_si (retour == NULL,
- "erreur allocation memoire pour retour\na2ri_vef_gabriel_graph");
- a2ri_vef_init (retour);
- for (int i = 0; i < m->nbvertex; i++)
- a2ri_vef_add_vertex (retour, m->ve[i].x, m->ve[i].y, m->ve[i].z);
- retour->xmin = m->xmin;
- retour->xmax = m->xmax;
- retour->ymin = m->ymin;
- retour->ymax = m->ymax;
- retour->zmin = m->zmin;
- retour->zmax = m->zmax;
- for (int i = 0; i < m->nbvertex; i++)
- {
- for (int j = 0; j < m->nbvertex; j++)
- if (i != j)
- {
- point3d_init (¢re,
- ((m->ve[i].x + m->ve[j].x) * 1.0) / 2.0,
- ((m->ve[i].y + m->ve[j].y) * 1.0) / 2.0,
- ((m->ve[i].z + m->ve[j].z) * 1.0) / 2.0);
- point3d_init (&p, m->ve[i].x, m->ve[i].y, m->ve[i].z);
- distance = point3d_length (¢re, &p);
- alinterieur = 0;
- k = 0;
- while (k < m->nbvertex && alinterieur == 0)
- {
- if (k != i && k != j)
- {
- point3d_init (&p, m->ve[k].x, m->ve[k].y, m->ve[k].z);
- if (point3d_length (&p, ¢re) < distance)
- alinterieur++;
- }
- k++;
- }
- if (!alinterieur)
- a2ri_vef_add_edge (retour, i, j, 1);
- }
- }
- return retour;
- }
- /**
- Calcul du graphe etendu Gabriel (NNG)
- @param m le modele
- @return un modele contenant les aretes
- */
- vef_model *
- a2ri_vef_extended_gabriel_hypergraph (
- const vef_model * const m)
- {
- vef_model *retour = a2ri_vef_gabriel_graph (m);
- int *listve = NULL,
- size = 0,
- ve1,
- ve2,
- ve3;
- point3d p[3],
- *centre = NULL;
- double *rayon = NULL;
- int trouve,
- k;
- vector3d AB,
- AC;
- /*PARTIE1 */
- for (int i = 0; i < retour->nbedge; i++)
- {
- for (int j = 0; j < retour->nbedge; j++)
- {
- listve = NULL;
- size = 0;
- list_int_add (&listve, &size, retour->ed[i].ve1,
- WITHOUT_REDUNDANCE);
- list_int_add (&listve, &size, retour->ed[i].ve2,
- WITHOUT_REDUNDANCE);
- list_int_add (&listve, &size, retour->ed[j].ve1,
- WITHOUT_REDUNDANCE);
- list_int_add (&listve, &size, retour->ed[j].ve2,
- WITHOUT_REDUNDANCE);
- if (size == 3)
- {
- vector3d_init (&AB,
- retour->ve[listve[0]].x -
- retour->ve[listve[1]].x,
- retour->ve[listve[0]].y -
- retour->ve[listve[1]].y,
- retour->ve[listve[0]].z -
- retour->ve[listve[1]].z);
- vector3d_init (&AC,
- retour->ve[listve[0]].x -
- retour->ve[listve[2]].x,
- retour->ve[listve[0]].y -
- retour->ve[listve[2]].y,
- retour->ve[listve[0]].z -
- retour->ve[listve[2]].z);
- double coeff = AB.dx / AC.dx;
- AC.dx *= coeff;
- AC.dy *= coeff;
- AC.dz *= coeff;
- if (!vector3d_equal (&AB, &AC))
- {
- ve1 = retour->ed[i].ve1;
- ve2 = retour->ed[i].ve2;
- if (!(ve2 == retour->ed[j].ve1 || ve2 == retour->ed[j].ve2))
- {
- ve3 = ve1;
- ve1 = ve2;
- ve2 = ve3;
- }
- if (ve2 == retour->ed[j].ve1)
- ve3 = retour->ed[j].ve2;
- else
- ve3 = retour->ed[j].ve1;
- if (a2ri_vef_search_edge (retour, ve1, ve3) == -1)
- {
- point3d_init (&(p[0]), retour->ve[ve1].x,
- retour->ve[ve1].y, retour->ve[ve1].z);
- point3d_init (&(p[1]), retour->ve[ve2].x,
- retour->ve[ve2].y, retour->ve[ve2].z);
- point3d_init (&(p[2]), retour->ve[ve3].x,
- retour->ve[ve3].y, retour->ve[ve3].z);
- centre = NULL;
- rayon = NULL;
- point3d_bounding_ball_minimale (p, 1, ¢re, &rayon);
- trouve = 0;
- k = 0;
- while (k < retour->nbvertex && !trouve)
- {
- point3d_init (&(p[0]), retour->ve[k].x,
- retour->ve[k].y, retour->ve[k].z);
- if (point3d_length (&(p[0]), &(centre[0])) < rayon[0])
- trouve = 1;
- k++;
- }
- if (!trouve)
- a2ri_vef_add_edge (retour, ve1, ve3, 0);
- free (centre);
- free (rayon);
- }
- }
- }
- free (listve);
- }
- }
- /*PARTIE2 */
- for (int i = 0; i < retour->nbedge; i++)
- {
- int numvertex_a = retour->ed[i].ve1;
- for (int j = 0; j < retour->ve[numvertex_a].nbsharededges; j++)
- {
- int numedge_a = retour->ve[numvertex_a].sharededges[j];
- int numvertex_b = retour->ed[numedge_a].ve1;
- for (k = 0; k < retour->ve[numvertex_b].nbsharededges; k++)
- {
- int numedge_b = retour->ve[numvertex_b].sharededges[k];
- if (i != numedge_a && i != numedge_b && numedge_a != numedge_b)
- {
- listve = NULL;
- size = 0;
- list_int_add (&listve, &size, retour->ed[i].ve1,
- WITHOUT_REDUNDANCE);
- list_int_add (&listve, &size, retour->ed[i].ve2,
- WITHOUT_REDUNDANCE);
- list_int_add (&listve, &size, retour->ed[numedge_a].ve1,
- WITHOUT_REDUNDANCE);
- list_int_add (&listve, &size, retour->ed[numedge_a].ve2,
- WITHOUT_REDUNDANCE);
- list_int_add (&listve, &size, retour->ed[numedge_b].ve1,
- WITHOUT_REDUNDANCE);
- list_int_add (&listve, &size, retour->ed[numedge_b].ve2,
- WITHOUT_REDUNDANCE);
- if (size == 3)
- {
- if (a2ri_vef_search_face
- (retour, i, numedge_a, numedge_b) == -1
- && a2ri_vef_search_face (retour, i, numedge_b,
- numedge_a) == -1)
- a2ri_vef_add_face (retour, i, numedge_a, numedge_b);
- }
- free (listve);
- }
- }
- numvertex_b = retour->ed[numedge_a].ve2;
- for (k = 0; k < retour->ve[numvertex_b].nbsharededges; k++)
- {
- int numedge_b = retour->ve[numvertex_b].sharededges[k];
- if (i != numedge_a && i != numedge_b && numedge_a != numedge_b)
- {
- listve = NULL;
- size = 0;
- list_int_add (&listve, &size, retour->ed[i].ve1,
- WITHOUT_REDUNDANCE);
- list_int_add (&listve, &size, retour->ed[i].ve2,
- WITHOUT_REDUNDANCE);
- list_int_add (&listve, &size, retour->ed[numedge_a].ve1,
- WITHOUT_REDUNDANCE);
- list_int_add (&listve, &size, retour->ed[numedge_a].ve2,
- WITHOUT_REDUNDANCE);
- list_int_add (&listve, &size, retour->ed[numedge_b].ve1,
- WITHOUT_REDUNDANCE);
- list_int_add (&listve, &size, retour->ed[numedge_b].ve2,
- WITHOUT_REDUNDANCE);
- if (size == 3)
- {
- if (a2ri_vef_search_face
- (retour, i, numedge_a, numedge_b) == -1
- && a2ri_vef_search_face (retour, i, numedge_b,
- numedge_a) == -1)
- a2ri_vef_add_face (retour, i, numedge_a, numedge_b);
- }
- free (listve);
- }
- }
- }
- //IDEM POUR LE SECOND POINT
- numvertex_a = retour->ed[i].ve2;
- for (int j = 0; j < retour->ve[numvertex_a].nbsharededges; j++)
- {
- int numedge_a = retour->ve[numvertex_a].sharededges[j];
- int numvertex_b = retour->ed[numedge_a].ve1;
- for (k = 0; k < retour->ve[numvertex_b].nbsharededges; k++)
- {
- int numedge_b = retour->ve[numvertex_b].sharededges[k];
- if (i != numedge_a && i != numedge_b && numedge_a != numedge_b)
- {
- listve = NULL;
- size = 0;
- list_int_add (&listve, &size, retour->ed[i].ve1,
- WITHOUT_REDUNDANCE);
- list_int_add (&listve, &size, retour->ed[i].ve2,
- WITHOUT_REDUNDANCE);
- list_int_add (&listve, &size, retour->ed[numedge_a].ve1,
- WITHOUT_REDUNDANCE);
- list_int_add (&listve, &size, retour->ed[numedge_a].ve2,
- WITHOUT_REDUNDANCE);
- list_int_add (&listve, &size, retour->ed[numedge_b].ve1,
- WITHOUT_REDUNDANCE);
- list_int_add (&listve, &size, retour->ed[numedge_b].ve2,
- WITHOUT_REDUNDANCE);
- if (size == 3)
- {
- if (a2ri_vef_search_face
- (retour, i, numedge_a, numedge_b) == -1
- && a2ri_vef_search_face (retour, i, numedge_b,
- numedge_a) == -1)
- a2ri_vef_add_face (retour, i, numedge_a, numedge_b);
- }
- free (listve);
- }
- }
- numvertex_b = retour->ed[numedge_a].ve2;
- for (k = 0; k < retour->ve[numvertex_b].nbsharededges; k++)
- {
- int numedge_b = retour->ve[numvertex_b].sharededges[k];
- if (i != numedge_a && i != numedge_b && numedge_a != numedge_b)
- {
- listve = NULL;
- size = 0;
- list_int_add (&listve, &size, retour->ed[i].ve1,
- WITHOUT_REDUNDANCE);
- list_int_add (&listve, &size, retour->ed[i].ve2,
- WITHOUT_REDUNDANCE);
- list_int_add (&listve, &size, retour->ed[numedge_a].ve1,
- WITHOUT_REDUNDANCE);
- list_int_add (&listve, &size, retour->ed[numedge_a].ve2,
- WITHOUT_REDUNDANCE);
- list_int_add (&listve, &size, retour->ed[numedge_b].ve1,
- WITHOUT_REDUNDANCE);
- list_int_add (&listve, &size, retour->ed[numedge_b].ve2,
- WITHOUT_REDUNDANCE);
- if (size == 3)
- {
- if (a2ri_vef_search_face
- (retour, i, numedge_a, numedge_b) == -1
- && a2ri_vef_search_face (retour, i, numedge_b,
- numedge_a) == -1)
- a2ri_vef_add_face (retour, i, numedge_a, numedge_b);
- }
- free (listve);
- }
- }
- }
- }
- return retour;
- }
- /**
- Calcul du graphe recouvrant minimal (EMST - Euclidean Minimal Spanning Tree)
- @param m le modele
- @return un modele contenant les aretes
- */
- vef_model *
- a2ri_vef_euclidean_minimal_spanning_tree (
- const vef_model * const m)
- {
- int *listedge = NULL,
- sizelistedge = 0,
- sizelistlongueur = 0;
- double *listlongueur = NULL;
- point3d p1,
- p2;
- vef_model *retour = (vef_model *) malloc (sizeof (vef_model));
- a2ri_erreur_critique_si (retour == NULL,
- "erreur allocation memoire pour retour\na2ri_vef_euclidean_minimal_spanning_tree");
- int *vnew = NULL,
- sizevnew = 0;
- int k,
- trouve,
- contve1,
- contve2;
- a2ri_vef_init (retour);
- for (int i = 0; i < m->nbvertex; i++)
- a2ri_vef_add_vertex (retour, m->ve[i].x, m->ve[i].y, m->ve[i].z);
- retour->xmin = m->xmin;
- retour->xmax = m->xmax;
- retour->ymin = m->ymin;
- retour->ymax = m->ymax;
- retour->zmin = m->zmin;
- retour->zmax = m->zmax;
- for (int i = 0; i < m->nbedge; i++)
- {
- point3d_init (&p1, m->ve[m->ed[i].ve1].x, m->ve[m->ed[i].ve1].y,
- m->ve[m->ed[i].ve1].z);
- point3d_init (&p2, m->ve[m->ed[i].ve2].x, m->ve[m->ed[i].ve2].y,
- m->ve[m->ed[i].ve2].z);
- list_int_add (&listedge, &sizelistedge, i, WITH_REDUNDANCE);
- list_double_add (&listlongueur, &sizelistlongueur,
- point3d_length (&p1, &p2), WITH_REDUNDANCE);
- }
- IFlist_edge_sort (listlongueur, listedge, sizelistedge);
- free (listlongueur);
- // Ajout du premier sommet dans la liste
- list_int_add (&vnew, &sizevnew, 0, WITH_REDUNDANCE);
- while (sizevnew != m->nbvertex)
- {
- k = 0;
- trouve = 0;
- while (!trouve)
- {
- do
- {
- contve1 =
- list_int_contains (vnew, sizevnew, m->ed[listedge[k]].ve1);
- contve2 =
- list_int_contains (vnew, sizevnew, m->ed[listedge[k]].ve2);
- k++;
- }
- while (contve1 == -1 && contve2 == -1);
- k--;
- if (contve1 != -1 && contve2 != -1)
- list_int_remove (&listedge, &sizelistedge, k);
- else
- trouve = 1;
- }
- a2ri_vef_add_edge (retour, m->ed[listedge[k]].ve1,
- m->ed[listedge[k]].ve2, 0);
- if (contve1 == -1)
- list_int_add (&vnew, &sizevnew, m->ed[listedge[k]].ve1,
- WITH_REDUNDANCE);
- else
- list_int_add (&vnew, &sizevnew, m->ed[listedge[k]].ve2,
- WITH_REDUNDANCE);
- list_int_remove (&listedge, &sizelistedge, k);
- }
- free (listedge);
- free (vnew);
- return retour;
- }
|