Discussion :

[BeanzMaster]

Bonjour wiwaxia merci pour toutes ces explications

J'ai compris ma "bêtise"

Effectivement avec ce polygone



avec ma fonction Function TBZ2DPolygonTool.IsConvex : Boolean;
Celui-ci est considéré, comme convex, alors qu'il ne l'est pas, mais c'est normal, l'algorithme ne traitant pas les intersections

J'ai donc fais un test simple pour les polygones complexes en cherchant pour chaque segments si une intersection existait ou si il y a un recouvrement.

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
Function TBZ2DPolygonTool.IsComplex : Boolean;
var
  EdgeList : TBZ2DEdgeList;
  I, J, K : Integer;
begin
  Result := False;
  EdgeList := TBZ2DEdgeList.Create;
  K := GetEdgeList(EdgeList);
  For I := 0 to K-1 do
  begin
    For J := 1 to K - 2 do
    begin
      if (I <> J) then
      begin
        if EdgeList.Items[I].IntersectWithLine(EdgeList.Items[J]) then
        begin
          Result := True;
          FreeAndNil(EdgeList);
          Exit;
        end;
      end;
    end;
  end;
end;
 
Function TBZ2DPolygonTool.GetPolygonType : TBZ2DPolygonType;
Begin
  if not(IsComplex) then
  begin
    if IsConvex then Result := ptConvex else result := ptConcave;
  end
  else result := ptComplex;
End;

J'ai testé avec plusieurs polygone et TBZ2DPolygonTool.GetPolygonType me retourne bien le bon type. Par exemple avec ton exemple de polygone générer aléatoirement celui me retourne bien qu'il est concave

Pour le problème de la rasterization, j'ai trouvé sur le web un autre moyen. Je vais essayé convertir un polygone complexe en réordonnant les segments, et en ajoutant ou supprimant certain segment au besoin en un polygone simple convexe ou concave. Je vais voir comment m'y prendre.

Bon dimanche

Jérôme

[wiwaxia]

Je reprends la suite des réponses à tes remarques, dont il m'a fallu provisoirement décrocher.

2°) Le nombre (N_t) de tours effectués caractérisant un polygone résulte de la sommation étendue à tous les sommets (1 ≤ i ≤ N) de l'angle polaire:

θ_i = (P_hP_i, P_iP_j) _{avec h = i - 1 si (1<i) sinon h = N et j = i + 1 si (i<N) sinon j = 1} ,

qui conduit à un angle total A_tot = Σ_i=1^N(θ_i) = 2π.N_t .

Les deux termes sont positifs lorsque la succession des sommets réalise un enroulement dans le sens direct, négatif dans le cas contraire.

Le polygone est convexe si tous les termes (θ_i) sont de même signe - voilà une autre définition de la convexité, et une réponse à l'une de tes questions:

... En attendant, j'ai quand même une petite question. Peut-on se servir de ta méthode "NTours" pour savoir si un polygone est concave ? si oui comment procéder ? ...

Si cette condition est réalisée, le polygone présente au minimum (⌡N_t⌡ - 1) points d'auto-intersection (fig I : N_t = +4 , N_int = 3); le débordement éventuel d'une boucle sur une autre fait apparaître un nombre pair de points supplémentaires (fig II : N_t = +1 , N_int = 2).
Il intervient donc déjà dans ce cas simple une relation du type N_int = (⌡N_t⌡ - 1) MOD 2 .

3°) Un retournement de boucle (fig III : N_t = 0 , N_int = 1), plus difficile à caractériser, fait apparaître un point supplémentaire d'auto-intersection; c'est pourquoi il paraît difficile d'échapper au dénombrement de croisements d'arêtes que tu sembles redouter

... ce qui m'éviterai de mettre en place un test des intersections des segments par "brute-force" (tes des segment un à un) ou au pire j'essayerai d'implémenter l'algorithme décrit ...

mais qui n'est pas au bout du monde - je le détaillerai, éventuellement.
Il intervient alors une double sommation de la forme

N_int = Σ_h=1^N-2(Σ_j=h+2^NIntersect(P_hP_i, P_jP_k)) ,

dans laquelle:

i = h + 1 , k = j + 1 si (j<N) sinon j = 1

et

Intersect(AB, CD) vaut 1 si les deux segments présentent un point d'intersection, zéro dans le cas contraire.

[BeanzMaster]

Bonjour,

Je reprends la suite des réponses à tes remarques, dont il m'a fallu provisoirement décrocher.

Pas de problèmes ne t'inquiètes pas. Je te remercie encore de prendre au tant de temps pour détailler et expliquer, (Même si, je dois l'avouer mon cerveau a du mal à tout visualiser et comprendre correctement)

3°) Un retournement de boucle (fig III : N_t = 0 , N_int = 1), plus difficile à caractériser, fait apparaître un point supplémentaire d'auto-intersection; c'est pourquoi il paraît difficile d'échapper au dénombrement de croisements d'arêtes que tu sembles redouter

Tu tapes dans le mille. Ce que je peux conclure c'est que c'est possible avec ta fonction NTours, sauf qu'il faut prendre en comptes les différents cas de figures, ce qui alourdirai grandement l'algorithme et qu'il devient complexe d'avoir un solution viable à 100%. De plus le temps d'exécution en serait grandement pénaliser, à la vue du nombre de boucles nécessaires.

mais qui n'est pas au bout du monde - je le détaillerai, éventuellement.
Il intervient alors une double sommation de la forme

N_int = Σ_h=1^N-2(Σ_j=h+2^NIntersect(P_hP_i, P_jP_k)) ,

dans laquelle:

i = h + 1 , k = j + 1 si (j<N) sinon j = 1

et

Intersect(AB, CD) vaut 1 si les deux segments présentent un point d'intersection, zéro dans le cas contraire.

J'ai commencé à faire pas mal de petites recherches sur ces "sweep line" tuto ici et là Le concept est vraiment intéressant car il permet entre autre de trouver le polygone convexe englobant un nuage de point ("Convex hull avec des sweep line", Algorithme de Graham .

Et il rejoint la discussion que nous avons eu sur la génération de bruit et de texture. Il permettrait de créer des textures de type cellulaire.

A voir maintenant comment décrire cet objet particulier et l'intégrer à mon code pour pouvoir le réutiliser dans tout ces différents cas de figures.

Mine de rien, je ne pensais vraiment pas au commencement, qu'il y avait autant de choses sur les traitements numérique avec les polygones.

A bientôt

Jérôme

[wiwaxia]

Le retournement de boucle, lorsqu'il est unique (fig IIIb du message #22), se détecte aisément: il suffit de trouver une séquence de termes consécutifs (θ_m ,... θ_n) de signe opposé à celui de la somme totale (A_tot) - donc supposée non-nulle, et dont la somme partielle

A_mn = Σ_i=mⁿ(θ_i)

dépasse 1 tour en valeur absolue.

Il s'agit néanmoins d'un cas très particulier, et l'on voit ici la limite de tout calcul d'angle, qui ne tient pas compte des distances - voir les polygones (IIa) et (IIb).
On n'échappe donc pas au calcul du nombre d'auto-intersections, dont le codage présente une difficulté lorsque deux arêtes se superposent - c'est le cas du premier polygone que tu as proposé (#1):

(Ntour) vaut 1 pour le premier polygone (IVa) qui présente une concavité, 2 pour le suivant, et le calcul de (Nint) apparaît problématique.

4°) Une autre grandeur permet de caractériser un polygone: l'aire algébrique (S) de la portion de plan qu'il délimite, calculable d'une manière relativement simple à partir d'un point quelconque (G) par l'expression:

S = (1/2)*Σ_i=1^N(Det(GP_i, GP_j)) _{avec j = i + 1 si (i<N) sinon j = 1} ;

chaque déterminant (Det(GP_i, GP_j) = (GP_i×GP_j)) représentant l'aire algébrique du parallélogramme construit sur les vecteurs (GP_i, GP_j), aire égale au double de celle du triangle orienté (GP_iP_j).
Elle est, comme l'angle total de rotation (A_tot) et le nombre de tours effectués positive lorsque l'enroulement du polygone s'effectue dans le sens positif, négative dans le cas contraire.
Par exemple les figures (I, IIa, IIIa, IIIb) du message (#22) présentent une aire positive.

Il va de soi que l'on peut toujours trouver des polygones inclassables, malgré la diversité des critères précédemment définis: tout polygone croisé dont un point d'auto-intersection est un centre de symétrie (I) présente une aire algébrique nulle, de même que le nombre de tours.

[wiwaxia]

#18

... Peut-on se servir de ta méthode "NTours" pour savoir si un polygone est concave ? si oui comment procéder ?
A l'heure actuelle j'ai cette méthode pour connaitre si un polygone est convexe (trouvé sur stackoverflow)
On part du principe que le polygone n'est pas un polygone complexe ...

#19

... Bon pour ce qui est de savoir si un polygone est concave j'ai ma réponse il faut simplement que je compare tous les angle et si il y en à un qui fait moins de la somme de 2 ??? angles consécutifs fait moins 180° bingo le polygone est concave, c'est bien cela, non ?

On peut utiliser la fonction Ntour dans sa version esquissée au message #22 à condition de procéder de la façon suivante:

a) le polygone doit être dépourvu de toute auto-intersection, ce qui contraint à l'évaluation du nombre de croisements, et l'on doit en conséquence trouver:

Nint = 0 ;

des cas véritablement vicelards sont susceptibles de se présenter - voir les polygones (IVa) et (IVb) du message #24, mais ne paraissent pas insolubles;
b) le parcours du polygone doit correspondre à une rotation d'un seul tour: la ligne fermée doit par conséquent vérifier:

Nt = ± 1 ou A_tot = ± 2π ;

c) ces deux conditions vérifiées, il faut ensuite reprendre la liste des angles correspondant à chacun des (N) sommets: les séquences de valeurs consécutives de signe opposé à celui de (A_tot) révèlent alors les parties concaves du polygone; il faut simplement s'assurer que le premier terme de la liste correspond à un sommet convexe, donc que l'angle correspondant (θ_i0) présente un signe identique à celui de (A_tot).

#18

... D’où ma question si le polygone n'est ni convexe ni concave il sera forcément complexe (ce qui m'éviterai de mettre en place un test des intersections des segments par "brute-force" (tes des segment un à un) ou au pire j'essayerai d'implémenter l'algorithme décrit ici ...

#23

... Ce que je peux conclure c'est que c'est possible avec ta fonction NTours, sauf qu'il faut prendre en compte les différents cas de figures, ce qui alourdirait grandement l'algorithme et qu'il devient complexe d'avoir un solution viable à 100%. De plus le temps d'exécution en serait grandement pénalisé, à la vue du nombre de boucles nécessaires.

Ce que tu dénommes polygone complexe, bien que conforme à l'intuition, ne relève malheureusement pas d'une définition précise en raison du grand nombre de difficultés susceptibles de se présenter, et de nature à mettre en déroute les algorithmes évoqués jusque là.
Il est néanmoins possible de coder quelques filtres simples permettant d'éliminer les particularités gênantes; je tâcherai de programmer cela.

#23

J'ai commencé à faire pas mal de petites recherches sur ces "sweep line" tuto ici et là Le concept est vraiment intéressant car il permet entre autre de trouver le polygone convexe englobant un nuage de point ("Convex hull avec des sweep line", Algorithme de Graham .

Et il rejoint la discussion que nous avons eu sur la génération de bruit et de texture. Il permettrait de créer des textures de type cellulaire ...

Tu abordes d'autres questions intéressantes, mais qui sortent de la présente discussion.
L'enveloppe polygonale d'un nuage de points se code facilement.
Quant à la genèse de textures, j'ai été surpris de la simplicité de l'algorithme de partition du plan en cellules de VoronoÏ; le sujet (qui soulève bien des questions) pourrait être repris dans une autre discussion.

[wiwaxia]

La traque de quelques bogues particulièrement retors a pris quelque temps.

