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
    Avatar de BeanzMaster
    Homme Profil pro
    Amateur Passionné
    Inscrit en
    septembre 2015
    Messages
    1 345
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Suisse

    Informations professionnelles :
    Activité : Amateur Passionné
    Secteur : Tourisme - Loisirs

    Informations forums :
    Inscription : septembre 2015
    Messages : 1 345
    Points : 3 339
    Points
    3 339
    Billets dans le blog
    2
    Par défaut
    Bonjour wiwaxia merci pour toutes ces explications

    J'ai compris ma "bêtise"

    Effectivement avec ce polygone

    Nom : 2020-01-23_171718.png
Affichages : 44
Taille : 754 octets

    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é

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    1 026
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 73
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 1 026
    Points : 1 905
    Points
    1 905
    Billets dans le blog
    5
    Par défaut 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 ≤ i ≤ N) de l'angle polaire:
    θ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 = Σi=1Ni) = 2π.Nt .
    Nom : Angle de rotation.png
Affichages : 41
Taille : 7,5 Ko
    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:
    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 (⌡Nt⌡ - 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 = (⌡Nt⌡ - 1) MOD 2 .
    Nom : Images_1_2_3_750x338.png
Affichages : 43
Taille : 35,8 Ko
    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 = Σh=1N-2j=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
    Avatar de BeanzMaster
    Homme Profil pro
    Amateur Passionné
    Inscrit en
    septembre 2015
    Messages
    1 345
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Suisse

    Informations professionnelles :
    Activité : Amateur Passionné
    Secteur : Tourisme - Loisirs

    Informations forums :
    Inscription : septembre 2015
    Messages : 1 345
    Points : 3 339
    Points
    3 339
    Billets dans le blog
    2
    Par défaut
    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 = Σh=1N-2j=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é

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    1 026
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 73
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 1 026
    Points : 1 905
    Points
    1 905
    Billets dans le blog
    5
    Par défaut 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 (θm ,... θn) de signe opposé à celui de la somme totale (Atot) - donc supposée non-nulle, et dont la somme partielle
    Amn = Σi=mni)
    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):
    Nom : 0211_Polygone_2 arêtes confondues.png
Affichages : 38
Taille : 11,9 Ko
    (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=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.
    Nom : 0211_Polygone_Centre symétrie.png
Affichages : 39
Taille : 8,3 Ko


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

  5. #25
    Membre chevronné

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    1 026
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 73
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 1 026
    Points : 1 905
    Points
    1 905
    Billets dans le blog
    5
    Par défaut 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π ;
    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 (θ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.

    Nom : 1402_Worley_Ordre 1_350xx.png
Affichages : 30
Taille : 19,9 KoNom : 1402_Worley_Ordre 2_350xx.png
Affichages : 29
Taille : 28,3 Ko
    Nom : 1402_Worley_01_350xx.png
Affichages : 30
Taille : 63,6 Ko


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

  6. #26
    Membre chevronné

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    1 026
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 73
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 1 026
    Points : 1 905
    Points
    1 905
    Billets dans le blog
    5
    Par défaut 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 :

    Nom : 0220_N=100_Polygone.png
Affichages : 22
Taille : 18,5 Ko
    Nom : 0220_N=100_Calcul_1333555333_Vb.png
Affichages : 21
Taille : 29,1 Ko

    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 (θ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 (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é

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    1 026
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 73
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 1 026
    Points : 1 905
    Points
    1 905
    Billets dans le blog
    5
    Par défaut 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 (θi < 0):

    Nom : 0217_N=17_Pol_Liste.png
Affichages : 20
Taille : 27,2 Ko
    Nom : 0217_N=41_Pol Liste.png
Affichages : 20
Taille : 51,3 Ko

    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:

    Nom : 0218_Polygone_5 Carrés_3 Images.png
Affichages : 19
Taille : 18,4 Ko

    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;


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

  8. #28
    Membre expert
    Avatar de BeanzMaster
    Homme Profil pro
    Amateur Passionné
    Inscrit en
    septembre 2015
    Messages
    1 345
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Suisse

    Informations professionnelles :
    Activité : Amateur Passionné
    Secteur : Tourisme - Loisirs

    Informations forums :
    Inscription : septembre 2015
    Messages : 1 345
    Points : 3 339
    Points
    3 339
    Billets dans le blog
    2
    Par défaut
    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π ;
    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 (θ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 (θ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

    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é

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    1 026
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 73
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 1 026
    Points : 1 905
    Points
    1 905
    Billets dans le blog
    5
    Par défaut 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.

    Nom : 0225_Polygone #01.png
Affichages : 3
Taille : 5,5 Ko

    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 ±∞) conduit à choisir celle vérifiant │F(u)│ ≤ 1/√2 , donc u0 = 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:
    Nom : 200225_Equation fonctionnelle.png
Affichages : 5
Taille : 14,2 Ko
    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é, sans exclure une éventuelle discussion - bien que je croie qu'aucune argumentation décisive ne s'en dégage en faveur de l'un ou de l'autre.

    La suite à plus tard.


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

  10. #30
    Membre chevronné

    Homme Profil pro
    Formation: Chimie et Physique (structure de la matière)
    Inscrit en
    décembre 2010
    Messages
    1 026
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 73
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Formation: Chimie et Physique (structure de la matière)
    Secteur : Enseignement

    Informations forums :
    Inscription : décembre 2010
    Messages : 1 026
    Points : 1 905
    Points
    1 905
    Billets dans le blog
    5
    Par défaut Rasterisation de polygone complexe
    Citation Envoyé par BeanzMaster Voir le message
    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 ((Xmin, Ymin) , ((Xmax, Ymax)), et prendre une paire de coordonnées plus élevées:
    XG = Round(k * Xmax) , YG = Round(k * Ymax) 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é (V1, V2) = (GSi, GSj) ,
    et chacun des vecteurs est donné par la relation de Chasles:
    GSi = OSi - OG , GSj = OSj - OG .
    Nom : 0226_Rectangle Polygone.png
Affichages : 2
Taille : 9,7 Ko
    Il est vrai que mes programmes ne pèchent pas par excès de commentaires.


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

Discussions similaires

  1. Réponses: 0
    Dernier message: 02/05/2015, 12h34
  2. Decoupage D'un Raster Par Un Polygone
    Par simolay dans le forum SIG : Système d'information Géographique
    Réponses: 1
    Dernier message: 11/07/2012, 17h41
  3. Triangulation d'un polygone 3D complexe
    Par sapin dans le forum C++
    Réponses: 7
    Dernier message: 10/04/2009, 10h09
  4. [2D] Transformer un polygone complexe en triangle
    Par Kewlcool dans le forum Développement 2D, 3D et Jeux
    Réponses: 11
    Dernier message: 11/12/2008, 22h20
  5. [LOD] Polygons complexes
    Par Mucho dans le forum OpenGL
    Réponses: 4
    Dernier message: 20/10/2006, 15h30

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo