Discussion :

[souviron34]

Bon , ça m'a pris un peu de temps, mais il a fallu que je fasse pas mal d'édition par rapport à mon original.

Je note 5 points principaux :

1. La méthode est "méthode incrémentale Delete and Build" (voir les commentaires dans le code. Elle a un incconvénient, elle prend plus de temps que par exemple Divide & Conquer. ou Sweep. Cependant, on le re-gagne ensuite, car ces méthodes obligent à tout recalculer si on ajoute ou enlève un point, alors que l'incrémental non. Je fournis d'ailleurs les routines pour ajouter ou enlever un point du réseau (référé par son uméro dans le buffer de points initial)
   
   
2. Comme pour tous les autres exemples existants, j'ai pris une enveloppe convexe. Dans mes algos à moi, j'avais envisagé le cas d'une enveloppe concave, ce qui complexifie pas mal les calculs. Si quelqu'un le souhaite, je met à disposition, mais le code a environ 5 à 600 lignes de plus.
   
   
3. Au vu des figures que j'avais, j'aimerais savoir si vous avez la même chose (problème) que j'ai eu avec la routine InCircle, lorsque les triangles sont extrêmement aplatis ou allongés (oui, j'avais des données "étranges"). Là aussi, il m'avait fallu ajouter du code pour tester "manuellement". Je ne l'ai pas inclus, mais là encore je le tiens à disposition (à moins que cela soit la routine que j'avais récupéré ??).
   
   
4. Egalement, dans mon code original, je faisais ressortir les indices du contour extérieur , ce qui évitait de les recalculer si besoin était (accélarération). Je ne l'ai pas inclus, mais là encore je le tiens à disposition.
   
   
5. Il y a 2 possibilités de structures de triangle, suivant que l'on veut optimiser en vitesse ou en mémoire utilisée. Par défaut la structure est optimisée en vitesse. Si on veut optimiser en mémoire utilisée, il faut rajouter un flag OPTIMIZED_MEMORY à la compil.

NOTE : le code étant trop long pour tenir dans un seul message, j'ai mis le code en 2 messages (la triangulation proprement dite est dans le suivant).


Maintenant voici :

TriStructs.h

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
 
/****************************************************************
*****************************************************************
*****************************************************************
 
 
     TriStructs.h :  Ce module contient l'"include file" des
                     structures utilisées pour le calcul de triangulation. 
 
       Copyright : Environnement Canada & COGITECH Jean Souviron 2000
        Auteur    : Jean Souviron (COGITECH Jean Souviron)
                    Janvier 2000
 
        Please insert these copyrights in each code where you use 
        part of this software. Failure to do so is a direct violation of the
        international copyright laws.
 
*****************************************************************
*****************************************************************
*****************************************************************
*/
 
 
#ifndef _JS_TRIANGSTRUCTS
#define _JS_TRIANGSTRUCTS
 
 
/* Structure de point utilisée */
typedef struct  _GeoPt {
 
        double     X ;
        double     Y ;
 
} GeoPt ;
 
 
 
/* Structure des triangles */
typedef struct _Triangle {
 
  int                S1 ;
  int                S2 ;
  int                S3 ;
 
#ifndef OPTIMIZED_MEMORY
  GeoPt              Center ;
  double             R ;
#endif
 
  struct _Triangle  *next ;
  struct _Triangle  *previous ;
 
} Triangle ;
 
 
 
 
 
#ifndef ERROR
#define ERROR 1
#endif
#ifndef SUCCESS
#define SUCCESS 0
#endif
 
 
 
 
#endif

Triangle.h

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
/****************************************************************
*****************************************************************
*****************************************************************
 
 
     Triangle.h :  Ce module contient l'"include file" des routines
                      publiques de calcul de triangulation. 
 
       Copyright : Environnement Canada & COGITECH Jean Souviron 2000
        Auteur    : Jean Souviron (COGITECH Jean Souviron)
                    Janvier 2000
 
        Please insert these copyrights in each code where you use 
        part of this software. Failure to do so is a direct violation of the
        international copyright laws.
 
 
*****************************************************************
*****************************************************************
*****************************************************************
*/
 
 
#ifndef _JS_TRIANGULATION
#define _JS_TRIANGULATION
 
#include "TriStructs.h"
 
 
 
extern int     Triangulate ( GeoPt *Pts, int N_Pts,
			     Triangle **Triangles, int *N_Triangles );
 
extern int     RemovesOnePointToTriangulation ( int num, GeoPt *Pts,
					        Triangle **Triangles, 
						int *N_Triangles );
 
extern int     AddsOnePointToTriangulation    ( int num, GeoPt *Pts,
						Triangle **Triangles, 
						int *N_Triangles );
 
 
 
#endif

Et enfin un exemple (absurde à cause des points, qui sont aléatoires) d'utilisation :

TriMain.c

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
 
/****************************************************************
*****************************************************************
*****************************************************************
 
 
    Ce module contient un exemple d'utilisation de la triangulation
 
       Copyright : Environnement Canada & COGITECH Jean Souviron 2000
        Auteur    : Jean Souviron (COGITECH Jean Souviron)
                    Janvier 2000
 
        Please insert these copyrights in each code where you use 
        part of this software. Failure to do so is a direct violation of the
        international copyright laws.
 
*****************************************************************
*****************************************************************
*****************************************************************
*/
 
#include <stdlib.h>
#include <stdio.h>
 
#include "Triangle.h"
 
 
 
int main ( int argc, char **argv )
{
  GeoPt        Pts[100] ;
  int          i, N_Triangles = 0, N_Pts = 100 ;
  Triangle    *Triangles = (Triangle *)NULL, *elt = (Triangle *)NULL ;
  Triangle    *next = (Triangle *)NULL ;
 
 
/*
--- Rempli le buffer de points
*/
  for ( i = 0 ; i < 100 ; i++ )
    {
      Pts[i].X = 30.0 + 40.0 *((double)rand()/RAND_MAX) ;
      Pts[i].Y = 10.0 + 80.0 *((double)rand()/RAND_MAX) ;
    }
 
 
/*
--- Triangulate to find the total number of triangles to watch
*/
  i = Triangulate ( Pts, N_Pts, &Triangles, &N_Triangles );
  if ( (i == ERROR) || (N_Triangles == 0) )
    {
      return 0 ;
    }
 
 
/*
--- Affiche les triangles
*/
  elt = Triangles ;
  while ( elt != (Triangle *)NULL )
    {
      fprintf (stderr, "Sommets [1] %g,%g  [2] %g,%g [3] %g %g\n",
	       Pts[elt->S1].X, Pts[elt->S1].Y,
	       Pts[elt->S2].X, Pts[elt->S2].Y,
	       Pts[elt->S3].X, Pts[elt->S3].Y );
 
      elt = elt->next ;
    }
 
 
/*
--- Frees the triangles
*/
  elt = Triangles ;
  while ( elt != (Triangle *)NULL )
    {
      next = elt->next ;
 
      free ( elt ) ;
 
      elt = next ;
    }
 
 
  return 1 ;
}