L'algorithme donné au message #16 contenait dans ses 3 dernières lignes une erreur assez discrète, qui ne s'était jamais manifestée jusque là ( il faut toujours se relire attentivement, et jusqu'au bout).

Voici donc deux versions équivalentes de l'algorithme du calcul de l'angle orienté déterminé par les directions de deux vecteurs:

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
 FUNCTION Angle2Va(V1, V2: Vect_2D): Reel;
   VAR Dt, N1N2, N21, N22, p, Ps, q, Theta: Reel; T1, T2: Bool;
   BEGIN
     N21:= Norme2(V1);     N22:= Norme2(V2); N1N2:= Sqrt(N21 * N22);
     p:= V1.x * V2.x;      q:= V1.y * V2.y;  Ps:= p + q;
     p:= V1.x * V2.y;      q:= V1.y * V2.x;  Dt:= p - q;
     T1:= (N1N2<1E-18);    T2:= (Abs(Ps)<Abs(Dt));
     IF T1 THEN Theta:= 0
           ELSE IF T2 THEN IF (Dt>0) THEN Theta:= ArcCos(Ps/N1N2)
                                     ELSE Theta:= -ArcCos(Ps/N1N2)
                      ELSE IF (Ps>0) THEN Theta:= ArcSin(Dt/N1N2)
                                     ELSE BEGIN
                                            p:= -ArcSin(Dt/N1N2);
                                            IF (Dt<0) THEN Theta:= p - Pi
                                                      ELSE Theta:= p + Pi
                                          END;
     Result:= Theta
   END;

 FUNCTION Angle2Vb(V1, V2: Vect_2D): Reel;
   VAR At, Dt, N1N2, N21, N22, p, Ps, q, Theta: Reel; T1, T2: Bool;
   BEGIN
     N21:= Norme2(V1);     N22:= Norme2(V2); N1N2:= Sqrt(N21 * N22);
     p:= V1.x * V2.x;      q:= V1.y * V2.y;  Ps:= p + q;
     p:= V1.x * V2.y;      q:= V1.y * V2.x;  Dt:= p - q;
     T1:= (N1N2<1E-18);    T2:= (Abs(Ps)<Abs(Dt));
     IF T1 THEN Theta:= 0
           ELSE IF T2 THEN BEGIN
                             At:= ArcTan(Ps/Dt);
                             IF (Dt>0) THEN Theta:= H_Pi - At
                                       ELSE Theta:= -H_Pi - At
                           END
                      ELSE BEGIN
                             At:= ArcTan(Dt/Ps);
                             IF (Ps>0) THEN Theta:= At
                                       ELSE IF (Dt<0) THEN Theta:= At - Pi
                                                      ELSE Theta:= At + Pi
                           END;
     Result:= Theta
   END;

Tout polygone à nombre pair de sommets, et présentant un centre de symétrie (I) en l'un de ses points de croisement, constitue à cet égard un excellent test, puisque les angles associés à chacun des sommets sont deux à deux opposés et que leur somme est nulle (Ntour = 0).

Voici ce que l'on obtient dans le cas d'un polygone pseudo-aléatoire s'inscrivant dans une image de dimensions (La, Ha), dont les 100 sommets se regroupent par paires d'indices (i, j = N + 1 - i), de coordonnées complémentaires vérifiant les relations:

x_i + x_j = La - 1 ; y_i + y_j = Ha - 1 :

Il s'agit ici d'une image de dimensions 700x300 ; remarquer la valeur et la constance des sommes (x_i + x_j ), (y_i + y_j) - nombres entiers - et (θ_i + θ_j) - réel affiché ici avec 9 décimales.
En bleu les angles positifs (rotations orientées dans le sens direct), en rouge les angles négatifs (rotations orientées dans le sens horaire.

Ce polygone est produit par la procédure suivante:

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
 CONST ... / ... NmaxV  = 100;
 ... / ...
 PROCEDURE Calc_Pol04(La1, Ha1: Z_32; VAR L_V: Tab_V2d);
   CONST C1 = 0.100; C2 = 1 - C1; C3 = C2 - C1; C4 = 1.44;
   VAR i, j, Lim: Byte; Xm, Xmax, Ym, Ymax: Z_32;
       Ki, p, q, r: Reel;
       Lst1: Tab_V2d;
   BEGIN
     RandSeed:= 1333555333; Lim:= NmaxV DIV 2;
     Xmax:= 0; Ymax:= 0;    Ki:= 1 / (Lim - 1);
     FOR i:= 1 TO NmaxV DO
       BEGIN
         j:= i - 1;
         IF (i>Lim) THEN BEGIN
                           Xm:= La1 - Lst1[NmaxV - j].x;
                           Ym:= Ha1 - Lst1[NmaxV - j].y
                         END
                    ELSE BEGIN
                           p:= Ki * j;           q:= C1;
                           IncR(q, C3 * p);      IncR(q, Random2(C1));
                           Ym:= Round(Ha1 * q);
                           q:= 0.460;            r:= -C4 * p;
                           IncR(q, r * (1 - p)); IncR(q, Random2(C1));
                           Xm:= Round(La1 * q)
                         END;
         Lst1[i].x:= Xm; IF (Xmax<Xm) THEN Xmax:= Xm;
         Lst1[i].y:= Ym; IF (Ymax<Ym) THEN Ymax:= Ym
       END;
     Lst1[0].x:= Xmax; Lst1[0].y:= Ymax; L_V:= Lst1
   END;

elle-même appelée par l'instruction:

Code :

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

Calc_Pol04(Larg_Image - 1, Haut_Image - 1, Polygone);

En fin de la seconde ligne apparaissent les valeurs maximales des coordonnées (X_max, Y_max), ce qui permet de s'assurer du non-débordement de la figure.

[wiwaxia]

Ci-dessous deux exemples simples de polygones non croisés (Pol01, Pol02), respectivement dotés de 17 et 41 sommets et présentant un enroulement unique (Ntour = +1) dans le sens direct; les sommets concaves s'y distinguent par un tracé en rouge (θ_i < 0):

Le signe de l'aire algébrique ne va pas forcément de pair avec celui du nombre de tours, parce que les surfaces délimitées par les arêtes font intervenir leur longueur, en plus de leur orientation; par exemple ce polygone (Pol03) à 5 boucles et 4 points de croisement, effectuant 3 tours dans le sens direct (Nt = +3 > 0) et dont l'aire est selon les cas positive, négative ou nulle:

Peu de changement, en ce qui concerne les déclarations de types et variables:

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
 CONST Dim_Max = 1500;
        NmaxV  = 100; ... / ...

 TYPE Pixel = ARRAY[1..3] OF Byte;
      Tab_Pix = ARRAY[0..Dim_Max, 0..Dim_Max] OF Pixel;
      Vect_2D = RECORD  x, y: Z_32; o: Reel  END;
      Tab_V2d = ARRAY[0..NmaxV] OF Vect_2D;

 VAR Larg_Image, Haut_Image, T_Fichier, T_Image: Z_32;
     V_Fich_1, V_Fich_2: File OF Byte;
     Matrice_1, Matrice_2: Tab_Pix;
     Nom_F2: String;
     Polygone: Tab_V2d;
     Aire: Reel;

hormis les enregistrements de type Vect_2D définissant les positions des sommets, et comportant une variable réelle supplémentaire dont la valeur est celle de l'angle (θ_i); la référence au mot "vecteur" apparaît à la réflexion abusive et devrait être changée.
Les procédures spécifiques sont appelées comme il suit:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
 PROCEDURE P2;
   BEGIN
     Zero_Pol(Polygone);
//     Calc_Pol01(Larg_Image, Haut_Image, Polygone);
//     Calc_Pol02(Larg_Image, Haut_Image, Polygone);
//     Calc_Pol03(Larg_Image, Haut_Image, Polygone);
     Calc_Pol04(Larg_Image - 1, Haut_Image - 1, Polygone);
     Calc_Aire(Aire);       Aff_Aire;
     Calc_Angles(Polygone); Aff_Angles(Polygone);
     Calc_Mat_Im2(Larg_Image, Haut_Image, Matrice_1, Matrice_2);
     Trace_Polygone(Polygone, Matrice_2);
   END;

L'algorithme est assez rudimentaire au niveau du choix de chaque type de polygone; s'il fonctionne pour tout nombre de sommets dans le cas des deux premiers (Pol01, Pol02), il provoque un plantage dans le cas du suivant (Pol03) pour NmaxV ≠ 12 et du dernier (Pol04) pour tout nombre impair de sommets; ma priorité était d'aborder toutes les variantes.

Les procédures de construction des polyèdres sont les suivantes:

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
 //  PROCEDURE Calc_Pol04(La1, Ha1: Z_32; VAR L_V: Tab_V2d);    déjà donnée (message précédent)
 
PROCEDURE Calc_Pol03(La, Ha: Z_32; VAR L_V: Tab_V2d);      // NmaxV = 12
   TYPE Tab_R = ARRAY[1..12] OF Reel;
   CONST u= 0.100; v = 0.200; U1 = 1 - u; V1 = 1 - v;
         Lx: Tab_R = (u, v, v, u, u, U1, U1, V1, V1, U1, U1, u);
         Ly: Tab_R = (u, u, U1, U1, V1, V1, U1, U1, u, u, v, v);
   VAR i: Byte; Xm, Xmax, Ym, Ymax: Z_32;
       Lst1: Tab_V2d;
   BEGIN
     Xmax:= 0; Ymax:= 0;
     FOR i:= 1 TO NmaxV DO
       BEGIN
         Xm:= Round(La * Lx[i]);
         Ym:= Round(Ha * Ly[i]);
         Lst1[i].x:= Xm; IF (Xmax<Xm) THEN Xmax:= Xm;
         Lst1[i].y:= Ym; IF (Ymax<Ym) THEN Ymax:= Ym
       END;
     Lst1[0].x:= Xmax; Lst1[0].y:= Ymax; L_V:= Lst1
   END;
 
 PROCEDURE Calc_Pol02(La, Ha: Z_32; VAR L_V: Tab_V2d);      // NmaxV = 41
   CONST D_PisN = D_Pi / NmaxV; Amax = 2.400 * Pi; Kt = 0.0860;
         R0 = 0.500; R1 = 0.295; R2 = (0.700 * R0) - R1;
   VAR i: Byte; Xm, Xmax, Ym, Ymax: Z_32; Ct, St, p, q, t, u, v, w: Reel;
       Lst1: Tab_V2d;
   BEGIN
     Xmax:= 0; Ymax:= 0;
     FOR i:= 1 TO NmaxV DO
       BEGIN
         u:= (i - 0.25) * D_PisN;
         v:= Sin(u);     t:= Amax * v;
         Ct:= Cos(t);    St:= Sin(t);
         v:= Cos(u);     w:= R1 + (R2 * v);
         p:= Kt * t;     q:= w * (1 + p);
         u:= q * Ct;     Xm:= Round(La * (R0 + u));
         v:= q * St;     Ym:= Round(Ha * (R0 + v));
         Lst1[i].x:= Xm; IF (Xmax<Xm) THEN Xmax:= Xm;
         Lst1[i].y:= Ym; IF (Ymax<Ym) THEN Ymax:= Ym
       END;
     Lst1[0].x:= Xmax; Lst1[0].y:= Ymax; L_V:= Lst1
   END;
 
 PROCEDURE Calc_Pol01(La, Ha: Z_32; VAR L_V: Tab_V2d);      // NmaxV = 17
   CONST D_PisN = D_Pi / NmaxV; R0 = 0.500; R1 = 0.330; R2 = R0 - R1;
   VAR i: Byte; Xm, Xmax, Ym, Ymax: Z_32; Ct, St, t, u, v, w: Reel;
       Lst1: Tab_V2d;
   BEGIN
     Xmax:= 0; Ymax:= 0;
     FOR i:= 1 TO NmaxV DO
       BEGIN
         t:= i * D_PisN;    Ct:= Cos(t);          St:= Sin(t);
         u:= Cos(3.60 * t); v:= R2 * u;           w:= R1 + v;
         u:= w * Ct;        Xm:= Round(La * (R0 + u));
         v:= w * St;        Ym:= Round(Ha * (R0 + v));
         Lst1[i].x:= Xm;    IF (Xmax<Xm) THEN Xmax:= Xm;
         Lst1[i].y:= Ym;    IF (Ymax<Ym) THEN Ymax:= Ym
       END;
     Lst1[0].x:= Xmax; Lst1[0].y:= Ymax; L_V:= Lst1
   END;

Et quant au reste du programme, pas de difficulté particulière:

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
(*HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH
 
 P2 / Calculs autour du polygone
 
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH*)
 
 FUNCTION Random2(u: Reel): Reel;
   VAR v, w: Reel;
   BEGIN
     v:= Random; w:= 2 * v; Result:= u * (w - 1)
   END;
 
 FUNCTION Det(VAR V1, V2: Vect_2D): Reel;
   VAR p, q: Reel;
   BEGIN
     p:= V1.x * V2.y;
     q:= V1.y * V2.x;
     Result:= p - q
   END;
 
 FUNCTION Diff_2V(V1, V2: Vect_2D): Vect_2D;
   VAR W12: Vect_2D;
   BEGIN
     W12.x:= V1.x - V2.x;
     W12.y:= V1.y - V2.y; Result:= W12
   END;
 
 PROCEDURE Aff_Aire;
   BEGIN
     E(0015); Wt(4, 38, 'Aire alg‚brique:        Ap =   ');
     E(0010); Write(Aire:12:4)
   END;
 
 PROCEDURE Calc_Aire(VAR Aire_: Reel);
   VAR i, j: Byte; S: Reel; Ve1, Ve2, Vg: Vect_2D;
   BEGIN
     Vg.x:= Round(1.1 * Polygone[0].x);
     Vg.y:= Round(1.1 * Polygone[0].y);
     S:= 0;
     FOR i:= 1 TO NmaxV DO
       BEGIN
         IF (i>1) THEN j:= i - 1 ELSE j:= NmaxV;
         IF (i<NmaxV) THEN j:= i + 1 ELSE j:= 1;
         Ve1:= Diff_2V(Polygone[i], Vg);
         Ve2:= Diff_2V(Polygone[j], Vg);
         IncR(S, Det(Ve1, Ve2));
       END;
     Aire_:= 0.5 * S
   END;
 
 PROCEDURE Aff_Angles(VAR L_V: Tab_V2d);
   CONST C1 = 25; L1 = 42; Epsilon = 1E-15;
   VAR i, j, k, Lim, x, y: Byte; p, q: Reel;
   BEGIN
     q:= L_V[0].o / D_Pi;
     E(0015); Wt(4, L1 - 2, 'Nombre de tours:        Nt =   ');
     E(0010); Write(q:12:9);
     Lim:= (NmaxV + 1) DIV 2;
     FOR k:= 1 TO NmaxV DO
       BEGIN
         j:= (k - 1) DIV Lim; x:= C1 * j; Inc(x);
         i:= (k - 1) MOD Lim; y:= i + L1;
         p:= L_V[k].o;
         IF (p<-Epsilon) THEN E(0012)
                         ELSE IF (p>Epsilon) THEN E(0011)
                                             ELSE E(0015);
         We(x, y, k, 4); Write('     ', p:12:9)
       END;
 
(*     E(0010);
     We(48, 40, Polygone[0].x, 6); Write(Polygone[0].y:6);
     FOR k:= 1 TO (NmaxV DIV 2) DO
       BEGIN
         We(48, 41 + k, (Polygone[k].x + Polygone[NmaxV + 1 - k].x), 6);
         Write((Polygone[k].y + Polygone[NmaxV + 1 - k].y):6, '  ');
         Write((Polygone[k].o + Polygone[NmaxV + 1 - k].o):12:9);          *)
       END
   END;
 
 FUNCTION Angle2Vb(V1, V2: Vect_2D): Reel;
   VAR At, Dt, N1N2, N21, N22, p, Ps, q, Theta: Reel; T1, T2: Bool;
   BEGIN
     N21:= Norme2(V1);     N22:= Norme2(V2); N1N2:= Sqrt(N21 * N22);
     p:= V1.x * V2.x;      q:= V1.y * V2.y;  Ps:= p + q;
     p:= V1.x * V2.y;      q:= V1.y * V2.x;  Dt:= p - q;
     T1:= (N1N2<1E-18);    T2:= (Abs(Ps)<Abs(Dt));
     IF T1 THEN Theta:= 0
           ELSE IF T2 THEN BEGIN
                             At:= ArcTan(Ps/Dt);
                             IF (Dt>0) THEN Theta:= H_Pi - At
                                       ELSE Theta:= -H_Pi - At
                           END
                      ELSE BEGIN
                             At:= ArcTan(Dt/Ps);
                             IF (Ps>0) THEN Theta:= At
                                       ELSE IF (Dt<0) THEN Theta:= At - Pi
                                                      ELSE Theta:= At + Pi
                           END;
     Result:= Theta
   END;
 
 FUNCTION Angle2Va(V1, V2: Vect_2D): Reel;
   VAR Dt, N1N2, N21, N22, p, Ps, q, Theta: Reel; T1, T2: Bool;
   BEGIN
     N21:= Norme2(V1);     N22:= Norme2(V2); N1N2:= Sqrt(N21 * N22);
     p:= V1.x * V2.x;      q:= V1.y * V2.y;  Ps:= p + q;
     p:= V1.x * V2.y;      q:= V1.y * V2.x;  Dt:= p - q;
     T1:= (N1N2<1E-18);    T2:= (Abs(Ps)<Abs(Dt));
     IF T1 THEN Theta:= 0
           ELSE IF T2 THEN IF (Dt>0) THEN Theta:= ArcCos(Ps/N1N2)
                                     ELSE Theta:= -ArcCos(Ps/N1N2)
                      ELSE IF (Ps>0) THEN Theta:= ArcSin(Dt/N1N2)
                                     ELSE BEGIN
                                            p:= -ArcSin(Dt/N1N2);
                                            IF (Dt<0) THEN Theta:= p - Pi
                                                      ELSE Theta:= p + Pi
                                          END;
     Result:= Theta
   END;
 
 PROCEDURE Calc_Angles(VAR L_V: Tab_V2d);
   VAR h, i, j: Byte; Atot, Theta: Reel; Ve1, Ve2: Vect_2D;
   BEGIN
     Atot:= 0;
     FOR i:= 1 TO NmaxV DO
       BEGIN
         IF (i>1) THEN h:= j - 1 ELSE h:= NmaxV;
         IF (i<NmaxV) THEN j:= i + 1 ELSE j:= 1;
         Ve1:= Diff_2V(Polygone[i], Polygone[h]);
         Ve2:= Diff_2V(Polygone[j], Polygone[i]);
         Theta:= Angle2Va(Ve1, Ve2);
         L_V[i].o:= Theta; IncR(Atot, Theta)
       END;
     L_V[0].o:= Atot
   END;
 
 ... / ...
 
 PROCEDURE Zero_Pol(VAR Lst_V: Tab_V2d);
   VAR i: Byte;
   BEGIN
     FOR i:= 1 TO NmaxV DO
       WITH Lst_V[i] DO BEGIN
                          x:= 0; y:= 0; o:= 0
                        END
   END;

[BeanzMaster]

Bonjour, wiwaxia, c'est à mon tour d'avoir décrocher

#18

#19

On peut utiliser la fonction Ntour dans sa version esquissée au message #22 à condition de procéder de la façon suivante:

a) le polygone doit être dépourvu de toute auto-intersection, ce qui contraint à l'évaluation du nombre de croisements, et l'on doit en conséquence trouver:

Nint = 0 ;

des cas véritablement vicelards sont susceptibles de se présenter - voir les polygones (IVa) et (IVb) du message #24, mais ne paraissent pas insolubles;
b) le parcours du polygone doit correspondre à une rotation d'un seul tour: la ligne fermée doit par conséquent vérifier:

