Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Traitement d'images Discussion :

Rasterization de polygone complex


Sujet :

Traitement d'images

  1. #21
    Membre expert
    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
    • "L'Homme devrait mettre autant d'ardeur à simplifier sa vie qu'il met à la compliquer" - Henri Bergson
    • "Bien des livres auraient été plus clairs s'ils n'avaient pas voulu être si clairs" - Emmanuel Kant
    • "La simplicité est la sophistication suprême" - Léonard De Vinci
    • "Ce qui est facile à comprendre ou à faire pour toi, ne l'est pas forcément pour l'autre." - Mon pèrei

    Mes projets sur Github - Blog - Site DVP

  2. #22
    Membre chevronné
    Rastérisation de polygone complexe
    Je reprends la suite des réponses à tes remarques, dont il m'a fallu provisoirement décrocher.

    2°) Le nombre (Nt) de tours effectués caractérisant un polygone résulte de la sommation étendue à tous les sommets (1 &#8804; i &#8804; N) de l'angle polaire:
    &#952;i = (PhPi, PiPj) 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 Atot = &#931;i=1N(&#952;i) = 2&#960;.Nt .
    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 (&#952;i) sont de même signe - voilà une autre définition de la convexité, et une réponse à l'une de tes questions:
    Citation Envoyé par BeanzMaster Voir le message
    ... 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 (&#8993;Nt&#8993; - 1) points d'auto-intersection (fig I : Nt = +4 , Nint = 3); le débordement éventuel d'une boucle sur une autre fait apparaître un nombre pair de points supplémentaires (fig II : Nt = +1 , Nint = 2).
    Il intervient donc déjà dans ce cas simple une relation du type Nint = (&#8993;Nt&#8993; - 1) MOD 2 .
    3°) Un retournement de boucle (fig III : Nt = 0 , Nint = 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
    Citation Envoyé par BeanzMaster Voir le message
    ... 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
    Nint = &#931;h=1N-2(&#931;j=h+2NIntersect(PhPi, PjPk)) ,
    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.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  3. #23
    Membre expert
    Bonjour,
    Citation Envoyé par wiwaxia Voir le message
    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)

    Citation Envoyé par wiwaxia Voir le message

    3°) Un retournement de boucle (fig III : Nt = 0 , Nint = 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.

    Citation Envoyé par wiwaxia Voir le message

    mais qui n'est pas au bout du monde - je le détaillerai, éventuellement.
    Il intervient alors une double sommation de la forme
    Nint = &#931;h=1N-2(&#931;j=h+2NIntersect(PhPi, PjPk)) ,
    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 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
    • "L'Homme devrait mettre autant d'ardeur à simplifier sa vie qu'il met à la compliquer" - Henri Bergson
    • "Bien des livres auraient été plus clairs s'ils n'avaient pas voulu être si clairs" - Emmanuel Kant
    • "La simplicité est la sophistication suprême" - Léonard De Vinci
    • "Ce qui est facile à comprendre ou à faire pour toi, ne l'est pas forcément pour l'autre." - Mon pèrei

    Mes projets sur Github - Blog - Site DVP

  4. #24
    Membre chevronné
    Rastérisation de polygone complexe
    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 (&#952;m ,... &#952;n) de signe opposé à celui de la somme totale (Atot) - donc supposée non-nulle, et dont la somme partielle
    Amn = &#931;i=mn(&#952;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)*&#931;i=1N(Det(GPi, GPj)) avec j = i + 1 si (i<N) sinon j = 1 ;
    chaque déterminant (Det(GPi, GPj) = (GPi×GPj)) représentant l'aire algébrique du parallélogramme construit sur les vecteurs (GPi, GPj), aire égale au double de celle du triangle orienté (GPiPj).
    Elle est, comme l'angle total de rotation (Atot) 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.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  5. #25
    Membre chevronné
    Rastérisation de polygone complexe
    #18
    Citation Envoyé par BeanzMaster Voir le message
    ... 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
    Citation Envoyé par BeanzMaster Voir le message
    ... 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 Atot = ± 2&#960; ;
    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 (Atot) 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 (&#952;i0) présente un signe identique à celui de (Atot).

    #18
    Citation Envoyé par BeanzMaster Voir le message
    ... 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
    Citation Envoyé par BeanzMaster Voir le message
    ... 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
    Citation Envoyé par BeanzMaster Voir le message

    J'ai commencé à faire pas mal de petites recherches sur ces "sweep line" tuto ici et 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.




    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  6. #26
    Membre chevronné
    Rasterisation de polygone complexe
    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:
    xi + xj = La - 1 ; yi + yj = Ha - 1 :



    Il s'agit ici d'une image de dimensions 700x300 ; remarquer la valeur et la constance des sommes (xi + xj ), (yi + yj) - nombres entiers - et (&#952;i + &#952;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 (Xmax, Ymax), ce qui permet de s'assurer du non-débordement de la figure.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  7. #27
    Membre chevronné
    Rasterisation de polygone complexe
    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 (&#952;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 (&#952;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 &#8800; 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;


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  8. #28
    Membre expert
    Bonjour, wiwaxia, c'est à mon tour d'avoir décrocher

    Citation Envoyé par wiwaxia Voir le message
    #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 Atot = ± 2&#960; ;
    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 (Atot) 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 (&#952;i0) présente un signe identique à celui de (Atot).
    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

    Citation Envoyé par wiwaxia Voir le message

    #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.

    Citation Envoyé par wiwaxia Voir le message

    #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.

    Citation Envoyé par wiwaxia Voir le message
    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)

    Citation Envoyé par wiwaxia Voir le message
    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 (&#952;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.


    Citation Envoyé par wiwaxia Voir le message

    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
    • "L'Homme devrait mettre autant d'ardeur à simplifier sa vie qu'il met à la compliquer" - Henri Bergson
    • "Bien des livres auraient été plus clairs s'ils n'avaient pas voulu être si clairs" - Emmanuel Kant
    • "La simplicité est la sophistication suprême" - Léonard De Vinci
    • "Ce qui est facile à comprendre ou à faire pour toi, ne l'est pas forcément pour l'autre." - Mon pèrei

    Mes projets sur Github - Blog - Site DVP

  9. #29
    Membre chevronné
    Rasterisation de polygone complexe
    Bonjour,

    Je vois que tu a lu attentivement les algorithmes.

    Citation Envoyé par BeanzMaster Voir le message
    ... 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 (Xmax, Ymax) des coordonnées des sommets.

    Citation Envoyé par BeanzMaster Voir le message
    ... 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:
    D2i, j > 0 pour tout couple (i, j) vérifiant 0 < i < j <= Nombre de sommets
    b) chaque sommet (Si) hors de toute arête (SjSk), impliquant des angles au sommets non-nuls; on aurait dans le cas contraire:
    Det(SjSi, SjSk) = 0 (vecteurs colinéaires) ,
    Pscal(SjSi, SjSk) > 0 (vecteurs de même sens) ,
    SjSi < SjSk) (Si appartient au segment SjSk ;
    c) les arêtes ne se recouvrent pas, sinon l'on observerait le cas suivant:
    Det(SiSj, SkSl) = 0 (vecteurs colinéaires) ,
    Det(SiSj, SiSk) = 0 (droites confondues) ,
    MiMk < (SiSj + SkSl)/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.

    Citation Envoyé par BeanzMaster Voir le message
    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 (u0) pour laquelle F(u) s'annule:
    F(u0) = 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 ±&#8734 conduit à choisir celle vérifiant &#9474;F(u)&#9474; &#8804; 1/&#8730;2 , donc u0 = 0 ou (±&#960;/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 &#9474;ArcTan(u)&#9474; &#8804; 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 (N1N2 = 0) liée à l'intervention d'un vecteur nul.

    La suite à plus tard.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  10. #30
    Membre chevronné
    Rasterisation de polygone complexe
    Ce message n'a pas pu être affiché car il comporte des erreurs.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  11. #31
    Membre expert
    Ce message n'a pas pu être affiché car il comporte des erreurs.
    • "L'Homme devrait mettre autant d'ardeur à simplifier sa vie qu'il met à la compliquer" - Henri Bergson
    • "Bien des livres auraient été plus clairs s'ils n'avaient pas voulu être si clairs" - Emmanuel Kant
    • "La simplicité est la sophistication suprême" - Léonard De Vinci
    • "Ce qui est facile à comprendre ou à faire pour toi, ne l'est pas forcément pour l'autre." - Mon pèrei

    Mes projets sur Github - Blog - Site DVP

  12. #32
    Membre chevronné
    Rasterisation de polygone complexe
    Ce message n'a pas pu être affiché car il comporte des erreurs.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  13. #33
    Membre expert
    Citation Envoyé par wiwaxia Voir le message
    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.

    Citation Envoyé par wiwaxia Voir le message

    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 )

    Citation Envoyé par wiwaxia Voir le message

    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:
    N1 * N2 = (N12 * N22)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

    Citation Envoyé par wiwaxia Voir le message

    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
    • "L'Homme devrait mettre autant d'ardeur à simplifier sa vie qu'il met à la compliquer" - Henri Bergson
    • "Bien des livres auraient été plus clairs s'ils n'avaient pas voulu être si clairs" - Emmanuel Kant
    • "La simplicité est la sophistication suprême" - Léonard De Vinci
    • "Ce qui est facile à comprendre ou à faire pour toi, ne l'est pas forcément pour l'autre." - Mon pèrei

    Mes projets sur Github - Blog - Site DVP

  14. #34
    Membre chevronné
    Rasterisation de polygone complexe
    Citation Envoyé par BeanzMaster Voir le message
    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.

    Citation Envoyé par BeanzMaster Voir le message
    ... 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.

    Citation Envoyé par BeanzMaster Voir le message
    ... 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.V1 (produit d'un vecteur par un réel)
    # p = V1.V2 (produit scalaire)
    # V = V1×V2 (produit vectoriel)

    Citation Envoyé par BeanzMaster Voir le message
    ... 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 (R3):
    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).

    Citation Envoyé par BeanzMaster Voir le message
    ... 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: &#9553;V&#9553; = &#9553;V1&#9553;*&#9553;V2&#9553;*&#9474;Sin(&#952&#9474;
    qui implique: &#9553;V&#9553; &#8804; &#9553;V1&#9553;*&#9553;V2&#9553; = &#9553;V&#9553;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.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  15. #35
    Membre chevronné
    Rasterisation de polygone complexe
    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.


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  16. #36
    Membre éclairé
    Pair, impair et passe
    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
    Ever tried. Ever failed. No matter. Try Again. Fail again. Fail better. (Samuel Beckett)

  17. #37
    Membre chevronné
    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;


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  18. #38
    Membre chevronné
    Rasterisation de polygone complexe
    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&#960
    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;


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  19. #39
    Membre éclairé
    Sens
    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
    Ever tried. Ever failed. No matter. Try Again. Fail again. Fail better. (Samuel Beckett)

  20. #40
    Membre expert
    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à

    Citation Envoyé par Guesset Voir le message
    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
    • "L'Homme devrait mettre autant d'ardeur à simplifier sa vie qu'il met à la compliquer" - Henri Bergson
    • "Bien des livres auraient été plus clairs s'ils n'avaient pas voulu être si clairs" - Emmanuel Kant
    • "La simplicité est la sophistication suprême" - Léonard De Vinci
    • "Ce qui est facile à comprendre ou à faire pour toi, ne l'est pas forcément pour l'autre." - Mon pèrei

    Mes projets sur Github - Blog - Site DVP