surface de l'intersection de deux triangles quelconques

**zekey** · 22/01/2007, 13h55

Bonjour,

je cherche un algo (pas forcément une implémentation) pour résoudre le problème suivant :
Calculer l'aire représentée par l'intersection de deux triangles.

Ce problème est certainement trivial mais je n'ai rien trouvé chez mon ami google.

Quelqu'un aurait-il une idée.

Merci d'avance

**Nemerle** · 22/01/2007, 20h42

http://bobuse.free.fr/Delaunay/

**khayyam90** · 22/01/2007, 20h50

Bien le bonsoir Steve,

Ce problème n'est pas si simple, en y réfléchissant rapidement, je classe les différents cas de la manière suivante (je recommande de faire des dessins) :
A et B deux triangles quelconques.
* aucun sommet de A n'est dans B et aucun sommet de B n'est dans A (1)
* un sommet de A est dans B et B n'a aucun sommet dans A (2)
* deux sommets de A sont dans B et aucun sommet de B n'est dans A (3)
* A est entièrement contenu dans B (4)
* A a un sommet dans B et B a un sommet dans A (5)

Il va déjà falloir un outil pour déterminer si un point est situé dans un triangle. Ca se fait en calculant la somme des angles orientés formés entre ce point et chacun des points du triangle. Le signe de la somme indique si le point est dedans ou dehors.
D'une manière similaire, on pourra faire un outil permettant de savoir si deux points sont situés de part et d'autre d'un triangle ou non.

Le cas (1) se divise encore en trois sous cas : A est à cheval sur B (1-1) , autrement dit un sommet d'un côté et les deux autres sommets de l'autre côté ; A est 'autour' de B (1-2) (les deux triangles forment une étoile de David) et A et B sont franchements disjoints (1-3).
(2) se divise aussi en deux cas : une étoile de David avec un sommet de A à l'intérieur de B (2-1) ; A 'pique' dans B (2-2)

Il va maintenant falloir déterminer le polygone commun aux deux triangles.

(1-3) nous donne une aire nulle, c'est le cas le plus simple.
Pour (1-1), il s'agit d'un quadrilatère. On détermine les 4 sommets en calculant les intersections entre les arrêtes des triangles.
Pour (1-2) c'est déjà plus compliqué. L'aire recherchée est un hexagone. Les sommets sont les intersections de toutes les arrêtes entre elles.
(2-1) il s'agit d'un pentagone P. Un sommet de P est le sommet de A présent dans B. Les autres sommets sont les intersections entre arrêtes.
(2-2) il s'agit d'un triangle T. Un sommet de T est le sommet de A qui est dans B, les deux autres sommets de T sont les intersections entre les arrêtes de A et celles de B.
Pour (3) il s'agit d'un quadrilatère Q. Les deux sommets de A présents dans B sont des sommets de Q. Les autres sommets sont (comme d'hab) les intersections entre les arrêtes de A et B
Pour (4) il s'agit d'un triangle, en l'occurence A.
Pour (5), c'est un quadrilatère, idem que pour les cas précédents, on connait 2 points, les deux autres points viennent d'intersections entre arrêtes.

Une fois qu'on connait la forme, il faut calculer son aire. Plusieurs méthodes existent, on peut par exemple tout ramener à des triangles (dont l'aire est simple à calculer). Tous les polygones obtenus sont convexes, on peut les trianguler simplement en créant des triangles fan autour du centre de gravité du polygone.

Donc pour résumer :
* déterminer dans quel cas tu te trouves
* déterminer le polygone d'intersection
* le trianguler et calculer l'aire des triangles.

Les cas où A et B ont une arrête en commun ou juste un morceau d'arrêtes sont englobés dans les cas précédents.

L'une des grosses difficultés sera de manipuler les points dans le bon ordre et de ne pas s'emméler les pinceaux.

En espérant ne pas avoir oublié de cas et être resté compréhensible.

**zekey** · 23/01/2007, 09h23

Envoyé par Nemerle

http://bobuse.free.fr/Delaunay/