Nt = ± 1 ou A_tot = ± 2π ;

c) ces deux conditions vérifiées, il faut ensuite reprendre la liste des angles correspondant à chacun des (N) sommets: les séquences de valeurs consécutives de signe opposé à celui de (A_tot) révèlent alors les parties concaves du polygone; il faut simplement s'assurer que le premier terme de la liste correspond à un sommet convexe, donc que l'angle correspondant (θ_i0) présente un signe identique à celui de (A_tot).

A cette première lecture je visualise un peu près les tests à effectuer. Il faudrait que se soit plusieurs algorithmes en un qui se lanceraient de manière progressive suivant les cas de figures. Un découpage en plusieurs petites fonctions me parait plus qu'évident

#23

Ce que tu dénommes polygone complexe, bien que conforme à l'intuition, ne relève malheureusement pas d'une définition précise en raison du grand nombre de difficultés susceptibles de se présenter, et de nature à mettre en déroute les algorithmes évoqués jusque là.
Il est néanmoins possible de coder quelques filtres simples permettant d'éliminer les particularités gênantes; je tâcherai de programmer cela.

Oui je l'entend bien cette notion de "complexe" n'est pas évidentes. Je me rend bien comptes que les polygones sont bien plus difficiles à cerner dans leur globalité mathématique de ce que je pensais au début de cette discussion.

#23

Tu abordes d'autres questions intéressantes, mais qui sortent de la présente discussion.
L'enveloppe polygonale d'un nuage de points se code facilement.
Quant à la genèse de textures, j'ai été surpris de la simplicité de l'algorithme de partition du plan en cellules de VoronoÏ; le sujet (qui soulève bien des questions) pourrait être repris dans une autre discussion.

Oui c'était juste pour dire, je pense que nous aurons l'occasion d'en reparler dans une autre discussion dédiée.

La traque de quelques bogues particulièrement retors a pris quelque temps.

L'algorithme donné au message #16 contenait dans ses 3 dernières lignes une erreur assez discrète, qui ne s'était jamais manifestée jusque là ( il faut toujours se relire attentivement, et jusqu'au bout).

Voici donc deux versions équivalentes de l'algorithme du calcul de l'angle orienté déterminé par les directions de deux vecteurs:

Y- a-t-il une différence de précision à utiliser arcSin/arcCos plutôt que arcTan ? (j'ai d'autres question du coup, cf plus bas)

Ci-dessous deux exemples simples de polygones non croisés (Pol01, Pol02), respectivement dotés de 17 et 41 sommets et présentant un enroulement unique (Ntour = +1) dans le sens direct; les sommets concaves s'y distinguent par un tracé en rouge (θ_i < 0):

Le signe de l'aire algébrique ne va pas forcément de pair avec celui du nombre de tours, parce que les surfaces délimitées par les arêtes font intervenir leur longueur, en plus de leur orientation; par exemple ce polygone (Pol03) à 5 boucles et 4 points de croisement, effectuant 3 tours dans le sens direct (Nt = +3 > 0) et dont l'aire est selon les cas positive, négative ou nulle:

Oui c'est ce que j'avais déja pu comprendre lors de mes diverse lectures.

Je vais sortir un peu du cadre pour comprendre ton code et tes fonctions

#1

Dans ta fonction du calcul de l'aire

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
 PROCEDURE Calc_Aire(VAR Aire_: Reel);
   VAR i, j: Byte; S: Reel; Ve1, Ve2, Vg: Vect_2D;
   BEGIN
     Vg.x:= Round(1.1 * Polygone[0].x);
     Vg.y:= Round(1.1 * Polygone[0].y);
     S:= 0;
     FOR i:= 1 TO NmaxV DO
       BEGIN
         IF (i>1) THEN j:= i - 1 ELSE j:= NmaxV;
         IF (i<NmaxV) THEN j:= i + 1 ELSE j:= 1;
         Ve1:= Diff_2V(Polygone[i], Vg);
         Ve2:= Diff_2V(Polygone[j], Vg);
         IncR(S, Det(Ve1, Ve2));
       END;
     Aire_:= 0.5 * S
   END;

Pourquoi prendre le point d'origine et le multiplié par 1.1 ?

Code :

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

1
2
Vg.x:= Round(1.1 * Polygone[0].x);
Vg.y:= Round(1.1 * Polygone[0].y);

pour ensuite faire la différence avec

Code :

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

1
2
Ve1:= Diff_2V(Polygone[i], Vg);
Ve2:= Diff_2V(Polygone[j], Vg);

Et enfin

Code :

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

IncR(S, Det(Ve1, Ve2));

#1.a

avec ta fonction :

Code :

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

1
2
3
4
5
6
7
FUNCTION Det(VAR V1, V2: Vect_2D): Reel;
   VAR p, q: Reel;
   BEGIN
     p:= V1.x * V2.y;
     q:= V1.y * V2.x;
     Result:= p - q
   END;

Elle correspond bien à la magnitude d'un produit en croix 3D ? (malgré que le produit en croix d'un vecteur 2D n'existe pas)

On substitue donc cette opération en deux fonctions afin de pouvoir simuler le produit en croix d'un vecteur 3D

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
 
{ Retourne le produit en croix du vecteur
    Equivalent au produit en croix d'un vecteur 3D. (Pour simuler le calcul et obtenir un résultat, on "suppose" que la valeur "Z" est égale à 1)
    Pour obtenir la valeur de "Z" (magnitude) du produit en croix d'un vecteur 3D il faut utiliser la fonction Perp  }
function TBZVector2f.CrossProduct(A:TBZVector2f):TBZVector2f;
begin
  Result.x := Self.y - A.y; 
  Result.y := A.x - Self.x; 
   // (Self.y*A.z) - (A.y*Self.z) // Z = 1;
  // (A.x*Self.z) - (Self.x*A.z) // Z = 1
  // Result.Z := (Self.x*A.y) - (Self.y*A.x)
end; 
 
{ Retourne la composante Z (Magnitude) d'un produit en croix d'un vecteur 3D. Nous supposons ici que la valeur "Z" est égale à 0 }  
function TBZVector2f.Perp(A : TBZVector2f) : Single;
begin
  Result := (Self.x * A.y) - (Self.y * A.x);
end;

C'est bien ça ?

Voici dans mon cas la fonction que j'utilise dans le calcul de l'aire :

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
function TBZ2DPolygonTool.GetArea : Single;
Var
  Area : Single;
  i, j : Integer;
begin
   j := FPoints.Count - 1 ;
   Area := 0;
   for i := 0 to FPoints.Count - 1 do
   begin
     Area := Area + (FPoints.Items[j].X + FPoints.Items[i].X) * ( FPoints.Items[j].Y - FPoints.Items[i].Y);
     j:=i;
   end;
   Area := Area * 0.5;
   Result := Abs(Area)
end;

Celle-ci serait-elle erronée ? manquerait-elle de précision ? Hormis le fait que je retourne uniquement des valeurs absolue.

Peu de changement, en ce qui concerne les déclarations de types et variables:

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
 
 
 FUNCTION Angle2Vb(V1, V2: Vect_2D): Reel;
   VAR At, Dt, N1N2, N21, N22, p, Ps, q, Theta: Reel; T1, T2: Bool;
   BEGIN
     N21:= Norme2(V1);     N22:= Norme2(V2); N1N2:= Sqrt(N21 * N22);
     p:= V1.x * V2.x;      q:= V1.y * V2.y;  Ps:= p + q;
     p:= V1.x * V2.y;      q:= V1.y * V2.x;  Dt:= p - q;
     T1:= (N1N2<1E-18);    T2:= (Abs(Ps)<Abs(Dt));
     IF T1 THEN Theta:= 0
           ELSE IF T2 THEN BEGIN
                             At:= ArcTan(Ps/Dt);
                             IF (Dt>0) THEN Theta:= H_Pi - At
                                       ELSE Theta:= -H_Pi - At
                           END
                      ELSE BEGIN
                             At:= ArcTan(Dt/Ps);
                             IF (Ps>0) THEN Theta:= At
                                       ELSE IF (Dt<0) THEN Theta:= At - Pi
                                                      ELSE Theta:= At + Pi
                           END;
     Result:= Theta
   END;
 
 PROCEDURE Calc_Angles(VAR L_V: Tab_V2d);
   VAR h, i, j: Byte; Atot, Theta: Reel; Ve1, Ve2: Vect_2D;
   BEGIN
     Atot:= 0;
     FOR i:= 1 TO NmaxV DO
       BEGIN
         IF (i>1) THEN h:= j - 1 ELSE h:= NmaxV;
         IF (i<NmaxV) THEN j:= i + 1 ELSE j:= 1;
         Ve1:= Diff_2V(Polygone[i], Polygone[h]);
         Ve2:= Diff_2V(Polygone[j], Polygone[i]);
         Theta:= Angle2Va(Ve1, Ve2);
         L_V[i].o:= Theta; IncR(Atot, Theta)
       END;
     L_V[0].o:= Atot
   END;

#2

Ok donc si je comprend correctement

N1 et N2 représente les longueurs des vecteurs au carré et donc N1N2 ??? là je suis perdu pourquoi multiplier les 2 valeurs entre elles ? Est ce que cela est une autre façon de calculer la distance entre 2 vecteurs ?

Code :

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

1
2
3
4
5
6
7
8
9
function TBZVector2f.Length:Single;
begin
  Result := System.Sqrt((Self.X * Self.X) + (Self.Y * Self.Y));
end;
 
function TBZVector2f.Distance(constref A:TBZVector2f):Single;
begin
  Result := (Self - A).Length;
end;

#3

Je ne comprend pas

Code :

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

p:= V1.x * V2.x;      q:= V1.y * V2.y;  Ps:= p + q;

par rapport à

Code :

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

p:= V1.x * V2.y;      q:= V1.y * V2.x;  Dt:= p - q;

que l'on peux remplacer par

Code :

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

Det(v1,v2);

ps, cela correspond à quoi ? je ne comprend pas pourquoi, multiplier les valeurs de v1 par v2 et les ajouter ensemble.

Une fonction comme celle-ci dessous ne suffirait-elle pas, pour calculer l'angle entre deux vecteurs ?

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
function TBZVector2f.AngleBetweenPoints(C: TBZVector2f):Single;
var
  Angle : Single;
begin
   //Angle :=  Math.arctan2(P.y - C.y, P.x - C.x)
   //         -Math.arctan2(Self.y - C.y, Self.x - C.x);
 
   Angle := Math.Arctan2((C.y - Self.y), (C.x - Self.x));
  Result := Angle;
  if result < 0 then result := result + cPI;
 
   //result := (Angle * cRadian);
   //if Result < 0 then result := result + 360;
 
end;

[EDIT] #4

petit oublis voici mes fonctions pour calculer l'angle entre 2 vecteurs avec un point central

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
function TBZVector2f.Length:Single;
begin
  Result := System.Sqrt((Self.X * Self.X) + (Self.Y * Self.Y));
end;  
 
function TBZVector2f.Normalize : TBZVector2f;
begin
 Result := Self * (1/Self.Length);
end;  
 
function TBZVector2f.DotProduct(A:TBZVector2f):Single;
begin
  Result := (Self.X * A.X) + (Self.Y * A.Y);
end;  
 
function TBZVector2f.AngleCosine(constref A: TBZVector2f): Single;
begin
   Result:=Self.DotProduct(A)/(Self.Length*A.Length);
end;
 
function TBZVector2f.AngleBetween(Constref A, ACenterPoint : TBZVector2f): Single;
Var
  vt1,vt2  :  TBZVector2f;
begin
  vt1 := Self - ACenterPoint;
  vt2 := A - ACenterPoint;
  vt1 := vt1.Normalize;
  vt2 := vt2.Normalize;
  Result := ArcCos(vt1.AngleCosine(vt2));
end;

AngleBetween serait-il suffisant ?


Wiwaxia merci pour le temps que tu prends à répondre. Et pour tes précises et précieuses informations et explications.

Merci encore, à bientôt

Jérôme

[wiwaxia]

Bonjour,

Je vois que tu a lu attentivement les algorithmes.

... A cette première lecture je visualise un peu près les tests à effectuer. Il faudrait que se soit plusieurs algorithmes en un qui se lanceraient de manière progressive suivant les cas de figures. Un découpage en plusieurs petites fonctions me parait plus qu'évident ...

Le nombre de tours effectués par le polygone, son aire algébrique , déterminés par les procédures

Calc_Angles(VAR L_V: Tab_V2d) ; Calc_Aire(VAR Aire_: Reel);

que l'on pourrait tout aussi bien convertir en fonctions, s'appliquent à tout type de polygone et constituent les outils de base pour la caractérisation des objets étudiés.
On pourrait y adjoindre le nombre d'enroulement autour d'un point quelconque du plan, évoqué au message #16 mais lié à une fonction booléenne, ainsi que la détermination des valeurs maximales (X_max, Y_max) des coordonnées des sommets.

... Oui je l'entend bien cette notion de "complexe" n'est pas évidentes. Je me rend bien compte que les polygones sont bien plus difficiles à cerner dans leur globalité mathématique de ce que je pensais au début de cette discussion ...

Permettre l'intervention de polygones complexes, c'est à dire présentant des éléments de dégénérescence tels que des sommets et/ou des arêtes confondus, c'est ouvrir la boîte de Pandore et se condamner tôt ou tard à des algorithmes à marcher au plafond.
La plupart des codes de création des polygones évitent facilement ces cas particuliers, ou les rendent du moins très peu probables.
Des tests relativement simples permettent de les détecter:
a) deux sommets quelconques non confondus (impliquant des arêtes non-nulles), ce qui se traduit par:

D²_{i, j} > 0 _{pour tout couple (i, j) vérifiant 0 < i < j <= Nombre de sommets}

b) chaque sommet (S_i) hors de toute arête (S_jS_k), impliquant des angles au sommets non-nuls; on aurait dans le cas contraire:

Det(S_jS_i, S_jS_k) = 0 _{(vecteurs colinéaires}) ,
Pscal(S_jS_i, S_jS_k) > 0 _{(vecteurs de même sens}) ,
S_jS_i < S_jS_k) _{(Si appartient au segment SjSk ;}

c) les arêtes ne se recouvrent pas, sinon l'on observerait le cas suivant:

Det(S_iS_j, S_kS_l) = 0 _{(vecteurs colinéaires}) ,
Det(S_iS_j, S_iS_k) = 0 _{(droites confondues}) ,
M_iM_k < (S_iS_j + S_kS_l)/2 _{recouvrement partiel des arêtes de milieux (Mi, Mk)}

À cet égard, le petit bijou que tu avais proposé (#01) cumule les 3 particularités , ce qui engageait d'emblée la discussion à un niveau assez difficile.

Les cas précédents exclus, le croisement éventuel des arêtes conduit à des calculs un peu lourds, mais pas à des obstacles insurmontables.

Y- a-t-il une différence de précision à utiliser arcSin/arcCos plutôt que arcTan ? (j'ai d'autres question du coup, cf plus bas)

Non, dans la mesure où l'on utilise ces fonctions sur un domaine centré en la valeur (u₀) pour laquelle F(u) s'annule:

F(u₀) = 0 ,

les dérivées de ces fonctions restant proches (en valeur absolue) de l'unité.
# En ce qui concerne les deux premières (ArcSin(u) et ArcCos(u)), l'obligation de s'éloigner au mieux des points singuliers (vers lesquels la dérivée tend vers ±∞) conduit à choisir celle vérifiant │F(u)│ ≤ 1/√2 , donc u₀ = 0 ou (±π/2) - abstraction faite des éventuelles translations.
# Pour ce qui est de ArcTan(u), on recours selon les cas aux fonctions ArcTan(y/x) ou ArcTan(x/y) , de telle sorte que sorte que l'on ait │ArcTan(u)│ ≤ 1 ,
conformément à la relation fonctionnelle:

qui intervient aussi dans les algorithmes de calcul des fonctions Tan(x) et ArcTan(u).
Ma préférence va au second choix en raison de sa simplicité, le calcul de l'angle argument ne dépendant alors que du rapport d'un produit scalaire et d'un déterminant; le produit des normes ne sert seulement qu'à éviter l'impasse calculatoire (N₁N₂ = 0) liée à l'intervention d'un vecteur nul.

La suite à plus tard.

[wiwaxia]

Dans ta fonction du calcul de l'aire

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
 PROCEDURE Calc_Aire(VAR Aire_: Reel);
   VAR i, j: Byte; S: Reel; Ve1, Ve2, Vg: Vect_2D;
   BEGIN
     Vg.x:= Round(1.1 * Polygone[0].x);
     Vg.y:= Round(1.1 * Polygone[0].y);
     S:= 0;
     FOR i:= 1 TO NmaxV DO
       BEGIN
         IF (i>1) THEN j:= i - 1 ELSE j:= NmaxV;
         IF (i<NmaxV) THEN j:= i + 1 ELSE j:= 1;
         Ve1:= Diff_2V(Polygone[i], Vg);
         Ve2:= Diff_2V(Polygone[j], Vg);
         IncR(S, Det(Ve1, Ve2));
       END;
     Aire_:= 0.5 * S
   END;

Pourquoi prendre le point d'origine et le multiplié par 1.1 ?

Code :

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

1
2
Vg.x:= Round(1.1 * Polygone[0].x);
Vg.y:= Round(1.1 * Polygone[0].y);

pour ensuite faire la différence avec

Code :

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

1
2
Ve1:= Diff_2V(Polygone[i], Vg);
Ve2:= Diff_2V(Polygone[j], Vg);

a) Tout polygone est circonscrit dans son plan par le rectangle de diagonale ((X_min, Y_min) , ((X_max, Y_max)), et prendre une paire de coordonnées plus élevées:

X_G = Round(k * X_max) , Y_G = Round(k * Y_max) avec (k > 1)

permet de s'assurer que le point (G), alors extérieur au rectangle, ne se superpose pas à l'un des sommets ou l'une des arêtes.
b) Les positions des (NmaxV) sommets sont consignées dans un tableau de dimension supérieure:

Code :

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

TYPE Tab_V2d = ARRAY[0..NmaxV] OF Vect_2D;

et le premier élément de rang nul contient les valeurs maximales des coordonnées:

Code :

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

Lst1[0].x:= Xmax; Lst1[0].y:= Ymax; L_V:= Lst1

- ces instructions figurent dans la procédure de calcul de chaque polygone, par ex. Calc_Pol01(Larg_Image, Haut_Image, Polygone) .
c) Il faut calculer l'angle orienté (V₁, V₂) = (GS_i, GS_j) ,
et chacun des vecteurs est donné par la relation de Chasles:

GS_i = OS_i - OG , GS_j = OS_j - OG ,

d'où le recours à la fonction Diff_2V(V1, V2: Vect_2D): Vect_2D .

Il est vrai que mes programmes n'ont jamais brillé par la surabondance des commentaires .

[BeanzMaster]

a) Tout polygone est circonscrit dans son plan par le rectangle de diagonale ((X_min, Y_min) , ((X_max, Y_max)), et prendre une paire de coordonnées plus élevées:

X_G = Round(k * X_max) , Y_G = Round(k * Y_max) avec (k > 1)

permet de s'assurer que le point (G), alors extérieur au rectangle, ne se superpose pas à l'un des sommets ou l'une des arêtes.
b) Les positions des (NmaxV) sommets sont consignées dans un tableau de dimension supérieure:

Code :

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

TYPE Tab_V2d = ARRAY[0..NmaxV] OF Vect_2D;

et le premier élément de rang nul contient les valeurs maximales des coordonnées:

Code :

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

Lst1[0].x:= Xmax; Lst1[0].y:= Ymax; L_V:= Lst1

- ces instructions figurent dans la procédure de calcul de chaque polygone, par ex. Calc_Pol01(Larg_Image, Haut_Image, Polygone) .

Ok merci, j'ai compris

c) Il faut calculer l'angle orienté (V₁, V₂) = (GS_i, GS_j) ,
et chacun des vecteurs est donné par la relation de Chasles:

GS_i = OS_i - OG , GS_j = OS_j - OG ,

d'où le recours à la fonction Diff_2V(V1, V2: Vect_2D): Vect_2D .

Bon là je commence à entrevoir le bout du tunnel, avec cette relation de Chalses j'ai trouvé 2 sites https://www.maths-cours.fr/methode/r...ls-vectoriels/ et la qui m'ont permis de presque tout comprendre (faut que je mette en pratique dans un autre cas concret pour je pige à 100%)

Il est vrai que mes programmes n'ont jamais brillé par la surabondance des commentaires .

Pas de problème, on n'a chacun nos habitudes en matière de codage et c'est comme tout lorsque l'on sait, c'est évident, mais pas forcément pour autrui. C'est comme si je te donnai une de mes recettes de cuisine, tu va me dire oulala ca veux dire quoi ça ?, pourquoi je dois faire ça ? Et pis un peu de flou, ce ne fait pas de mal, juste un peu plus à réfléchir

[wiwaxia]

On aborde ici un problème de compréhension, lié à une méconnaissance de l'anglais et des mathématiques.

Cette difficulté est aggravée par la pratique du franglais, liée à la surabondance massive de la documentation anglo-saxonne.
Le recours systématique à ce jargon dégrade la pensée comme le langage, en escamotant l'effort de traduction indispensable à la bonne compréhension des idées; il conduit facilement à des méprises dès que l'on n'a pas une connaissance approfondie de la langue (ce qui est mon cas).
Il n'est pas question de faire la leçon à quiconque; mais il faut cependant pointer une source de difficultés réelles, et très répandues.

avec ta fonction :

Code :

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

1
2
3
4
5
6
7
FUNCTION Det(VAR V1, V2: Vect_2D): Reel;
   VAR p, q: Reel;
   BEGIN
     p:= V1.x * V2.y;
     q:= V1.y * V2.x;
     Result:= p - q
   END;

Elle correspond bien à la magnitude d'un produit en croix 3D ? (malgré que le produit en croix d'un vecteur 2D n'existe pas)

Je n'ai jamais rencontré la notion de "magnitude d'un produit en croix ".
On désigne par l'expression "produit en croix" une technique visuelle de calcul enseignée dès le collège, permettant un calcul rapide sur 4 termes disposés en carré.

Le produit vectoriel (cross product) est l'opération qui à tout couple de vecteurs de (R³):

V₁ = X₁.u_x + Y₁.u_y + Z₁.u_z ,
V₂ = X₂.u_x + Y₂.u_y + Z₂.u_z ,

fait correspondre un troisième vecteur:

V = V₁×V₂ = X.u_x + Y.u_y + Z.u_z

dont les composantes admettent pour expressions les "produits en croix":

X = Y₁*Z₂ - Z₁*Y₂ ,
Y = Z₁*X₂ - X₁*Z₂ ,
Z = X₁*Y₂ - Y₁*X₂ .

Ce vecteur est normal aux deux précédents; le trièdre (V₁, V₂, V) est direct et sa norme a pour expression géométrique:

║V║ = ║V₁║*║V₂║*│Sin(θ)│ ,

(θ) désignant l'écart angulaire séparant leurs directions.

... si je comprend correctement
N1 et N2 représentent les longueurs des vecteurs au carré et donc N1N2 ??? là je suis perdu pourquoi multiplier les 2 valeurs entre elles ? Est ce que cela est une autre façon de calculer la distance entre 2 vecteurs ?

Code :

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

1
2
3
4
5
6
7
8
9
function TBZVector2f.Length:Single;
begin
  Result := System.Sqrt((Self.X * Self.X) + (Self.Y * Self.Y));
end;
 
function TBZVector2f.Distance(constref A:TBZVector2f):Single;
begin
  Result := (Self - A).Length;
end;

Je ne comprend pas

Code :

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

p:= V1.x * V2.x;      q:= V1.y * V2.y;  Ps:= p + q;

par rapport à

Code :

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

p:= V1.x * V2.y;      q:= V1.y * V2.x;  Dt:= p - q;

que l'on peux remplacer par

Code :

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

Det(v1,v2);

ps, cela correspond à quoi ? je ne comprend pas pourquoi, multiplier les valeurs de v1 par v2 et les ajouter ensemble.

Le produit scalaire (dot product) est l'opération qui à tout couple de vecteurs (V₁[/B], V₂[/B]) fait correspondre le réel:

V₁.V₂ = X₁*X₂ + Y₁*Y₂ + Z₁*Z₂ ;

il admet pour expression géométrique: V₁.V₂ = ║V₁║*║V₂║*Cos(θ) ,
(θ) désignant toujours l'angle déterminé par leurs directions.

La définition s'adapte sans difficulté aux dimensions inférieures (2 ou 1).
Le produit scalaire d'un vecteur par lui-même conduit au carré de sa norme euclidienne:

V.V = X² + Y² + Z² = ║V║² ;

si le vecteur est défini par un couple de points, on trouve alors le carré de la distance:

AB.AB = ║AB║² = (AB)² = d_AB² .

Le produit mixte de 3 vecteurs (triple product) est l'opération composée qui à 3 vecteurs de (R³) fait correspondre le réel:

(V₁, V₂, V₃) = (V₁×V₂).V₃ ;

le résultat s'identifie au déterminant de la matrice des trois vecteurs (matrice carrée d'ordre 3), d'où les notations équivalentes:

(V₁, V₂, V₃) = Det(V₁, V₂, V₃) .

Il représente de plus le volume algébrique du parallélépipède construit sur V₁, V₂ et V₃ ;
Il s'annule en même temps que l'un des trois termes s'identifie au vecteur nul (V_i = 0), mais aussi
- dès que deux des vecteurs sont colinéaires, ou plus généralement
- dès qu'il intervient de dépendance linéaire entre les 3 vecteurs.

Cas particulier: si (V₁) et (V₂) appartiennent au plan (xOy) - ce qui entraîne Z₁ = Z₂ = 0 ,
et si (V₃) est égal au vecteur unitaire (u_z) - ce qui entraîne X₃ = Y₃ = 0 , et Z₃ = 1 ,
alors le résultat du produit mixte s'identifie au déterminant de la matrice des 2 premiers vecteurs (matrice carrée cette fois d'ordre 2):

(V₁, V₂, u_z) = Det(V₁, V₂) = X₁*Y₂ - Y₁*X₂ ;

il représente l'aire algébrique du parallélogramme construit sur les vecteurs (V₁) et (V₂) dans le plan orienté par le repère (xOy), et vérifie la relation géométrique:

(V₁, V₂, u_z) = ║V₁║*║V₂║*Sin(θ) ,

dans laquelle (θ) représente l'angle orienté déterminé par les deux vecteurs.

Les instructions citées, qui fournissent les valeurs du produit scalaire (Ps) et du déterminant (Det):

Code :

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

1
2
     p:= V1.x * V2.x;      q:= V1.y * V2.y;  Ps:= p + q;
     p:= V1.x * V2.y;      q:= V1.y * V2.x;  Dt:= p - q;

sont conformes à ce qui précède.
Les carrés des normes des vecteurs (N21, N22), directement issus d'une somme, conduisent simplement à leur produit:

N₁ * N₂ = (N₁² * N₂²)^1/2 ,

ce que font les instructions suivantes:

Code :

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

     N21:= Norme2(V1);     N22:= Norme2(V2); N1N2:= Sqrt(N21 * N22) .

J'espère que cet exposé ne sera pas suivi de trop d'effets secondaires indésirables. En cas d'urgence, n'hésitez pas à signaler la lecture de ce forum à votre pharmacien.

[BeanzMaster]

On aborde ici un problème de compréhension, lié à une méconnaissance de l'anglais et des mathématiques.

Cette difficulté est aggravée par la pratique du franglais, liée à la surabondance massive de la documentation anglo-saxonne.
Le recours systématique à ce jargon dégrade la pensée comme le langage, en escamotant l'effort de traduction indispensable à la bonne compréhension des idées; il conduit facilement à des méprises dès que l'on n'a pas une connaissance approfondie de la langue (ce qui est mon cas).
Il n'est pas question de faire la leçon à quiconque; mais il faut cependant pointer une source de difficultés réelles, et très répandues.

Oui tu as raison, pour ma part je me débrouille plutôt bien en anglais, mais en maths c'est une autre histoire. Et comme tu le dis, il y a surabondance de documentation anglo-saxonne, mais difficile (souvent) de trouver leurs équivalent en français.
Avec les maths j'ai du mal a traduire correctement les termes (et en plus j'utilise des termes anglophone dans mon code et du coup j'associe un thème (une formule, une règle etc...) à un mot anglais et du coup c'est en français que j'ai du mal à m'exprimer .
N'ayant pas fais de maths poussées au lycée (et au collège toutes ces notions avancées sur les vecteurs, n'étaient pas encore au programme), à 43 ans je suis un peu larguer par moment, souvent avec les notations des formules mathématiques. Le codage m'aide (très) souvent à comprendre les concepts et formules. je comprend, je les appliques, mais je suis incapables de les expliquer. Bref un sacré mélange dans mon cerveau.

Je n'ai jamais rencontré la notion de "magnitude d'un produit en croix "

.

Je ne sais plus et je ne retrouve plus le site ou j'ai piocher ce terme pour cette fonction qu'il est plus correcte d'appeler (après une recherche rapide) un produit dyadique en bon français, outer product ou ce "Perp" appelé aussi "perpendicular cross product" chez les anglais (et là je ne suis même pas sure que ce soit la même définition mathématique, pour le coup)

Voila par exemple ce que l'on peux lire sur wikipedia en anglais à ce propos Cross product

Code :

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

 the magnitude of the product of two perpendicular vectors is the product of their lengths

Magnitude peux donc se traduire par plusieurs termes : Grandeur, Ampleur, Distance ??? donc comme tu le dis ce n'est pas évident du coup. (surtout pour moi, et en plus j'apprend des choses erronées )