Il me semblait que Delaunay permettait une triangulation d'une forme quelconque, je ne comprend pas l'intérêt dans le calcul de mon intersection de surface.

Merci khayyam90 pour ton temps et ton algo, c'est en effet avec cette solution que j'ai commencé, à ceci prêt que j'utilise le produit vectoriel pour déterminer l'inclusion ou l'exclusion. C'est en effet très compliqué et ça me semble extrêmement compliqué pour ce que cela doit faire (je suis informaticien pas mathématicien, ce qui implique que je suis fainéant CQFD).

J'ai également pensé à une solution analytique basée sur les équations de droites et les intégrales mais cela ne me mène pas bien loin parce que le problème des différents cas reste entier.

Je laisse le sujet encore un peu ouvert et puis je tag résolu. Merci pour votre temps.

**ToTo13** · 23/01/2007, 09h42

Bonjour,

je suis d'accord avec khayyam90, il faut faire plusieurs cas.

Donc :
- trouver le nombre de sommet du triangle A qui est dans B et inversement. C'est un simple calcul d'angle ou de déterminant.
- Selon le cas, calculer les intersections entre segments. C'est facile car c'est des morceaux de droites affines.
- Tu obtiens alors un polygone, sa surface est la réponse que tu souhaites.

L'ensemble des calculs n'est pas forcément très dur, le problème est de bien gére chaque cas.

**progfou** · 23/01/2007, 10h32

Pas certain d'avoir compris la question, mais une piste sans doute :
Si tu cherches la surface d'un triangle ABC, il suffit de connaître les positions des points A,B et C, puis de calculer les vecteur AB et AC (désolé pour les flèches, pas de LaTeX dans le forum

), puis le produit vectoriel entre ces deux vecteurs.
La norme de celui-ci divisée par deux te donne l'aire du triangle.

**Zavonen** · 24/01/2007, 12h59