Les instructions citées, qui fournissent les valeurs du produit scalaire (Ps) et du déterminant (Det):

Code :

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

1
2
     p:= V1.x * V2.x;      q:= V1.y * V2.y;  Ps:= p + q;
     p:= V1.x * V2.y;      q:= V1.y * V2.x;  Dt:= p - q;

sont conformes à ce qui précède.
Les carrés des normes des vecteurs (N21, N22), directement issus d'une somme, conduisent simplement à leur produit:

N₁ * N₂ = (N₁² * N₂²)^1/2 ,

ce que font les instructions suivantes:

Code :

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

     N21:= Norme2(V1);     N22:= Norme2(V2); N1N2:= Sqrt(N21 * N22) .

Ok merci pour ces explications plus que concises sur les règles mathématique sur les vecteurs

J'espère que cet exposé ne sera pas suivi de trop d'effets secondaires indésirables. Signaler éventuellement la lecture de ce forum à votre pharmacien.

Déja trop tard pour les effets secondaire indésirables, c'est comme avec les mentos !!

Merci encore beaucoup wiwaxia pour ton temps et ton aide. Je bois littéralement tes textes (en plusieurs lecture car je ne comprend jamais tout la première fois) (et me couche après avec un tube d'aspirine )

Bonne soirée

Jérôme

[wiwaxia]

Oui tu as raison, pour ma part je me débrouille plutôt bien en anglais, mais en maths c'est une autre histoire.
... / ... Avec les maths j'ai du mal a traduire correctement les termes (et en plus j'utilise des termes anglophone dans mon code et du coup j'associe un thème (une formule, une règle etc...) à un mot anglais et du coup c'est en français que j'ai du mal à m'exprimer ...

Alors deux liens s'imposent, que tu dois garder à portée de clic: Reverso et Linguee.
Tu peux aussi rechercher les paires d'articles de Wikipédia rédigés en anglais et en français, pour confirmer la traduction d'une définition et des principales propriétés qui s'y rattachent - ce que j'ai fait dans le précédent message, sans considération (faute de temps) du niveau de difficulté.
L'outsider encore du franglais !
Le champion dans le domaine de la traduction scientifique et technique est le Grand Dictionnaire Terminologique (GDL pour les initiés) édité par l'Office Québecois de la Langue Française - à utiliser quand on se trouve à bout de ressource.

... N'ayant pas fait de maths poussées au lycée (et au collège toutes ces notions avancées sur les vecteurs, n'étaient pas encore au programme), à 43 ans je suis un peu largué par moment, souvent avec les notations des formules mathématiques. Le codage m'aide (très) souvent à comprendre les concepts et formules. je comprend, je les applique, mais je suis incapable de les expliquer ...

Ton désarroi est tout à fait compréhensible, vu que l'artillerie lourde (produit vectoriel, déterminant) n'est abordée qu'au-delà du bac.
Il te faut disposer au minimum d'un formulaire, qui te fournisse des explications claires et en français.
Tu devrais t'imposer comme règle de ne jamais utiliser une notion sans avoir eu connaissance de sa traduction correcte: c'est contraignant au début, mais cela te permettrait d'apprendre beaucoup de choses et te donnerait plus d'aisance.
On peut effectivement reconnaître la nature d'une opération à partir de son codage, à condition d'être entraîné à la lecture des algorithmes et à leur traduction mathématique; il est beaucoup plus difficile de comprendre une nouvelle notion, d'autant qu'un langage très élaboré puisse devenir totalement hermétique, et ses outils autant de boîtes noires.
Je reviendrai plus tard sur les sites de maths consultables.

... Je ne sais plus et je ne retrouve plus le site ou j'ai piocher ce terme pour cette fonction qu'il est plus correcte d'appeler (après une recherche rapide) un produit dyadique en bon français, outer product ou ce "Perp" appelé aussi "perpendicular cross product" chez les anglais (et là je ne suis même pas sure que ce soit la même définition mathématique, pour le coup) ...

Le terme "produit" présente une ambiguïté, parce qu'il désigne à la fois une opération et son résultat.
Dis-toi bien qu'il existe un grand nombre de produits, qui peuvent faire intervenir des nombres, des vecteurs, des matrices, et être eux-mêmes des nombres, des vecteurs ou des matrices; exemples:
# p = u * v (produit de deux nombres réels ou complexes)
# V = q.V₁ (produit d'un vecteur par un réel)
# p = V₁.V₂ (produit scalaire)
# V = V₁×V₂ (produit vectoriel)

... je ne retrouve plus le site ou j'ai piocher ce terme pour cette fonction qu'il est plus correcte d'appeler (après une recherche rapide) un produit dyadique en bon français, outer product ou ce "Perp" appelé aussi "perpendicular cross product" chez les anglais (et là je ne suis même pas sure que ce soit la même définition mathématique, pour le coup) ...

Le produit dyadique de deux vecteurs de (R³):

A = U # V (caractère indisponible)

est le produit tensoriel (c. à d. terme à terme) de la matrice colonne associée à (u) par la matrice ligne associée à V, et conduit à une matrice carrée d'ordre 3:

La notion de produit extérieur est trop complexe pour être évoquée ici.
Quand au "perpendicular cross product", on retombe sur l'article de Wikipédia qui signale deux termes synonymes (vector product, directed area product).

... Voila par exemple ce que l'on peux lire sur wikipedia en anglais à ce propos Cross product

Code :

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

 the magnitude of the product of two perpendicular vectors is the product of their lengths

Magnitude peux donc se traduire par plusieurs termes : Grandeur, Ampleur, Distance ??? donc comme tu le dis ce n'est pas évident du coup. (surtout pour moi, et en plus j'apprends des choses erronées ...

Voici les traductions que donne Linguee de ce mot:

Il s'agit ici de la valeur maximale, qui ne figure pas dans la liste: le terme le moins inapproprié est le mot: amplitude.
À rapprocher de la relation donnée précédemment: ║V║ = ║V1║*║V2║*│Sin(θ)│
qui implique: ║V║ ≤ ║V1║*║V2║ = ║V║_max .
Comme quoi une traduction correcte ne se trouve pas forcément dans un dictionnaire, et demande de connaître ce dont il est question.

[wiwaxia]

Pour tous ceux à qui la rencontre d'une formule mathématique ne procure pas un bonheur parfait:

# l'excellente mise au point d'un membre de développez.com;

# sur le site de Bibm@th.net (tous niveaux):
un formulaire;
un dictionnaire;

# sur le site de Mathovore (?) des formulaires tous niveaux;

# sur les-mathematiques.net, un cours de DEUG/Prépas (un peu raide);

# le site de Gérard Villemain consacré aux nombres (plus ludique);

# celui de Serge Mehl, orienté vers l'histoire (Chronomath);

# l'encyclopédie Mathcurve des courbes et des surfaces;

# MathWorld, la meilleure encyclopédie de mathématiques, facile à comprendre bien qu'écrite en anglais;

# enfin pour toutes les questions que vous vous êtes posées et que vous n'avez jamais osé demander: Wolfram Alpha .

Toute autre suggestion est la bienvenue.

[Guesset]

Bonjour,

Je me suis demandé si pour outrepasser l'algorithme de parité il ne fallait pas persévérer et appliquer cette parité au tracé du contour lui même :

• On trace le contour en 1 pixel de large en mode xor de la couleur du fond (excepté le dernier point de chaque segment)
• On remplit selon l'algorithme pair impair
• on retrace le contour en mode normal (avec sa largeur cible et sa couleur cible)

Je n'ai pas encore testé mais cela me paraît prometteur y compris quand un point appartient à plus de 2 segments de contour.



Qu'en pensez-vous ?

Salutations

[wiwaxia]

L'algorithme de parité séduit par sa simplicité, et été abordé dans une précédente discussion;

https://fr.wikipedia.org/wiki/Th%C3%...A8me_de_Jordan
http://geomalgorithms.com/a03-_inclusion.html

Il ne dispense pas malheureusement d'envisager des cas particuliers dont la résolution est assez lourde; la forme définitive a été donnée plus loin (#38).

L'algorithme ne fait aucune distinction entre les polygones croisé et non croisé initialement proposés par BeanzMaster; la suoerposition totale de deux arêtes - (5,6) et (10.1) - ne conduit cependant pas à une réponse aberrante.

La caractérisation de chaque sommet par la valeur de son angle orienté distingue sans ambiguïté les deux figures:
# polygone croisé:



# polygone non croisé:



Leur programmation est très simple; ils ne diffèrent que par l'échange de deux de leus sommets (de rags 7 et 9):

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
 PROCEDURE Calc_Pol05(La1, Ha1: Z_32; VAR L_V: Tab_V2d);    // NmaxV = 10
   TYPE TabE = ARRAY[1..10] OF Byte;
   CONST f = 0.100;
         Lx1: TabE = (1, 9, 9, 1, 1, 3, 7, 7, 3, 3);          // (1): polygone croisé
         Ly1: TabE = (1, 1, 9, 9, 1, 3, 3, 7, 7, 3);
         Lx2: TabE = (1, 9, 9, 1, 1, 3, 3, 7, 7, 3);          // (2): polygone non croisé
         Ly2: TabE = (1, 1, 9, 9, 1, 3, 7, 7, 3, 3);
   VAR i: Word; p, q: Reel; V: Vect_2D;
   BEGIN
     FOR i:= 1 TO NmaxV DO BEGIN
                             p:= f * Lx2[i]; V.x:= Round(La1 * p);
                             q:= f * Ly2[i]; V.y:= Round(Ha1 * q);
                             L_V[i]:= V
                           END
   END;

[wiwaxia]

L'examen du cas le plus général (où le polygone présente plusieurs boucles) conduit à reprendre le calcul du nombre d'enroulements observés autour de tout point du plan de la figure.
Il s'agit de la fonction Ntour évoquée au message #16 et décrite au suivant (#17) sous la forme d'un booléen - il fallait alors répondre à l'alternative dedans/dehors.
Cette appellation laisse d'ailleurs à désirer, car elle incite à confondre la fonction avec le nombre algébrique d'enroulements que présente le polygone, qui se rattache à la somme des angles orientés de ses sommets:

Ntot = Atot/(2π)

et caractérise la figure considérée.

Ce nouvel outil permet, par la coloration de l'image entière, la distinction immédiate entre les deux polygones litigieux, qui présentent deux arêtes non consécutives entièrement confondues: le premier apparaît manifestement croisé, tandis que le second est simplement concave:

Les colorations appartiennent à une palette dont le paramètre unique (t) varie de (-1) à (+1);
on lui affecte ici la valeur t = Ntour/NtMax, avec dans le cas présent NtMax = 2:

On peut en modifier le niveau de gris central (constante g).

Le programme a été amélioré par la distinction entre la dimension du tableau de vecteurs (NmaxV = 100) et le nombre de sommets (Nsomm1) du polygone étudié:

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
(*HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH
 
 P2 / Fonctions de couleur
 
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH*)
 
 CONST m = 255; g = 0.700; h = 1 - g;                       // g = niveau relatif de gris (<= 1)
       Lim1 = 0.350;       I_Lm1 = 1 / (1 - Lim1);
       Lim2 = 0.400;       L22 = Lim2 * Lim2; I_L4 = 1 / (L22 * L22);
 
 FUNCTION Fc2(t: Reel): Byte;                      // t varie entre -1 et +1
   VAR s, u, v, w: Reel;
   BEGIN
     s:= Abs(t);
     IF (s<Lim1) THEN BEGIN
                        u:= Sqr(s / Lim1); w:= g + (h * u)
                      END
                 ELSE BEGIN
                        u:= (s - Lim1) * I_Lm1;
                        v:= Sqr(u); w:= 1 - v
                      END;
     Result:= Round(m * w)
   END;
 
 FUNCTION Fc1(t: Reel): Byte;                      // t varie entre -1 et +1
   VAR u, v, w: Reel;
   BEGIN
     IF (t<0) THEN BEGIN
                     u:= Sqr(1 + t); v:= Sqr(u); w:= g * v
                   END
              ELSE IF (t<Lim2) THEN BEGIN
                                      u:= Sqr(Sqr(t)); v:= h * u;
                                      w:= g + (I_L4 * v)
                                    END
                               ELSE w:= 1;
     Result:= Round(m * w)
   END;
 
(*HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH
 
 P2 / Procédures et calculs divers
 
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH*)
 
 FUNCTION Norme2(V: Vect_2D): Reel;
   VAR X2, Y2: Z_32;
   BEGIN
     X2:= Sqr(V.x); Y2:= Sqr(V.y);
     Result:= X2 + Y2
   END;
 
 CONST D_Pi = 2 * Pi; H_Pi = Pi / 2;
 
 FUNCTION Angle2Vb(V1, V2: Vect_2D): Reel;
   VAR At, Dt, N1N2, N21, N22, p, Ps, q, Theta: Reel; T1, T2: Bool;
   BEGIN
     N21:= Norme2(V1);     N22:= Norme2(V2); N1N2:= Sqrt(N21 * N22);
     p:= V1.x * V2.x;      q:= V1.y * V2.y;  Ps:= p + q;
     p:= V1.x * V2.y;      q:= V1.y * V2.x;  Dt:= p - q;
     T1:= (N1N2<1E-18);    T2:= (Abs(Ps)<Abs(Dt));
     IF T1 THEN Theta:= 0
           ELSE IF T2 THEN BEGIN
                             At:= ArcTan(Ps/Dt);
                             IF (Dt>0) THEN Theta:= H_Pi - At
                                       ELSE Theta:= -H_Pi - At
                           END
                      ELSE BEGIN
                             At:= ArcTan(Dt/Ps);
                             IF (Ps>0) THEN Theta:= At
                                       ELSE IF (Dt<0) THEN Theta:= At - Pi
                                                      ELSE Theta:= At + Pi
                           END;
     Result:= Theta
   END;
 
 PROCEDURE IncR(VAR u: Reel; v: Reel);
   VAR w: Reel;
   BEGIN
     w:= u + v; u:= w
   END;
 
 FUNCTION Diff_2V(V1, V2: Vect_2D): Vect_2D;
   VAR W12: Vect_2D;
   BEGIN
     W12.x:= V1.x - V2.x;
     W12.y:= V1.y - V2.y; Result:= W12
   END;
 
 PROCEDURE ZeroM(VAR Ma: Tab_Pix);
   CONST Pzero: Pixel = (150, 0, 150);
   VAR i, j: Z_32;
   BEGIN
     FOR i:= 0 TO Dim_Max DO
       FOR j:= 0 TO Dim_Max DO Ma[i, j]:= Pzero
   END;
 
(*HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH
 
 P2 / Calcul de la seconde matrice
 
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH*)
 
 VAR Nsomm1, Ntour1: Byte;
 
 PROCEDURE Trace_Polygone(Imax: Byte; L_V: Tab_V2d; VAR Ma2: Tab_Pix);
   CONST c = 0; Pc: Pixel = (c, c, c);
   VAR i, j: Byte; Dx, Dy, k, Npoint, Xm, Ym: Z_32; I_Np, Kx, Ky: Reel;
       Ta, Tb: Bool; Px: Pixel;
   BEGIN
     FOR i:= 1 TO Imax DO
       BEGIN
         IF (i<Imax) THEN j:= i + 1
                     ELSE j:= 1;
         Dx:= L_V[j].x - L_V[i].x; Dy:=  L_V[j].y - L_V[i].y;
         Npoint:= 1;               Inc(Npoint, Abs(Dx));
         Inc(Npoint, Abs(Dy));     I_Np:= 1 / Npoint;
         Kx:= Dx / Npoint;         Ky:= Dy / Npoint;
         FOR k:= 0 TO Npoint DO
           BEGIN
             Xm:= L_V[i].x; Inc(Xm, Round(k * Kx));
             Ym:= L_V[i].y; Inc(Ym, Round(k * Ky));
             Ma2[Xm, Ym]:= Pc
           END
       END
   END;
 
 PROCEDURE Calc_Mat_Im2(Ns1, Nt1: Byte; La, Ha: Z_32; VAR Ma1, Ma2: Tab_Pix);
   CONST Nmax = 3;
   VAR i, j, Ntour: Byte; Xm, Ym: Z_32; Sa, r: Reel;
       Vg1, Vg2, Vg: Vect_2D; Px: Pixel;
   BEGIN
     ZeroM(Matrice_2);
     FOR Xm:= 0 TO (La - 1) DO
       FOR Ym:= 0 TO (Ha - 1) DO
         BEGIN
           Sa:= 0; Vg.x:= Xm; Vg.y:= Ym;
           FOR i:= 1 TO Ns1 DO
             BEGIN
               IF (i<Ns1) THEN j:= i + 1
                          ELSE j:= 1;
               Vg1:= Diff_2V(Polygone[i], Vg);
               Vg2:= Diff_2V(Polygone[j], Vg);
               IncR(Sa, Angle2Vb(Vg1, Vg2));
             END;
           Ntour:= Round(Sa / D_Pi); r:= Ntour / Nt1;
           IF (r> 1) THEN r:=  1;
           IF (r<-1) THEN r:= -1;
           Px[1]:= Fc1(r);           Px[3]:= Fc1(-r);
           Px[2]:= Fc2(r);           Ma2[Xm, Ym]:= Px
         END
   END;
 
 PROCEDURE Calc_Pol_10(VAR Ns_1, Nt_1: Byte; La1, Ha1: Z_32; VAR L_V: Tab_V2d);    // NmaxV = 10
   CONST N1 = 10; f = 0.100;
   TYPE TabE = ARRAY[1..N1] OF Byte;
   CONST Lx1: TabE = (1, 9, 9, 1, 1, 3, 7, 7, 3, 3); // Polygone crois‚
         Ly1: TabE = (1, 1, 9, 9, 1, 3, 3, 7, 7, 3);
         Lx2: TabE = (1, 9, 9, 1, 1, 3, 3, 7, 7, 3); // Polygone non crois‚
         Ly2: TabE = (1, 1, 9, 9, 1, 3, 7, 7, 3, 3);
   VAR i: Word; p, q: Reel; V: Vect_2D;
   BEGIN
     Ns_1:= N1; Nt_1:= 2;
     FOR i:= 1 TO N1 DO BEGIN
//                          p:= f * Lx1[i]; V.x:= Round(La1 * p);
//                          q:= f * Ly1[i]; V.y:= Round(Ha1 * q);
                          p:= f * Lx2[i]; V.x:= Round(La1 * p);
                          q:= f * Ly2[i]; V.y:= Round(Ha1 * q);
                          L_V[i]:= V
                        END
   END;
 
 PROCEDURE Zero_Pol(VAR Lst_V: Tab_V2d);
   VAR i: Byte;
   BEGIN
     FOR i:= 1 TO NmaxV DO
       WITH Lst_V[i] DO BEGIN
                          x:= 0; y:= 0
                        END
   END;

[Guesset]

Bonjour,

Je ne suis pas sûr que l'ordre du tracé d'un polygone ait une importance quelconque pour distinguer l'intérieur de l'extérieur sur une surface plane. En 3D, savoir quel coté d'une face est tournée vers l'extérieur du volume peut être intéressant (le produit vectoriel sert à cela) mais cela n'a pas de rapport avec le remplissage de l'intérieur d'une surface 2D.

L'algorithme que je propose fait sauter la dépendance aux recouvrements de contours (le mode xor inverse le tracé trait/fond à chaque recouvrement) et permet d'utiliser l'algorithme des parités dans des cas complexes. Il s'applique sur un polygone en mode bitmap (non vectoriel).

Il ne s'intéresse nullement au sens de rotation lors du tracé. En 3D cela pourrait être utile pour déterminer la couleur du remplissage (mais pas le remplissage lui même) puisque nous aurions la normale au tracé avec le produit vectoriel (son spin ?).

Associer la complexité d'une solution à la complexité du problème est une habitude que nous avons tous. Mais ce n'est pas forcément légitime : la théorie des nombres, par exemple, regorge de problèmes courts et simples dont la résolution est très complexe.

Salutations

[BeanzMaster]

Bonjour,

merci wiwaxia, d'abord pour les liens, j'ai commencé à lire deux trois chose, il y a de quoi faire

Je n'ai pas encore analyser tes dernières explications et sources, mais la solution est là

Bonjour,

Je ne suis pas sûr que l'ordre du tracé d'un polygone ait une importance quelconque

En fait les derniers messages de wiwaxia font référence à un autre question que j'ai posé dans la discussion #18.

En ce qui concerne l'algo de parité celui n'est pas 100% parfait voir la capture en fin de message #15 et ici

Merci