Si vous pouvez vous contenter d'une approximation, il y a toujours cette bonne vieille méthode aléatoire dite de 'Monte-Carlo'.
Il est facile de tester l'appartenance d'un point à un triangle, donc à l'intersection de deux triangles.
Placez la surface à mesurer dans une enveloppe géométrique simple (rectangle, cercle,...). Déclenchez ensuite N tirs aléatoires sur cette enveloppe, comptez le nombre n de 'coups au but' (dans l'intersection) et faites le rapport sur le nombre total de tir p=N/n.
Si A est l'aire que vous cherchez et si S est la surface de l'enveloppe
A est à peu égal à Sxp.
La qualité du résultat dépend bien sûr du générateur pseudo-aléatoire et du nombre de tirs. Pour des intégrales on atteint très facilement le millième d'u.a.

**khayyam90** · 24/01/2007, 14h01

Oui, bien vu, je trouve ta réponse très pertinente. Ca se programme rapidement et les résultats ne sont pas mauvais du tout

**Kangourou** · 24/01/2007, 14h33

salut,

C'est quand meme mieux d'avoir une solution exacte quand c'est possible, non ?

Sinon je penser qu'on peut simplifier l'algo donne par khayyam90. L'idee est de construire la liste de points qui seront les sommets du polygone intersection.
On cree une liste vide et on ajoute:
- les sommets de A qui sont a l'interieur de B
- les sommets de B qui sont a l'interieur de A
- les intersections entre un segment de A et un segment de B, si elles existent

Le 3 eme cas necessite de calculer 9 intersections de segments, qui ne seront evidemment pas toutes des "vraies" intersections (segments qui ne se coupent pas). Il faut donc une procedure qui calcule l'intersection de 2 segments et qui renvoie une valeur specifique si les segments ne se croisent pas.

Ensuite, il faut ordonner les points dans le sens du contour. Une solution consiste a calculer le centre de gavite du nuage de points, a calculer l'angle de chaque point du nuage par rapport a ce centre, puis a trier les points selon cet angle.

Enfin, calcul de l'aire, cf. khayyam90.

Il me semble d'ailleurs que c'est generalisable a l'intersection de 2 polygones convexes.

**Zavonen** · 24/01/2007, 15h26

Voici donc une méthode 'déterministe' basée sur les techniques d'intégration. L'avantage est de faire l'économie de l'étude des positions respectives des deux triangles.
Appelons donc ABC le premier triangle et DEF le second.
Choisissons un pas p =1/n ( n étant un entier qu'on peut choisir aussi grand qu'on veut).
On considère les vecteurs:
DE' = (1-p)DE
DF'=(1-p)DF
(Excusez je ne sais pas mettre les flèches)
Ainsi le triangle DEF peut être considéré comme la réunion du triangle DE'F' et d'une "bande" trapézoïdale EE'F'F , dont la surface est sensiblement:
ds=valeur absolue du déterminant de (EE', EF).
Ces approximations sont d'autant plus justes que p est petit.
Il s'agit maintenant de déterminer quelle portion de cette bande est dans l'intersection des deux triangles.
Pour cela on remonte le segment EF de E vers F par exemple par une suite de points distants de EF/n et à chaque fois on teste l'appartenance à l'intersection. On arrive ainsi à une certaine proportion q de points de la bande appartenant à l'intersection. On estime donc la contribution de la bande à la surface totale de l'intersection à q*ds.
Il suffit ensuite d'itérer le processus.
Si ce n'est pas clair faites un dessin.

**pseudocode** · 24/01/2007, 21h29

Je vais peut-etre (sans doute

) dire une enorme betise, mais c'est pas juste une variante du sweepline de Bentley-Ottmann ?

En fait, il s'agit de calculer les points d'intersections de chaque segment du triangle 1 avec ceux du triangle 2, puis de construire le "polygone" commun aux 2 triangles. Apres le calcul de l'aire ne devrait pas etre trop compiqué (a priori le polygone sera convexe).

**Zavonen** · 24/01/2007, 22h42

Envoyé par pseudocode

Je vais peut-etre (sans doute

) dire une enorme betise, mais c'est pas juste une variante du sweepline de Bentley-Ottmann?

C'est bien possible, mais je n'en ai jamais entendu parler. De mon point de vue c'est bien plus simple. Il s'agit de l'application directe d'un théorème sur le calcul intégral, vieux de deux siècles, qui dit que dans certaines conditions, on peut remplacer une intégrale double par une intégrale simple. En clair si vous voulez calculer une surface S, balayez cette surface par une droite Dx se déplaçant parallèlement à une direction donnée, suivant un paramètre x variant entre deux bornes a et b, appelez f(x) la longueur du segment intersection de la doite Dx avec S, S sera l'intégrale entre a et b de f(x). En résumé, s'il fallait rendre à César, je dirais plutôt merci à Leibniz, Newton et Riemann, sans même déranger Lebesgue.

**Kangourou** · 25/01/2007, 09h38

Envoyé par pseudocode

En fait, il s'agit de calculer les points d'intersections de chaque segment du triangle 1 avec ceux du triangle 2, puis de construire le "polygone" commun aux 2 triangles. Apres le calcul de l'aire ne devrait pas etre trop compiqué (a priori le polygone sera convexe).

Tout a fait d'accord.

Pourquoi preferer une approximation qui va converger au bout de N iterations, avec toujours un ecart residuel, alors qu'on a une methode qui donne la valeur exacte avec un nombre reduit de calcul ?

**pseudocode** · 25/01/2007, 09h41

Envoyé par Zavonen

En clair si vous voulez calculer une surface S, balayez cette surface par une droite Dx se déplaçant parallèlement à une direction donnée

C'est marrant, en déplacant la droite Dx verticalement on arrive a la technique des algo "scanline".

Mais ca nous donne une approximation de l'aire, et pas la valeur exacte.

Apres avoir reflechi un peu au probleme, je pense que trouver les sommets du polygone commun est une solution simple et automatisable.

Les sommets de ce polygone sont:
les (eventuels) points d'intersection segment/segment des 2 triangles
+ les (eventuels) sommets du triangle A a l'interieur du triangle B
+ les (eventuels) sommets du triangle B a l'interieur du triangle A

...ce qui devrait nous donner une liste de 0,3,4,5 ou 6 points (

).

Le polygone devrait etre convexe (une histoire de topologie des compact fermés de R2

), donc pour calculer sa surface on a le choix des methodes. Par exemple calculer le barycentre, et additionner les surfaces des triangles formant le maillage.

**Zavonen** · 25/01/2007, 19h03

Le polygone devrait etre convexe (une histoire de topologie des compact fermés de R2 )

Oui le polygone est convexe, car c'est une intersection de demi-plans, lesquels sont tous convexes, et la convexité se conserve par intersection (pas de besoin de compacité ni aucun autre argument topologique).
L'intérieur d'un triangle est lui-même défini comme l'inter. de 3 demi-plans.
Pour une étude exhaustive, il faut commencer par l'intersection d'un triangle avec un demi plan défini par une droite (un support d'un des côtés du deuxième triangle), si la droite ne passe par aucun des somments existants la figure obtenue dépend de la "partition" des 3 sommets existants.
3 - 0 donne triangle ou rien
2-1 donne quadrilatère ou triangle
Si la droite passe par deux sommets on a triangle ou rien
Si la droite passe par un sommet on a 2 possibilités:
triangle - triangle
triangle - rien
On a en fait qu'un seul cas nouveau généré :le quadrilatère.
On répète l'argument encore deux fois
Et on doit arriver à la classification suivante, et sans prendre le temps de le vérifier j'imagine qu'on arrive en théorie soit à
Un hexagone
Un pentagone
Un quadrilatère
Un triangle
Rien

...ce qui devrait nous donner une liste de 0,3,4,5 ou 6 points ().

Ce qui fait que je suis tout à fait d'accord avec vous.

je pense que trouver les sommets du polygone commun est une solution simple et automatisable.

Automatisable, pour sûr, simple ???
Si une demi droite a pour équation ux+vy+w=0
Les deux demi-plans qu'elle délimite sont caractérisés par:
ux+vy+w>0
ux+vy+w<0
On coupe donc d'abord le triangle ABC par la droite (DE) et on conserve la partie qui se trouve du côté de F. Pour savoir ce qu'est cette partie, il faut partir de l'équation ux+vy+w=0 de la droite (DE) remplacer x et y par les cordonnées de F on obtient ainsi un signe + ou -
On fait le même calcul pour les points A, B, C en fonction du signe trouvé on sait quels sont les points qui sont du même côté de (DE) que F.
Dans le cas de la partition 2-1 on a évidement à calculer les coordonnées des points d'intersection de (DE) avec deux autres droites prises parmi (AB) (BC) (AC), cest le 'pire' cas conduisant à un quadrilatère ou un nouveau triangle.
Ensuite on refait la même chose à partir du polygône obtenu, de la droite (DF) et du sommet E.
On termine évidemment par (EF) et le sommet D.
L'idée est donc de couper à répétition des polygones par des demi-plans.
Les calculs à conduire sont simples, le plus compliqué étant les intersections de droites (deux équations deux inconnues premier degré), ou des équations de droites (idem).
Pour finir votre suggestion:

Par exemple calculer le barycentre, et additionner les surfaces des triangles formant le maillage.

me paraît plus que raisonnable.
Vous vouliez dire sans doute isobarycentre ou centre de gravité

**pseudocode** · 25/01/2007, 20h03

@Zavonen: désolé mais je n'ai pas le niveau suffisant en math/geometrie pour poursuivre cette conversation

. J'ai juste pensé a cet methode algo hier. Quand a l'explication "topologique" c'etait plus une boutade qu'autre chose

**Zavonen** · 25/01/2007, 20h58

Envoyé par pseudocode

@Zavonen: désolé mais je n'ai pas le niveau suffisant en math/geometrie pour poursuivre cette conversation

. J'ai juste pensé a cet methode algo hier. Quand a l'explication "topologique" c'etait plus une boutade qu'autre chose

Mais vous avez du bon sens ! Je crois que votre post m'a (re)conforté dans l'idée, qu'on pouvait trouver une solution purement géométrique. Qui veut la rédiger après nos derniers messages le pourra.
Pour moi c'est un problème résolu, en partie grâce à vous, et il ne m'intéresse plus
N'ayez à l'avenir aucun complexe.

**pseudocode** · 25/01/2007, 22h54

Envoyé par Zavonen

N'ayez à l'avenir aucun complexe.

Arf. Non y a pas de risque.

C'est juste que j'ai une approche "visuelle" de ce genre de problemes et pas "abstraite". Probablement car j'ai rencontré ces problemes lors du codage d'algo de dessin en 2D. Ah! le bon vieux temps des tracés de ligne/surface en asssembleur sur mon Atari ST... vintage...

**Zavonen** · 27/01/2007, 11h46

Voici une implémentation de l'algo décrit dans mon dernier post:

Code :

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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
#include <iostream>
 
// modélisation des points dans un plan rapporté à un repère
class CPoint
{
private:
    double x; // l'abscisse
    double y; // l'ordonnée
    int flag ; // flag utilisé comme marqueur pour savoir si le point appartient à un demi-plan
public:
// constructeur par défaut
    CPoint()
    {
        x=y=0;
        flag=0;
    };
// constructeur évident
    CPoint( double u, double v)
    {
        x=u;
        y=v;
        flag=0;
    }
// affichage sur console
    void Affiche ()
    {
        std::cout<<"\n"<<"("<<x<<","<<y<<") - "<<flag;
    }
// Accès aux données
    double Getx()
    {
        return x;
    }
    double Gety()
    {
        return y;
    }
    int GetFlag()
    {
        return flag;
    }
// affectation
    void operator= (CPoint M)
    {
        x=M.x;
        y=M.y;
        flag=M.flag;
    }
    // Pour affecter la donnée flag
    void SetFlag (int n)
    {
        flag=n;
    }
};
 
// modélisation d'une droite définie par deux points
class CDroite
{
private:
    CPoint A;
    CPoint B;
    // les coefficients de l'équation ux+vy+w=0 représentant la droite
    double u;
    double v;
    double w;
public:
    // Constructeur par défaut
    CDroite()
    {};
    // le constructeur évident
    CDroite (CPoint P, CPoint Q)
    {
        A=P;
        B=Q;
        // calcul instantané de l'équation
        u=A.Gety()-B.Gety();
        v=B.Getx()-A.Getx();
        w=A.Getx()*B.Gety()-A.Gety()*B.Getx();
 
    }
    // Affichage de l'équation
    void Affiche ()
    {
        std::cout<<"\n("<<u<<")x+("<<v<<")y+("<<w<<")=0";
    }
    // surcharge de * pour désigner l'intersection de deux droites
    CPoint operator* (CDroite Other)
    {
        double x,y,d;
        d=Other.u*v-u*Other.v;
        y=(u*Other.w-Other.u*w)/d;
        x=-(v*Other.w-w*Other.v)/d;
        CPoint P(x,y);
        return P;
    }
    // Calcule l'expression ux+vy+w pour un point P(x,y) déterminant ainsi de quel côté de la droite le point se trouve
    double Eval (CPoint P)
    {
        return u*P.Getx()+v*P.Gety()+w;
    }
 
 
};
 
// modélisation d'un demi plan par une droite et un point n'appartenant pas à cette droite
// définissant donc le 'bon côté' de la droite - celui où il se trouve
class CPolygone; // déclaration anticipée pour la méthode de marquage
 
class CDemiPlan
{
private:
    CDroite D; // La frontière
    CPoint P; // le point désignant le demi-plan à conserver
public:
    // constructeurs
    CDemiPlan()
    {} // par défaut ne fait rien
    // initialisation avec une droite et n point
    CDemiPlan(CDroite F, CPoint Q)
    {
        D=F;
        P=Q;
    }
    // accès aux données membres
    CDroite GetDroite()
    {
        return D;
    }
    CPoint GetPoint()
    {
        return P;
    }
    // Visualisation des données
    void Affiche()
    {
        D.Affiche();
        P.Affiche();
    }
    // marquage d'un point par son flag comme appartenant au demi-plan ou non
    void Marque (CPoint * pP)
    {
        double x=D.Eval(*pP);
        double y=D.Eval(P);
        if (x*y<0) pP->SetFlag(-1); // mauvais côté
        else if (x==0) pP->SetFlag(0);// point sur la frontière
        else pP->SetFlag(1); // bon côté
    }
 
};
 
// Cette classe doit servir pour la définition des  listes chaînées représentant les polygônes
class CPolyNoeud
{
private:
    CPoint * Sommet; // le sommet actuel
    CPolyNoeud * Suivant; // Pointeur sur le suivant
    friend class CPolygone; // la classe suivante peut manipuler les données privées
public:
// constructeur par défaut
    CPolyNoeud()
    {
        Sommet=NULL;
        Suivant=NULL;
    }
// affectation du sommet
    void SetSommet(CPoint& P)
    {
        Sommet=&P;
    }
// affectation du suivant
    void SetSuivant(CPolyNoeud * pPN)
    {
        Suivant =pPN;
    }
// affichage du sommet
    void Affiche ()
    {
        (*Sommet).Affiche();
    }
};
 
// Un polygone est une liste chaînée de CPolyNoeuds
// elle est entièrement caractérisée par le noeud de tête
class CPolygone
{
private:
    CPolyNoeud * T;
public:
// constructeur par défaut
    CPolygone()
    {
        T=NULL;
    }
// constructeur à partir d'un noeud unique
    CPolygone(CPolyNoeud * pPN)
    {
        T=new CPolyNoeud();
        T->Sommet=pPN->Sommet;
        T->Suivant=NULL;
 
    }
// constructeur à partir d'un tableau de n points
    CPolygone (CPoint * Tab, int n)
    {
        T=NULL;
        CPolyNoeud *pPN1, *pPN2;
        if (!n) return ;
        else
        {
            pPN1=new CPolyNoeud();
            pPN1->SetSommet(Tab[0]);
            T=pPN1;
        }
 
        for (int i=1; i<n; i++)
        {
            pPN2= new CPolyNoeud();
            pPN2->SetSommet(Tab[i]);
            pPN1->SetSuivant(pPN2);
            pPN1=pPN2;
        }
 
    }
    void Append (CPolyNoeud * pLast)
    {
        CPolyNoeud *pPN;
        pPN=T ;
        while (pPN->Suivant) pPN=pPN->Suivant;
        CPolyNoeud * Dernier= new CPolyNoeud();
        Dernier->Sommet=pLast->Sommet;
        Dernier->Suivant=NULL;
        pPN->Suivant=Dernier;
 
    }
    // Comptage du nombre de sommets
    int NombreSommets()
    {
        if (!T) return 0;
        int nbre=0;
        CPolyNoeud * pPN;
        pPN=T;
        while (pPN)
        {
            nbre ++;
            pPN=pPN->Suivant;
        }
        return nbre;
    }
// Comptage du nombre de flags >=0
    int NombreFlagsP()
    {
        if (!T) return 0;
        int nbre=0;
        CPolyNoeud * pPN;
        pPN=T;
        while (pPN)
        {
            if ((pPN->Sommet)->GetFlag()>=0) nbre++;
            pPN=pPN->Suivant;
        }
        return nbre;
    }
// Comptage du nombre de flags <=0
    int NombreFlagsN()
    {
        if (!T) return 0;
        int nbre=0;
        CPolyNoeud * pPN;
        pPN=T;
        while (pPN)
        {
            if ((pPN->Sommet)->GetFlag()<=0) nbre++;
            pPN=pPN->Suivant;
        }
        return nbre;
    }
 
    // Comptage du nombre de points sur la frontière
    int NombreFlags0()
    {
        if (!T) return 0;
        int nbre=0;
        CPolyNoeud * pPN;
        pPN=T;
        while (pPN)
        {
            if ((pPN->Sommet)->GetFlag()==0) nbre++;
            pPN=pPN->Suivant;
        }
        return nbre;
    }
// Comptage du nombre de franchissements
    int NombreCross()
    {
        int nbre=0;
        CPolyNoeud * pPN1,* pPN2;
        pPN1=T;
        pPN2=pPN1->Suivant;
        while (pPN2)
        {
            if (Traverse(pPN1,pPN2)) nbre++;
            pPN1=pPN2;
            pPN2=pPN2->Suivant;
        }
        return nbre;
    }
 
    CPoint IsoBarycentre()
    {
        double sx=0, sy=0;
        CPolyNoeud * pPN=T;
        int n=NombreSommets();
        while (pPN->Suivant)
        {
            sx+=(pPN->Sommet)->Getx();
            sy+=(pPN->Sommet)->Gety();
            pPN=pPN->Suivant;
        }
        CPoint G( sx/(n-1),sy/(n-1));
        return G;
    }
 
    // Calcul de la surface - le polygone est supposé convexe
    // on découpe en triangles
    // finalement sans utiliser le barycentre
    double Surface ()
    {
        if (NombreSommets()<3) return 0;
        double s=0;
        double ds;
        double x0,x1, y0,y1, x2,y2;
        CPolyNoeud * pPN0=T;
        CPolyNoeud * pPN1=T->Suivant;
        CPolyNoeud * pPN2=pPN1->Suivant;
        x0=pPN0->Sommet->Getx();
        y0=pPN0->Sommet->Gety();
        while (pPN2->Suivant)
        {
            x1=pPN1->Sommet->Getx();
            y1=pPN1->Sommet->Gety();
            x2=pPN2->Sommet->Getx();
            y2=pPN2->Sommet->Gety();
            ds=((x1-x0)*(y2-y0)-(y1-y0)*(x2-x0))/2 ;
            if (ds>0)s+=ds;
            else s-=ds;
            pPN1=pPN2;
            pPN2=pPN2->Suivant;
        }
        return s;
    }
 
// Accès aux données privées:
// retourne le sommet d'indice n
    CPolyNoeud* Get (int n)
    {
        CPolyNoeud * pPN=T;
        for (int i=0; i<n;i++)
            pPN=pPN->Suivant;
        return pPN;
    }
 
 
// affichage d'un polygone
    void Affiche()
    {
        CPolyNoeud* pPN;
        CPoint G=IsoBarycentre();
        if (!T) return; // polygone vide
        else
        {
            pPN=T;
            std::cout<<"\n"<<"Nombre de sommets: "<<NombreSommets()<<"\n";
            std::cout<<"\n"<<"Centre de gravite :";
            G.Affiche();
            std::cout<<"\n"<<"Surface: "<<Surface()<<"\n";
            std::cout<<"\nSommets:";
            while (pPN)
            {
                pPN->Affiche();
                pPN=pPN->Suivant;
            }
 
        }
    }
 
 
 
// marquage +1  -1  0 des sommets par un demi-plan
    void Marque(CDemiPlan * pH)
    {
        if (T==NULL) return ; // rien à faire
        CPolyNoeud * pPN=T;
// sinon marquer les sommets les uns après les autres
        while (pPN)
        {
            pH->Marque(pPN->Sommet);
            pPN=pPN->Suivant;
        }
    }
 
// Vérifie si on traverse la frontière pour passer de *PPN1 à *pPN2
    bool Traverse(CPolyNoeud * pPN1, CPolyNoeud *pPN2)
    {
        return (pPN1->Sommet->GetFlag())*(pPN2->Sommet->GetFlag())==-1;
 
    }
 
// Intersection d'un côté du polygone avec la frontière du demi-plan
// A calculer quand le côté traverse la frontière
    CPoint Inter (CPolyNoeud * pPN1, CPolyNoeud *pPN2,CDemiPlan& H)
    {
        CDroite D1=H.GetDroite();
        CDroite D2=CDroite(*(pPN1->Sommet),*(pPN2->Sommet));
        return D1*D2; // désigne l'intersection de deux droites par surcharge
    }
 
 
// surcharge de * pour calculer l'intersection d'un polygone convexe et d'un demi plan
    CPolygone& operator* (CDemiPlan& H)
    {
        CPolygone * Vide= new CPolygone();
        Marque(&H);
        if (NombreSommets()<3) return *Vide; // l'intersection est de dim <2
        Marque(&H);
        if (NombreFlagsP()<=0) return *Vide ; // tout est du mauvais côté, donc rien!
        if (NombreFlagsP()==NombreSommets()) return *this; // tout est du bon côté on garde tout
        // Si on arrive ici c'est que le polygone est de part et d'autre de la frontière
        // Il y a alors un ou deux franchissements
        // pas plus à cause de la convexité
        // Nous allons les détecter et insérer de nouveaux sommets
        int n=NombreSommets()+NombreCross();
        CPoint * Tableau1 = new CPoint [n];
        CPolyNoeud * pPN1,* pPN2;
        pPN1=T;
        pPN2=pPN1->Suivant;
        int i=0;
        Tableau1[i++]=*(pPN1->Sommet);
        while (pPN2)
        {
            if (Traverse(pPN1,pPN2))
                Tableau1[i++]=Inter(pPN1,pPN2,H);
            Tableau1[i++]=*(pPN2->Sommet);
            pPN1=pPN2;
            pPN2=pPN2->Suivant;
        }
        // Comptage des sommets situés du bon côté sauf le dernier
        int m =0;
        for (int i=0;i<n-1;i++)
            if (Tableau1[i].GetFlag()>=0) m++;
        m++; //pour boucler
        // récupération de ces sommets
        CPoint * Tableau2 = new CPoint [m];
        for (int i=0, j=0;i<n-1;i++)
        {
            if (Tableau1[i].GetFlag()>=0)
                Tableau2[j++]=Tableau1[i];
        }
        Tableau2[m-1]=Tableau2[0]; // on ferme
        // fabrication d'un polygone avec ces points
        CPolygone * I = new CPolygone(Tableau2,m);
 
        return *I;
    }
 
};
 
 
 
// Ce programme calcule l'intersection du triangle ABC
// avec le triangle DEF
// ainsi que sa surface
int main()
{
    // Sommets du premier triangle
    CPoint A(0,1);
    CPoint B(1,-1);
    CPoint C(-1,-1);
    // Sommets du second
    CPoint D(0,-1);
    CPoint E(-1,1);
    CPoint F(1,1);
    // Fabrication d'un polygone en deux temps
    CPoint Triangle[4]={A,B,C,A}; // pour fermer le polygone
    CPolygone P1(Triangle,4);
    // Le travail commence maintenant
    CDroite Delta1(D,E);
    CDemiPlan H1(Delta1,F);
    CPolygone P2 = P1*H1; //On coupe par un premier demi-plan
    CDroite Delta2(D,F);
    CDemiPlan H2(Delta2,E);
    CPolygone P3 =P2*H2; // puis par un second
    CDroite Delta3(E,F);
    CDemiPlan H3(Delta3,D);
    CPolygone P4=P3*H3;// puis par un troisième
    P4.Affiche(); // Voir le résultat
 
 
    return 0;
}

**coyotte507** · 27/01/2007, 22h38

Je suis d'accord avec pseudo-code

Calculer les intersection des segments du triangle est très simple. Pour calculer l'aire du polygone il suffit de le découper en triangles ensuites. (de toute facon le polygone sera toujours convexe donc l'ordre des points sera assez facile à déterminer)

Après il faut aussi rajouter les sommets des triangles originaux, mais pour ca il suffit de faire un simple test pour voir si ils "appartiennent" à l'autre triangle.

Enfin, voila une autre solution mois élégante mais beaucoup plus facile à coder

On prend les deux triangles sur des surfaces différentes, on les mets à moitié transparents, et on superpose les surfaces ^^. Reste à faire l'inventaire des pixels de mi-couleur.

surface de l'intersection de deux triangles quelconques

Mathématiques

Discussions similaires

Partager

Partager