Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 28-03-2021 19:53:22

Wiwaxia
Membre
Lieu : Paris 75013
Inscription : 21-12-2017
Messages : 409

La réduction des polyèdres convexes à l'intersection de demi-espaces

Bonjour,

Je prends l'initiative d'ouvrir un nouveau sujet afin de ne pas dévier inutilement une discussion lancée par Bernard-maths:

http://www.bibmath.net/forums/viewtopic.php?id=13396

qui part d'une idée apparentée mais la développe dans une direction spécifique

J'ai repris le contenu du message(#100) posté à la page (4)

http://www.bibmath.net/forums/viewtopic … =13396&p=4

et transféré les interventions qui ont suivi, qui n'avaient (heureusement) pas encore reçu de commentaire: la discussion n'en sera donc pas perturbée.

L'idée initialement exprimée était l'exploitation astucieuse, au moyen de la fonction valeur absolue, de la définition de tout polyèdre convexe considéré comme l'ensemble des solutions d'un système d'inéquations linéaires.

https://mathworld.wolfram.com/Polyhedron.html

Soit un plan (P), et (H) le pied de la perpendiculaire abaissée sur celui-ci depuis une origine donnée (O).
Ce plan est séparé du point (O) par la distance au centre Dc = OH ;
son orientation spatiale est définie par le vecteur unitaire (un) colinéaire à (OH) et de même sens:

un = (1/OH).OH .

KCygoGlNgNx_Equation-d-un-plan-dans-l-espace.png
On a pour tout point (M) du plan considéré HM perpendiculaire à un,
ce qui se traduit par l'annulation du produit scalaire correspondant: un.HM = 0 ;
en tenant compte de ce que HM = OM - OH ,
et en posant p = un.OM , il vient:

p - un.OH = 0 = p - (OH)(un.un) ,

soit finalement: p - Dc = 0 .

Soit maintenant un point quelconque (M) et la fonction F(p) = p - Dc + |p - Dc| ;
son expression dépend de la position du point par rapport au plan d'équation p = Dc :
a) si p ≤ Dc , alors F(p) = p - Dc + (Dc - p) = 0 ;
b) si p > Dc , alors F(p) = 2(p - Dc) > 0 .
Deux régions de l'espace, séparées par le plan frontière d'équation p = Dc , sont par conséquent discernables:
a) celle qui contient l'origine, caractérisée (comme le plan limite) par l'égalité F(p) = 0 ;
b) l'autre pour laquelle on a F(p) > 0 .

Élargissons désormais la notion précédente au cas d'un polyèdre convexe, défini par la donnée d'au moins 4 plans entourant l'origine, en considérant la somme suivante étendue à toutes les faces présentes dont chacune est caractérisée par le couple (unj , Dcj):

S(M) = Σj=1Nf (Fj(p)) ;

Le domaine intérieur (faces incluses) du polyèdre est caractérisé par l'égalité S(M) = 0 ;
comme il n'intervient en effet que des termes non-négatifs, chacun d'eux est obligatoirement nul:

Fj(p) = 0 ;

on définit ainsi l'intersection commune à tous les demi-espaces délimités par les diverses faces, et contenant l'origine.

Remarques:
# La donnée des sommets n'est pas indispensable: il suffit simplement de connaître pour chaque face la distance (Dcj) la séparant du centre, et les composantes du vecteur unitaire normal (unj) correspondant.
# La présence d'un centre de symétrie n'est pas nécessaire; s'il existe toutefois, l'expression de la somme S(M) se simplifie par regroupement des termes, dont le nombre est divisé par deux; on retrouve alors une expression du type:

S(M) = Σ (|Dc + p| + |Dc - p|) .

Dernière modification par Wiwaxia (29-03-2021 06:59:39)

Hors ligne

#2 28-03-2021 19:56:05

Wiwaxia
Membre
Lieu : Paris 75013
Inscription : 21-12-2017
Messages : 409

Re : La réduction des polyèdres convexes à l'intersection de demi-espaces

Bonjour,

Je reprends ici l'un des polyèdres cités en exemple au cours des échanges sur les oloïdes (message #09)
http://www.bibmath.net/forums/viewtopic.php?id=13733
L'objet est construit sur deux groupes de 3 segments de même longueur, respectivement situés dans les plans (xOz) et (yOz) du repère orthonormé direct orientant l'espace, et dont l'axe de symétrie commun (z'z) constitue l'axes de roto-inversion d'ordre (4) de l'ensemble.
Il n'y a pas de symétrie centrale.

KCzidSniHKx_Poly-NFA=08.12.18-A=32%C2%B0-Lam=03%C2%B0.png

La programmation des positions des 8 sommets envisagés ne présente aucune difficulté:


 PROGRAM Polyedre;

(*HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH

 Repr‚sentation en perpective des faces d'un poly‚dre … 26 faces

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH*)

 USES Crt, E_Texte, U_Copie_1F, Math, U_Math;

 CONST Nsomm = 8; Nface = 12;

 TYPE Ve3D = RECORD  x, y, z: Reel  END;
      Tab_V = ARRAY[1..Nsomm] OF Ve3D;
      Face = RECORD  Sa, Sb, Sc: Byte;
                     Un: Ve3D; Dc: Reel  END;
      Tab_F = ARRAY[1..Nface] OF Face;
      Tab_C = ARRAY[1..Nface] OF Pixel;

 VAR Rcen: Z_32;
     Vun1, Vun2, Vun3: Ve3D;
     LstS: Tab_V;
     LstF: Tab_F;
     LstC: Tab_C;
// ... / ...
 CONST DegRad = Pi / 180; AlphaDeg = 32.0; // Valeur de Alpha en degr‚s

 PROCEDURE AffSxyz;
   CONST L1 = 2; L2 = L1 + 1; v = 12; w = 5;
   VAR k: Byte;
   BEGIN
     E(1012); Wt(1, L1, '    k');
     E(0015); Write('     x           y');
     E(0011); Write('           z');
     FOR k:= 1 TO Nsomm DO
       BEGIN
         E(0012); We(1, k + L2, k, w);
         E(0015); Write(LstS[k].x:v:w, LstS[k].y:v:w);
         E(0011); Write(LstS[k].z:v:w)
       END;
     E(0015); Wt(49, L1, 'Valeur de Alpha:');
     E(0011); Wr(49, L1 + 2, AlphaDeg, 1003); Write(' ø')
   END;

 PROCEDURE Calc_S(Rsph: Reel; VAR L_s: Tab_V);
   VAR k:Byte; Alpha1, C1, C3, Rc1, Rc3, Rs1, Rs3, S1, S3: Reel;
   BEGIN
     Alpha1:= AlphaDeg * DegRad;
     SinCos(Alpha1, S1, C1);           SinCos(3 * Alpha1, S3, C3);
     Rc1:= Rsph * C1;                  Rs1:= Rsph * S1;
     Rc3:= Rsph * C3;                  Rs3:= Rsph * S3;
     L_s[1].x:= Rs3;  L_s[2].x:= Rs1;  L_s[3].x:= -Rs1; L_s[4].x:= -Rs3;
     L_s[1].z:= Rc3;  L_s[2].z:= Rc1;  L_s[3].z:=  Rc1; L_s[4].z:=  Rc3;
     FOR k:= 1 TO 4 DO L_s[k].y:= 0;
     L_s[5].y:=  Rs3; L_s[6].y:=  Rs1; L_s[7].y:= -Rs1; L_s[8].y:= -Rs3;
     L_s[5].z:= -Rc3; L_s[6].z:= -Rc1; L_s[7].z:= -Rc1; L_s[8].z:= -Rc3;
     FOR k:= 5 TO 8 DO L_s[k].x:= 0;   AffSxyz
   END;          

Il faut ensuite inventorier les diverses faces, lesquelles se caractérisent par:
# les indices respectifs (Ja, Jb, Jc) de leurs 3 sommets, donnés dans l'ordre croissant,
# les composantes du vecteur unitaire normal (Un), et
# la distance (Dc) les séparant de l'origine (O) du repère, et dans le cas présent centre de la sphère circonscrite au polyèdre.
Le critère de reconnaissance d'une face consiste en ceci que pour un triplet (i, j, k) donné, tous les autres points sont situés, comme l'origine, du même côté par rapport au plan (Mi, Mj, Mk);
par conséquent les produits mixtes (MiMj, MiMk, MiMl) et (MiMj, MiMk, MiO) sont de même signe pour tout (l) différent de (i, j) et (k).
Il n'y a ici que des faces triangulaires; la présence de faces à plus de 3 sommets n'introduit pas de difficulté insurmontable.


(*HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH

 D‚termination des sommets, des faces et des arˆtes

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH*)

 PROCEDURE AffF(VAR L_F: Tab_F);
   CONST L1 = 14; L2 = L1 + 1; v = 11; w = 5;
   VAR k: Byte;
   BEGIN
     E(0012); Wt(1, L1, '    j');
     E(0015); Write('   Ja   Jb   Jc      ');
     E(0010); Write('Nx         Ny         Nz        ');
     E(0014); Write('Dcen');
     FOR k:= 1 TO Nface DO
       WITH L_f[k] DO
         BEGIN
           E(0012); We(1, k + L2, k, w);
           E(0015); Write(Sa:w, Sb:w, Sc:w);
           E(0010); Write(Un.x:v:w, Un.y:v:w, Un.z:v:w);
           E(0014); Write(Dc:v:w)
         END;
     A_
   END;

 PROCEDURE Calc_F(VAR L_F: Tab_F);
   CONST Vzero: Ve3D = (x:0; y:0; z:0); Epsilon = -1E-10;
   VAR h, i, j, k, l: Byte; Pcen, q: Reel;
       Wj, Wk, Wn, Wcen, Wl: Ve3D; Test: Bool;
   BEGIN
     h:= 0;
     FOR i:= 1 TO (Nsomm - 2) DO
       BEGIN
         Wcen:= Diff2V(Vzero, LstS[i]);
         FOR j:= (i + 1) TO (Nsomm - 1) DO
           FOR k:= (j + 1) TO Nsomm DO
             BEGIN
               Wj:= Diff2V(LstS[j], LstS[i]);
               Wk:= Diff2V(LstS[k], LstS[i]);
               Wn:= Pvect(Wj, Wk); Pcen:= Pscal(Wn, Wcen);
               IF (Abs(Pcen)>Epsilon) THEN
                 BEGIN
                   Test:= True;
                   FOR l:= 1 TO Nsomm DO
                     IF (l<>i) AND ((l<>j) AND (l<>k)) THEN
                       BEGIN
                         Wl:= Diff2V(LstS[l], LstS[i]);
                         q:= Pscal(Wn, Wl);
                         IF ((Pcen * q)<-Epsilon) THEN Test:= False
                       END;
                   IF (Test AND (h<Nface)) THEN
                     BEGIN
                       Inc(h);
                       WITH L_F[h] DO
                         BEGIN
                           Sa:= i;               Sb:= j; Sc:= k;
                           Un:= Vunit(Pcen, Wn); Dc:= Pscal(LstS[i], Un)
                         END
                     END
                 END
             END
       END
   END;          

L'identification des arêtes est ici inutile.

L'affichage des données relatives aux sommets et aux faces permet de s'assurer de la conformité géométrique de l'objet attendu:

KCzi6CdVqQx_Resultats-A=32%C2%B0-Lam=03%C2%B0-Phi=20%C2%B0.png

Reste à donner le programme principal, les calculs préliminaires relatifs au nouveau repère et à la palette de couleur


(*HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH

 Calcul des couleurs

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH*)

 FUNCTION Lum(p: Reel): Byte;
   VAR u, v, w: Reel;
   BEGIN
//     u:= 1 + p; v:= Sqr(p - 0.5); w:= Sqrt(u * v);
//     Result:= Round(361.331 * w)
     u:= Sqrt(1 + p); Result:= Round(180.6657 * u)
   END;

 PROCEDURE Init_Lc(VAR L_c: Tab_C);
   VAR k: Byte; Px: Pixel;
   BEGIN
     FOR k:= 1 TO Nface DO
       WITH LstF[k].Un DO BEGIN
                             Px[1]:= Lum(-x); Px[2]:= Lum(y);
                             Px[3]:= Lum(-z); L_c[k]:= Px
                           END
   END;
(*HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH

 Calculs relatifs au nouveau repŠre

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH*)

 PROCEDURE CalcRc(La, Ha: Z_32; VAR Rs_: Z_32);
   BEGIN
     IF (La<Ha) THEN Rs_:= La DIV 2
                ELSE Rs_:= Ha DIV 2
   END;

 CONST LambdaDeg = 3.0; PhiDeg = 20.0;

 PROCEDURE Calc_U0123(VAR U_1, U_2, U_3: Ve3D);
   CONST DegRad = Pi / 180;
   VAR Clam, Cphi, Slam, Sphi: Reel; W: Ve3D;
   BEGIN
     SinCos(LambdaDeg * DegRad, Slam, Clam);
     SinCos(PhiDeg * DegRad, Sphi, Cphi);
     W.x:= -Sphi;         W.y:= Cphi;          W.z:= 0;    U_1:= W;
     W.x:= - Slam * Cphi; W.y:= - Slam * Sphi; W.z:= Clam; U_2:= W;
     W.x:= Clam * Cphi;   W.y:= Clam * Sphi;   W.z:= Slam; U_3:= W
   END;

(*HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH

 Programme principal

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH*)

 BEGIN
   Copie_F1;                     A_;
   Calc_U0123(Vun1, Vun2, Vun3); CalcRc(Larg_Image, Haut_Image, Rcen);
   Calc_S(Rcen * 0.960, LstS);   AffSxyz;
   Calc_F(LstF);                 AffF(LstF);
   Init_Lc(LstC);

   Calc_Mat_Im2(Larg_Image, Haut_Image, Rcen, Matrice_2);
   Creation_F2
 END.          

... et enfin le tracé de l'image, ainsi que les fonctions utilitaires:


(*HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH

 Utilitaires

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH*)

 FUNCTION Pvect(Wa, Wb: Ve3D): Ve3D;
   VAR p, q: Reel; W: Ve3D;
   BEGIN
     p:= Wa.y * Wb.z; q:= Wa.z * Wb.y; W.x:= p - q;
     p:= Wa.z * Wb.x; q:= Wa.x * Wb.z; W.y:= p - q;
     p:= Wa.x * Wb.y; q:= Wa.y * Wb.x; W.z:= p - q; Result:= W
   END;

 FUNCTION Diff2V(Wa, Wb: Ve3D): Ve3D;
   VAR W: Ve3D;
   BEGIN
     W.x:= Wa.x - Wb.x; W.y:= Wa.y - Wb.y;
     W.z:= Wa.z - Wb.z; Result:= W
   END;

 FUNCTION Vunit(Pc: Reel; V: Ve3D): Ve3D;
   VAR I1, N1, p, q, r, s: Reel; W: Ve3D;
   BEGIN
     p:= Sqr(V.x);     q:= Sqr(V.y);   r:= Sqr(V.z);   s:= p + q;
     N1:= Sqrt(r + s); IF (Pc<0) THEN I1:= 1 / N1 ELSE I1:= -1 / N1;
     W.x:= V.x * I1;   W.y:= V.y * I1; W.z:= V.z * I1; Result:= W
   END;

 FUNCTION Pscal(Wa, Wb: Ve3D): Reel;
   VAR p, q, r, s: Reel;
   BEGIN
     p:= Wa.x * Wb.x; q:= Wa.y * Wb.y; r:= Wa.z * Wb.z;
     s:= p + q;       Result:= r + s
   END;

(*HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH

 Caculs relatifs au polyŠdre

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH*)

 FUNCTION CombLin3V(C1, C2, C3: Z_32; V1, V2, V3: Ve3D): Ve3D;
   VAR W: Ve3D;
   BEGIN
     WITH W DO
       BEGIN
         x:= C1 * V1.x; IncR(x, C2 * V2.x); IncR(x, C3 * V3.x);
         y:= C1 * V1.y; IncR(y, C2 * V2.y); IncR(y, C3 * V3.y);
         z:= C1 * V1.z; IncR(z, C2 * V2.z); IncR(z, C3 * V3.z)
       END;
     Result:= W
   END;

 FUNCTION Identif_F(X1, Y1, Z1: Z_32): Byte;
//   CONST Seuil = 1E-10;
   VAR j, Jf: Byte; Max, p, q, r, s: Reel; W: Ve3D;
   BEGIN
     W:= CombLin3V(X1, Y1, Z1 + 1, Vun1, Vun2, Vun3); Jf:= 0; Max:= 0;
     FOR j:= 1 TO Nface DO
       BEGIN
         p:= Pscal(LstF[j].Un, W); q:= p - LstF[j].Dc;
         r:= Abs(q);               s:= q + r;
         IF (s>Max) THEN BEGIN
                           Jf:= j; Max:= s
                         END
       END;
     Result:= Jf
   END;

 FUNCTION F_Polyedre(X1, Y1, Z1: Z_32): Reel;
   VAR j: Byte; p, q, r, s: Reel; W: Ve3D;
   BEGIN
     W:= CombLin3V(X1, Y1, Z1, Vun1, Vun2, Vun3);
     s:= 0;
     FOR j:= 1 TO Nface DO
       BEGIN
         p:= Pscal(LstF[j].Un, W); q:= p - LstF[j].Dc;
         r:= Abs(q);               IncR(s, q + r)
       END;
     Result:= s
   END;

 PROCEDURE Calc_Mat_Im2(La, Ha, Rc: Z_32; VAR Ma2: Tab_Pix);
   CONST Seuil = 1E-10; P000: Pixel = (0, 0, 0);
   VAR Iface: Byte;
       Xcen, Ximg, Xm, Ycen, Yimg, Ym, Zimg, Zmin: Z_32;
       u: Reel; Px: Pixel;
   BEGIN
     Xcen:= La DIV 2; Ycen:= Ha DIV 2; Zmin:= -2 * Rc;
     FOR Xm:= 0 TO (La - 1) DO
       BEGIN
         Ximg:= Xm - Xcen; We(10, 40, Xm, 6);
         FOR Ym:= 0 TO (Ha - 1) DO
           BEGIN
             Yimg:= Ym - Ycen; Zimg:= 0;
             REPEAT
               Dec(Zimg); u:= F_Polyedre(Ximg, Yimg, Zimg + Rcen)
             UNTIL ((u<Seuil) OR (Zimg=Zmin));
             IF (Zimg=Zmin) THEN Px:= P000
                            ELSE BEGIN
                                   Iface:= Identif_F(Ximg, Yimg,
                                                     Zimg + Rcen);
                                   Px:= LstC[Iface]
                                 END;
             Ma2[Xm,Ym]:= Px
           END
       END
   END;          

Voici ce que cela donne - deux fonctions ont été données pour la palette de couleur, et l'on peut à loisir y inverser les signes des termes (x, y, z):

KCzjxfSdgwx_Deux-Polygones-A=32%C2%B0.png

Dernière modification par Wiwaxia (28-03-2021 20:03:15)

Hors ligne

#3 28-03-2021 19:57:47

Wiwaxia
Membre
Lieu : Paris 75013
Inscription : 21-12-2017
Messages : 409

Re : La réduction des polyèdres convexes à l'intersection de demi-espaces

J'ai regardé ce que donnait l'exécution du programme dans le cas du polyèdre d'ordre 21, les points extrêmes des deux lignes brisées (M1 et M21, M22 et M42) se retrouvant tous dans le plan (xOy) de cote nulle.

Cette version de diffère de la précédente que par la procédure d'initialisation des coordonnées des sommets, qui doit être rationalisée.


 PROCEDURE Calc_S(Rsph: Reel; VAR L_s: Tab_V);
   CONST Imax = (Nsomm + 2) DIV 4; I2 = 2 * Imax;  // Imax = 11 ; I2 = 22
         Jmax = (3 * Imax) - 1;    J2 = 2 * Jmax;  // Jmax = 32 ; J2 = 64
   VAR i, j: Z_08; Alpha1, Alpha, Ca, Rc, Rs, Sa: Reel;
   BEGIN
     Alpha1:= AlphaDeg * DegRad;
     FOR i:= 1 TO Imax DO
       BEGIN
         Alpha:= Alpha1 * (Imax - i); SinCos(Alpha, Sa, Ca);
         Rs:= Rsph * Sa;              Rc:= Rsph * Ca;
         WITH L_s[i] DO BEGIN
                          x:= Rs; y:= 0; z:= Rc
                        END;
         j:= i - 1; Inc(j, I2);                            // j = i + 21
         WITH L_s[j] DO BEGIN
                          x:= 0; y:= Rs; z:= -Rc
                        END;
         IF (i<Imax) THEN WITH L_s[I2 - i] DO BEGIN
                                                 x:= -Rs; y:= 0; z:= Rc
                                               END;
         IF (j<Jmax) THEN WITH L_s[J2 - j] DO BEGIN
                                                x:= 0; y:= -Rs; z:= -Rc
                                              END
       END
   END;          

KCzrKMjAXFx_SFA=42-80-120-R%C3%A9sultas-S.png

Interviennent dans ce cas 42 sommets, 80 faces et 120 arêtes; l'exécution du programme demande plusieurs minutes.

On découvre dans le second tableau
https://www.cjoint.com/doc/21_03/KCzrMM … -01-80.png
que les 80 faces apparaissent équidistantes du centre (O); ceci est lié à la contrainte imposée à la répartition des sommets, entre autres la coplanéité des points précédemment cités (z01 = z21 = z22 = z42 = 0); il existe donc dans le polyèdre une sphère inscrite tangente à chacune des faces.

En ce qui concerne l'image obtenue, il est plus difficile d'obtenir un contraste suffisant dans toutes les zones de l'image:


KCzrPNum2ix_4-images-SFA=42-80-120.png

Dernière modification par Wiwaxia (28-03-2021 20:04:15)

Hors ligne

#4 28-03-2021 19:58:47

Wiwaxia
Membre
Lieu : Paris 75013
Inscription : 21-12-2017
Messages : 409

Re : La réduction des polyèdres convexes à l'intersection de demi-espaces

J'ai relancé le programme pour une image de dimensions 701×701 : le calcul s'effectue alors en une vingtaine de minutes.

L'obtention de teintes suffisamment contrastées relève d'une loterie chromatique:

 FUNCTION Lum(h, p: Reel): Byte;
   VAR u, v: Reel;
   BEGIN
     u:= h * (1 + p);
     IF (p>0) THEN v:= Abs(Cos(u))
              ELSE v:= Abs(Sin(u)); Result:= Round(255.499 * v)
   END;

 PROCEDURE Init_Lc(VAR L_c: Tab_C);           // ! Meilleures couleurs
   CONST K1 = 3.080; K2 = 1.5 * K1; K3 = 2 * K1;
   VAR k: Byte; Px: Pixel;
   BEGIN
     FOR k:= 1 TO Nface DO
       WITH LstF[k].Un DO BEGIN
                             Px[1]:= Lum(K3, x); Px[2]:= Lum(K2, y);
                             Px[3]:= Lum(K1, z); L_c[k]:= Px
                           END
   END;          

KCCrgGQs58x_SAF=42-80-120-.png

Dernière modification par Wiwaxia (28-03-2021 20:05:39)

Hors ligne

#5 28-03-2021 20:15:39

Bernard-maths
Membre
Lieu : 34790 Grabels
Inscription : 18-12-2020
Messages : 1 316

Re : La réduction des polyèdres convexes à l'intersection de demi-espaces

Bonsoir Wiwaxia, et les autres ... z'aussi !

Très jolie cette "oloïde polyédriquée", c'était un peu ce que je cherchais à faire , en partant de tétraèdres ...

L'option des demi-espaces, faisant appel à un "centre", et que je n'ai pas vraiment suivie, est une alternative à ce que je t'avais suggéré, les bandes de plan, ou les tranches d'espace.

Et cela donne de belles images avec tes programmes !

De mon côté, je vais continuer les polyèdres rayonnant, car il y a encore beaucoup à dire !

Bonne soirée, Bernard-maths

Dernière modification par Bernard-maths (28-03-2021 20:20:18)


Ma philosophie est immuable : l'immobilisme tue ...
Les Anciens ont trouvé le plus facile ... il nous reste le plus dur !

Hors ligne

#6 29-03-2021 08:56:06

Wiwaxia
Membre
Lieu : Paris 75013
Inscription : 21-12-2017
Messages : 409

Re : La réduction des polyèdres convexes à l'intersection de demi-espaces

Bonjour Bernard-maths,

Bernard-maths a écrit :

... Très jolie cette "oloïde polyédriquée" ...

Le résultat est en effet fascinant. Cependant le polyèdre considéré est une approximation d'un sphéricône, et non d'un oloïde

Ne pas confondre l'oloïde avec le sphéricône, qui est l'enveloppe convexe de deux demi-cerles orthogonaux de mêmes centres. Sa surface est également développable puisque formée de 4 portions de cônes de révolution qui se raccordent "tangentement", mais avec des discontinuités de courbure.
https://mathcurve.com/surfaces/orthobic … ycle.shtml

La discussion que tu as lancée en décembre s'est déjà ramifiée en 3 fils différents ... qui dit mieux ?

Hors ligne

#7 29-03-2021 21:11:49

Bernard-maths
Membre
Lieu : 34790 Grabels
Inscription : 18-12-2020
Messages : 1 316

Re : La réduction des polyèdres convexes à l'intersection de demi-espaces

Bonsoir !

C'est vrai, je n'avais pas bien vu que c'était "tassé" !

Trois fils déjà !? Et dire que j'en ai d'autres ... possibles.

Mais celui-ci, que tu viens de lancer, et qui s'apparente aux bandes ou tranches, me servira aussi à moi, pour dire en tranches ce que tu diras en demis espaces ?

Après, on verra !

Bonne nuit ! Bernard-maths

Dernière modification par Bernard-maths (29-03-2021 21:12:13)


Ma philosophie est immuable : l'immobilisme tue ...
Les Anciens ont trouvé le plus facile ... il nous reste le plus dur !

Hors ligne

#8 31-03-2021 14:00:29

Bernard-maths
Membre
Lieu : 34790 Grabels
Inscription : 18-12-2020
Messages : 1 316

Re : La réduction des polyèdres convexes à l'intersection de demi-espaces

Bonjour à tous, et à Wiwaxia !

L'ouverture de ce nouveau fil de discussion était devenu quasi inévitable, vu les digressions que nous nous sommes déjà permises, dans celle du cube et des équations. Alors ...

Quelques réflexions et recherches, menées depuis plusieurs années (2018), m’amènent à vous dire … ce qui suit.

A )) Les équations de polyèdres de l’espace sont-elles encore à l’ordre du jour … ? Ou celles de polygones dans le plan ? OUI !
Personnellement, je ne connais pas de « méthode générale » pour en définir, mais j’ai tenté plusieurs approches …
Et il existe des tas de cas particuliers aussi !

Qu’est-ce qu’un polyèdre (ou polygone) ? C’est un objet comportant un certains nombre de points appelés sommets ; certains de ces sommets sont reliés deux à deux par des segments appelés arêtes ; certaines arêtes sont coplanaires et forment alors un polygone (plan) appelé face.

Et selon Wikipedia :

Un polyèdre est une forme géométrique à trois dimensions (un solide géométrique) ayant des faces planes polygonales qui se rencontrent selon des segments de droite qu'on appelle arêtes.

Le mot polyèdre, signifiant à plusieurs faces, provient des racines grecques πολύς (polys), « beaucoup » et ἕδρα (hedra), « base », « siège » ou « face »1. Un polyèdre est un solide dont toutes les faces sont des polygones. Les côtés de ces polygones sont appelés arêtes. Les extrémités des arêtes sont des points appelés sommets.

Très instructif à lire, de toute façon :    Polyèdre — Wikipédia (wikipedia.org)

Qu’en penser ? Ces 2 approches sous-entendent que l’objet est de dimensions finies, autrement dit, qu’on peut le mettre dans une boite (un cube), ou un carré pour un polygone. D’après cela, il n’existe donc pas de polyèdre « infini », ou « ouvert ? » … bien qu’on puisse les envisager !

Par exemple, prenons un vase à base carré, les 4 bords étant des trapèzes (isocèles) allant en s’élargissant … on a déjà 5 faces, on peut en ajouter une sixième en « fermant » le haut en carré. Ce polyèdre est bien un polyèdre donc ! Mais imaginons que les 4 côtés soient « infinis », qu’ils se prolongent indéfiniment. Il n’y a donc que 5 faces, et il est ouvert … mais il n'a que 4 sommets et 8 arêtes ?

De plus Wikipedia note au passage qu’il s’agit d’un « solide », et non seulement d’un « volume » … donc un objet « plein » !
Or nous ne percevons que l’aspect extérieur, surfacique … et certaines représentations « artistiques » ne font voir que les arêtes (grossies) … Il y a donc plusieurs approches possibles concernant un polyèdre (ou polygone).

B )) Alors, quelle équation ? Personnellement je suis amené à distinguer 4 sortes d’équations !
1)    Equation des sommets : facile ;        attention : la donnée des sommets ne détermine pas le polyèdre !
2)    Equation des arêtes : pas évident ;
3)    Equations des faces : pas évident ;
4)    Equation du volume : « assez » facile !            Hum !!!

En plus ces équations dépendent d’autre(s) caractéristique(s) de forme du polyèdre (polygone) … que nous allons voir.
En effet, un polyèdre peut être convexe, croisé, avec des trous, etc … Les plus « simples » sont-ils convexes ?
En fait … certains polyèdres ne sont pas des polyèdres, mais des « machin-èdres » … ? (Réflexion personnelle …)

C )) Polyèdre convexe : un polyèdre est dit convexe s’il est entièrement situé d’un seul côté de chaque plan de chacune de ses faces. Pour un polygone, d’un seul côté de chaque droite support de chacun de ses côtés.

Conséquence 1 : de chaque point intérieur, il est possible de joindre tout point d’une face par un segment intérieur au polyèdre. Donc sans recouper une autre face. (Adapter au polygone).
Il est alors possible de trouver une (des) équation(s) volumique(s) …

Conséquence 2 : pour chaque face, il est possible de tracer un plan parallèle au plan de la face, et passant par le sommet (il peut y en avoir plusieurs) le plus éloigné de la face. Le polyèdre est alors entièrement compris dans la « tranche d’espace » ainsi définie par ces 2 plans parallèles. Alors le polyèdre convexe est (en volume) l’intersection de toutes les tranches d’espace définies par les faces.
Ce qui permettra d’en tirer une équation volumique !

Conséquence 3 : il me semble fortement possible, mais cela reste à démontrer, que tout polyèdre peut se décomposer en un nombre fini de polyèdres convexes !? Alors, par cumul des équations convexes, il devient possible de déduire une équation volumique de tout polyèdre … Nous essayerons d’en montrer des exemples … ?


D )) Les surfaces de niveaux : les équations volumiques sont de la forme : Somme( fi(x) ) = 0, avec chaque fi(x) >= 0. Ce qui entraine que chaque fi(x) = 0 ! Ce qui veut dire qu’on est physiquement d’un certain côté d’un plan, pour les n plans des n faces. Donc on est à l’intérieur du polyèdre considéré.

En dehors du polyèdre les fi(x) sont > 0, et Somme( fi(x) ) > 0 … ! Alors si e est un réel > 0, que peut-on dire de l’égalité :
Somme( fi(x) ) = e ? On va constater qu’il s’agit d’un ensemble de points disposés en une surface entourant le polyèdre.

Cette surface, que j’appelle « de niveau » définit un nouvel objet, qui est un polyèdre "surfacique", constitué de faces parallèles à celles du polyèdre de départ (isométriques ?), à une distance dépendant de e, et de faces rectangulaires inclinées sur les arêtes de départ, et enfin de polygones inclinés sur les sommets de départ !!! (en général). Ce qui correspond à un polyèdre tronqué, « homothétique » du polyèdre de départ … !!!

E )) Finalement : c’est autour de ces méthodes diverses que la suite de cette nouvelle discussion va se dérouler.
Informations données, selon mes connaissances, ou mes « subodorations » (éclairées ?).

Cordialement, Bernard-maths.

PS : voici un machin-èdre 01, pour le plaisir des yeux ... Quelle équation peut correspondre ? (aucune idée !)


KCFoGjIDbOG_Macin-%C3%A8dre-01.jpg

Pourtant je vois une possibilité, je vous laisse chercher !!! Le tout est dans un cube de côté 10 ...

Dernière modification par Bernard-maths (01-04-2021 07:45:47)


Ma philosophie est immuable : l'immobilisme tue ...
Les Anciens ont trouvé le plus facile ... il nous reste le plus dur !

Hors ligne

#9 01-04-2021 08:02:08

Wiwaxia
Membre
Lieu : Paris 75013
Inscription : 21-12-2017
Messages : 409

Re : La réduction des polyèdres convexes à l'intersection de demi-espaces

Bonjour,

J'avais déjà signalé qu'il n'est pas nécessaire, dans le cas d'un polyèdre convexe, de prédéfinir la position des sommets:

Wiwaxia a écrit :

... # La donnée des sommets n'est pas indispensable: il suffit simplement de connaître pour chaque face la distance (Dcj) la séparant du centre, et les composantes du vecteur unitaire normal (unj) correspondant ...

Voici par exemple ce que l'on obtient dans le cas du dodécaèdre rhombique

https://mathcurve.com/polyedres/dodecae … ique.shtml

dont les 12 faces en losange sont perpendiculaires aux segments joignant le centre d'un cube aux milieux de ses arêtes; les normales correspondent alors aux 12 permutations du type

(0, ± a, ± a), avec a = 1/√2 :

KDbgtOLEN6x_Tableau-SFA=14.12.24.png

La suppression du calcul des coordonnées des sommets simplifie le programme, qui ne livre plus les indices caractérisant les faces dans sa version la plus simple.

KCDvTwkSgix_SFA=14-12-24-C=29.30.31.png


 PROGRAM Polyedre;

(*HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH

 Repr‚sentation en perpective des faces du dod‚caŠdre rhombique

 S = 14 ; F = 12 ; A = 24

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH*)

 USES Crt, E_Texte, U_Copie_1F, Math, U_Math;

// CONST Nsomm = 14;
 CONST Nface = 12;

 TYPE Ve3D = RECORD  x, y, z: Reel  END;
//      Tab_V = ARRAY[1..Nsomm] OF Ve3D;
      Face = RECORD  Sa, Sb, Sc: Byte;
                     Un: Ve3D; Dc: Reel  END;
      Tab_F = ARRAY[1..Nface] OF Face;
      Tab_C = ARRAY[1..Nface] OF Pixel;

 VAR Rcen: Z_32; Rsph: Reel;
     Vun1, Vun2, Vun3: Ve3D;
//     LstS: Tab_V;
     LstF: Tab_F;
     LstC: Tab_C;

(*HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH

 Utilitaires

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH*)

 FUNCTION Pvect(Wa, Wb: Ve3D): Ve3D;
   VAR p, q: Reel; W: Ve3D;
   BEGIN
     p:= Wa.y * Wb.z; q:= Wa.z * Wb.y; W.x:= p - q;
     p:= Wa.z * Wb.x; q:= Wa.x * Wb.z; W.y:= p - q;
     p:= Wa.x * Wb.y; q:= Wa.y * Wb.x; W.z:= p - q; Result:= W
   END;

 FUNCTION Diff2V(Wa, Wb: Ve3D): Ve3D;
   VAR W: Ve3D;
   BEGIN
     W.x:= Wa.x - Wb.x; W.y:= Wa.y - Wb.y;
     W.z:= Wa.z - Wb.z; Result:= W
   END;

 FUNCTION Vunit(Pc: Reel; V: Ve3D): Ve3D;
   VAR I1, N1, p, q, r, s: Reel; W: Ve3D;
   BEGIN
     p:= Sqr(V.x);     q:= Sqr(V.y);   r:= Sqr(V.z);   s:= p + q;
     N1:= Sqrt(r + s); IF (Pc<0) THEN I1:= 1 / N1 ELSE I1:= -1 / N1;
     W.x:= V.x * I1;   W.y:= V.y * I1; W.z:= V.z * I1; Result:= W
   END;

 FUNCTION Pscal(Wa, Wb: Ve3D): Reel;
   VAR p, q, r, s: Reel;
   BEGIN
     p:= Wa.x * Wb.x; q:= Wa.y * Wb.y; r:= Wa.z * Wb.z;
     s:= p + q;       Result:= r + s
   END;

(*HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH

 Caculs relatifs au polyŠdre

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH*)

 FUNCTION CombLin3V(C1, C2, C3: Z_32; V1, V2, V3: Ve3D): Ve3D;
   VAR W: Ve3D;
   BEGIN
     WITH W DO
       BEGIN
         x:= C1 * V1.x; IncR(x, C2 * V2.x); IncR(x, C3 * V3.x);
         y:= C1 * V1.y; IncR(y, C2 * V2.y); IncR(y, C3 * V3.y);
         z:= C1 * V1.z; IncR(z, C2 * V2.z); IncR(z, C3 * V3.z)
       END;
     Result:= W
   END;

 FUNCTION Identif_F(X1, Y1, Z1: Z_32): Byte;
   VAR j, Jf: Byte; Max, p, q, r, s: Reel; W: Ve3D;
   BEGIN
     W:= CombLin3V(X1, Y1, Z1 + 1, Vun1, Vun2, Vun3); Jf:= 0; Max:= 0;
     FOR j:= 1 TO Nface DO
       BEGIN
         p:= Pscal(LstF[j].Un, W); q:= p - LstF[j].Dc;
         r:= Abs(q);               s:= q + r;
         IF (s>Max) THEN BEGIN
                           Jf:= j; Max:= s
                         END
       END;
     Result:= Jf
   END;

 FUNCTION F_Polyedre(X1, Y1, Z1: Z_32): Reel;
   VAR j: Byte; p, q, r, s: Reel; W: Ve3D;
   BEGIN
     W:= CombLin3V(X1, Y1, Z1, Vun1, Vun2, Vun3);
     s:= 0;
     FOR j:= 1 TO Nface DO
       BEGIN
         p:= Pscal(LstF[j].Un, W); q:= p - LstF[j].Dc;
         r:= Abs(q);               IncR(s, q + r)
       END;
     Result:= s
   END;

 PROCEDURE Calc_Mat_Im2(La, Ha, Rc: Z_32; VAR Ma2: Tab_Pix);
   CONST Seuil = 1E-10; P000: Pixel = (0, 0, 0);
   VAR Iface: Byte;
       Xcen, Ximg, Xm, Ycen, Yimg, Ym, Zimg, Zmin: Z_32;
       u: Reel; Px: Pixel;
   BEGIN
     Xcen:= La DIV 2; Ycen:= Ha DIV 2; Zmin:= -2 * Rc;
     FOR Xm:= 0 TO (La - 1) DO
       BEGIN
         Ximg:= Xm - Xcen; We(10, 40, Xm, 6);
         FOR Ym:= 0 TO (Ha - 1) DO
           BEGIN
             Yimg:= Ym - Ycen; Zimg:= 0;
             REPEAT
               Dec(Zimg); u:= F_Polyedre(Ximg, Yimg, Zimg + Rcen)
             UNTIL ((u<Seuil) OR (Zimg=Zmin));
             IF (Zimg=Zmin) THEN Px:= P000
                            ELSE BEGIN
                                   Iface:= Identif_F(Ximg, Yimg,
                                                     Zimg + Rcen);
                                   Px:= LstC[Iface]
                                 END;
             Ma2[Xm,Ym]:= Px
           END
       END
   END;

(*HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH

 Calcul des couleurs

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH*)

 PROCEDURE Init_Lc(VAR L_f: Tab_F; VAR L_c: Tab_C);
   CONST m = 65280;
   VAR k: Byte; u: Reel; Px: Pixel;
   BEGIN
     FOR k:= 1 TO Nface DO
       BEGIN
         WITH LstF[k].Un DO
           BEGIN
             u:= Frac(29 * (1 + x)); Px[1]:= Round(Sqrt(m * u));
             u:= Frac(30 * (1 + y)); Px[2]:= Round(Sqrt(m * u));
             u:= Frac(31 * (1 + z)); Px[3]:= Round(Sqrt(m * u))
           END;
         L_c[k]:= Px
       END
   END;

(*HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH

 D‚termination des sommets, des faces et des arˆtes

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH*)

 PROCEDURE AffF(VAR L_F: Tab_F);
   CONST L1 = 2; L2 = L1 + 1; v = 11; w = 5;
   VAR k: Byte;
   BEGIN
     E(1012); Wt(1, L1, '    j');
     E(0015); Write('   Ja   Jb   Jc      ');
     E(0010); Write('Nx         Ny         Nz        ');
     E(0014); Write('Dcen');
     FOR k:= 1 TO Nface DO
       WITH L_f[k] DO
         BEGIN
           E(0012); We(1, k + L2, k, w);
           E(0015); Write(Sa:w, Sb:w, Sc:w);
           E(0010); Write(Un.x:v:w, Un.y:v:w, Un.z:v:w);
           E(0014); Write(Dc:v:w)
         END;
     A_; E(1015)
   END;

 CONST DegRad = Pi / 180;

 PROCEDURE CalcF(Rs_: Reel; VAR LstF: Tab_F);
   CONST L1 = 0.000; L2 = 1 - L1;
   VAR i, j, k: Z_08; h, Si2, Sij2, Sijk2: Byte; s: Reel;
   BEGIN
     h:= 0;
     FOR i:= -1 TO 1 DO
       BEGIN
         Si2:= Sqr(i);
         FOR j:= -1 TO 1 DO
           BEGIN
             Sij2:= Si2 + Sqr(j);
             FOR k:= -1 TO 1 DO
               BEGIN
                 Sijk2:= Sij2 + Sqr(k);
                 IF ((Sijk2=2) AND (h<Nface)) THEN
                   BEGIN
                     Inc(h); s:= Sqrt(Sijk2);
                     WITH LstF[h] DO BEGIN
                                       Sa:= 0; Sb:= 0; Sc:= 0;
                                       WITH Un DO BEGIN
                                                    x:= i / s; y:= j / s;
                                                    z:= k / s
                                                  END;
                                       Dc:= Rs_
                                     END
                   END
               END
           END
       END
   END;

(*HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH

 Calculs relatifs au nouveau repŠre

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH*)

 PROCEDURE CalcRcRs(La, Ha: Z_32; VAR Rc_: Z_32; VAR Rs_: Reel);
   BEGIN
     IF (La<Ha) THEN Rc_:= La DIV 2
                ELSE Rc_:= Ha DIV 2;
     Rs_:= 0.740 * Rc_
   END;

 CONST LambdaDeg = 20.0; PhiDeg = 35.0;

 PROCEDURE Calc_U0123(VAR U_1, U_2, U_3: Ve3D);
   CONST DegRad = Pi / 180;
   VAR Clam, Cphi, Slam, Sphi: Reel; W: Ve3D;
   BEGIN
     SinCos(LambdaDeg * DegRad, Slam, Clam);
     SinCos(PhiDeg * DegRad, Sphi, Cphi);
     W.x:= -Sphi;         W.y:= Cphi;          W.z:= 0;    U_1:= W;
     W.x:= - Slam * Cphi; W.y:= - Slam * Sphi; W.z:= Clam; U_2:= W;
     W.x:= Clam * Cphi;   W.y:= Clam * Sphi;   W.z:= Slam; U_3:= W
   END;

(*HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH

 Programme principal

HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH*)

 BEGIN
   Copie_F1;
   Calc_U0123(Vun1, Vun2, Vun3);
   CalcRcRs(Larg_Image, Haut_Image, Rcen, Rsph);
   CalcF(Rsph, LstF); AffF(LstF);
   Init_Lc(LstF, LstC);

   Calc_Mat_Im2(Larg_Image, Haut_Image, Rcen, Matrice_2);
   Creation_F2
 END

Des modifications mineures affectant le calcul des données caractéristiques des faces (Dc, Un) permettent de faire apparaître des déformations de l'objet, par exemple par une distribution aléatoire encadrée des distances au centre, ou de l'orientation des normales:

KDbgvuoG7fx_2-tab-L1=0.400-L3=0.400.png
KDbfvhPBuKx_2-poly%C3%A8dres.png

Dernière modification par Wiwaxia (01-04-2021 11:12:16)

Hors ligne

#10 01-04-2021 23:09:18

Wiwaxia
Membre
Lieu : Paris 75013
Inscription : 21-12-2017
Messages : 409

Re : La réduction des polyèdres convexes à l'intersection de demi-espaces

Bonsoir Bernard-maths

La meilleure définition des polyèdres convexes paraît être celle donnée par Mathworld, dans la référence déjà citée

In the usual definition, a polyhedron can be viewed as an intersection of half-spaces

J'en avais déjà pris connaissance dans les années 2000, à une époque où je m'intéressais aux polyèdres inscriptibles dans une sphère, et n'y avais pas donné suite à l'époque, car cette définition m'était d'abord apparue très théorique (faute d'avoir creusé le sujet), et peu susceptible de déboucher sur le calcul des arêtes et des sommets.
C'est l'introduction des valeurs absolues que tu as présentée en décembre dernier qui a permis d'entrevoir tout le parti que l'on pouvait tirer de cette définition.

Par ailleurs, je m'intéressais à l'époque à l'évolution d'un nuage de (N) points en répulsion mutuelle, assujettis ou non à rester à distance fixe de l'origine; la donnée initiale était par conséquent l'ensemble des positions des sommets, de laquelle on peut déduire l'identification et le dénombrement des faces, puis des arêtes.

Tout polyèdre convexe (1) se caractérise ainsi d'une manière exhaustive par trois ensembles de données interdépendantes:
a) la matrice des (Ns) vecteurs unitaires associés aux positions des sommets;
b) le tableau des (Nf) faces dont chacune est caractérisée par
- la liste des sommets présents, dont le nombre est au moins égal à trois,
- les composantes du vecteur unitaire normal définissant l'orientation de chaque face,
- la distance qui la sépare de l'origine du repère (le centre de la sphère circonscrite, si celle-ci existe);
c) le tableau des (Na) arêtes, dont chacune est caractérisée par la donnée de deux couples d'indices:
- celui de la paire de sommets délimitant le segment,
- celui des faces adjacentes dont l'arête est à l'intersection;
de ces deux couples on déduit immédiatement la longueur de l'arête, et l'angle dièdre déterminé par les deux faces.

Ce dernier tableau constitue le cœur de l'organisation interne du polyèdre; les données qu"il contient sont invariantes dans toute rotation ou translation imposée à l'objet.

La programmation des deux premières étapes a déjà été présentée sur plusieurs exemples simples (voir les messages précédents).

La détermination des arêtes s'impose dans le cas de la représentation d'un polyèdre en transparence; c'est un autre sujet qu'il faudrait aborder, mais qui ne présente pas de difficulté majeure.

D'une manière plus systématique, la détermination des éléments du polyèdre commence par celle des sommets selon l'ordre:

sommets ---> faces ---> arêtes ;

on pourrait effectivement commencer par les faces, comme dans le cas du dodécaèdre précédemment décrit: encore une nouvelle démarche calculatoire à explorer.

La rotation de l'objet implique celle des sommets et des faces; il pourrait être pratique d'envisager une "supermatrice" à (Ns + Nf) colonnes et rassemblant tous les vecteurs unitaires associes aux sommets et aux faces: une sorte d'"oursin", rassemblant finalement les positions des sommets du polyèdre et celles de son dual.

(1): j'aurais dû préciser: circonscriptible à une sphère.

Dernière modification par Wiwaxia (02-04-2021 10:27:50)

Hors ligne

#11 02-04-2021 07:38:38

Wiwaxia
Membre
Lieu : Paris 75013
Inscription : 21-12-2017
Messages : 409

Re : La réduction des polyèdres convexes à l'intersection de demi-espaces

Bernard-maths a écrit :

... Qu’en penser ? Ces 2 approches sous-entendent que l’objet est de dimensions finies, autrement dit, qu’on peut le mettre dans une boite (un cube), ou un carré pour un polygone. D’après cela, il n’existe donc pas de polyèdre « infini », ou « ouvert ? » … bien qu’on puisse les envisager !

Par exemple, prenons un vase à base carré, les 4 bords étant des trapèzes (isocèles) allant en s’élargissant … on a déjà 5 faces, on peut en ajouter une sixième en « fermant » le haut en carré. Ce polyèdre est bien un polyèdre donc ! Mais imaginons que les 4 côtés soient « infinis », qu’ils se prolongent indéfiniment. Il n’y a donc que 5 faces, et il est ouvert … mais il n'a que 4 sommets et 8 arêtes ? ...

Il est exclu d'envisager des sommets rejetés à l'infini, ou des arêtes ou des faces de dimensions illimitées:
- le monoèdre - c'est à dire le plan (S = 0, F = 1, A = 0),
- le dièdre (S = 0, F = 2, A = 1),
- le trièdre (S = 1, F = 3, A = 3)
ne sont pas des polyèdres, la relation d'Euler S + F - A = 2 n'est pas vérifiée.

Bernard-maths a écrit :

... De plus Wikipedia note au passage qu’il s’agit d’un « solide », et non seulement d’un « volume » … donc un objet « plein » !
Or nous ne percevons que l’aspect extérieur, surfacique … et certaines représentations « artistiques » ne font voir que les arêtes (grossies) ...

Le polyèdre est une portion de l'espace, forcément délimitée par une frontière bien définie - l'ensemble des faces.
Si l'origine (O) est située à l'intérieur du polyèdre convexe, la somme des hauteurs menées depuis un point quelconque (M) permet de caractériser le domaine interne de l'objet (fermé par ses diverses faces) par l'équation:

S(M, hi) - S(O, h'i) = 0 .

Bernard-maths a écrit :

... la donnée des sommets ne détermine pas le polyèdre ...

Elle suffit s'il est convexe.

Dernière modification par Wiwaxia (02-04-2021 10:29:59)

Hors ligne

#12 02-04-2021 08:32:08

Bernard-maths
Membre
Lieu : 34790 Grabels
Inscription : 18-12-2020
Messages : 1 316

Re : La réduction des polyèdres convexes à l'intersection de demi-espaces

Bonjour à tous ?

Wiwaxia, je vois que tu es réveillé ! Evidemment, si on veut que la relation d'Euler soit satisfaite, alors ce n'est pas un polyèdre (honnête ?), mais un machin-èdre. Mais je ne suis pas sur que la donnée des sommets définisse un seul polyèdre ... Il me semble qu'il faut ajouter des arêtes (peut-être pas toutes ?).

Pour ce qui est des demi-espaces, la recherche d'une équation demande (en plus d'une équation par face) qu'on regarde les signes de part et d'autre pour écrire une équation du demi-espace utile, etc ... Si j'ai "basculé" vers les tranches d'espace, c'est qu'il m'a paru un peu plus simple de chercher l'équation d'un plan parallèle, puis d'additionner 2 distances, avec des valeurs absolues ! C'est pour ça que je les aime, ah si on pouvait en faire des plats à déguster ;) !!!

Toujours est-il que nous naviguons sur des voies parallèles et complémentaires (va dire ça dans un e.v. ?), toi en traçant des polyèdres, et moi en en cherchant des équations ...

Mais on continue ! Je vais ci-après donner une équation de mon machin-èdre !

Bernard-maths

Dernière modification par Bernard-maths (02-04-2021 09:16:20)


Ma philosophie est immuable : l'immobilisme tue ...
Les Anciens ont trouvé le plus facile ... il nous reste le plus dur !

Hors ligne

#13 02-04-2021 08:54:29

Bernard-maths
Membre
Lieu : 34790 Grabels
Inscription : 18-12-2020
Messages : 1 316

Re : La réduction des polyèdres convexes à l'intersection de demi-espaces

Bonjour à ceux qui sont curieux de mon machin-èdre !

Bien que cet objet soit soit une chimère de polyèdre, il existe ! Regardez le bien, ses sommets sont ceux d'un cube ...
Mais si il n'en possède que 2 faces, celles du haut ABCD, et du bas EFGH, les 4 autres faces sont dans des plans diagonaux du cube.

https://cjoint.com/c/KDch1g7g5iG

KDch1g7g5iG_Machin-%C3%A8dre-01-%C3%A9quation.png

Nous voyons sur cette figure que :

1) les faces ABCD et EFGH sont dans les plans d'équations : z = a et z = -a (avec a = 5 ici).
2) que les faces ADGF et BCHE sont dans les plans diagonaux d'équations : x + z = 0 et x - z = 0. 
3) que les faces ABGH et CDHG sont dans les plans diagonaux d'équations : y + z = 0 et y - z = 0.
4) enfin que l'ensemble de la figure est contenue dans le prisme (infini) vertical entourant les 2 faces haute et basse ...

Nous voyons alors que les 6 faces sont contenues dans ce "tuyau carré". Si nous connaissons son équation, alors nous pourrons trouver une équation du machin-èdre !

Pour détailler, ce prisme est l'intersection de 2 tranches d'espace : la tranche des points compris entre les 2 plans parallèles d'équations : x = -a et x = a, et les 2 autres plans parallèles d'équations : y = -a et y = a.

Dans chaque tranche d'espace, les points sont caractérisés par le fait que la somme des 2 distances aux 2 plans est minimale, est égale à 2a = distance des 2 plans ... on a alors  : Abs(x+a) + Abs(x-a) = 2a et Abs(y+a) + Abs(y-a) = 2a pour les 2 tranches, ce qui donne finalement pour le prisme : Abs(x+a) + Abs(x-a) + Abs(y+a) + Abs(y-a) = 4a !!!

Si on veut qu'un point du plan soit sur le machin-èdre, il faut (et il suffit) qu'il soit sur l'un des 6 plans, ET qu'il soit dans le prisme ...

Dans le prisme, on vu, et pour les 6 plans : (z-a) (z+a) (x+z) (x-z) (y+z) (y-z) = 0 !

On peut alors regrouper les 2 équations de ce système en utilisant des valeurs absolues :

ABS( Abs(x+a) + Abs(x-a) + Abs(y+a) + Abs(y-a) - 4a) + ABS((z-a) (z+a) (x+z) (x-z) (y+z) (y-z)) = 0.

Bernard-maths

Dernière modification par Bernard-maths (02-04-2021 09:35:05)


Ma philosophie est immuable : l'immobilisme tue ...
Les Anciens ont trouvé le plus facile ... il nous reste le plus dur !

Hors ligne

#14 02-04-2021 17:23:44

Bernard-maths
Membre
Lieu : 34790 Grabels
Inscription : 18-12-2020
Messages : 1 316

Re : La réduction des polyèdres convexes à l'intersection de demi-espaces

Bonsoir !

Wiwaxia, je vois que tu es "devenu" raisonnable sur le fait que la donnée des sommets ne suffit pas à définir un polyèdre !

Si tu avais un léger doute, tu as rectifié en disant SI pour un polyèdre convexe ... Je suis en train de chercher un peu, et j'ai trouvé (cjoint suivant) le cas d'un polyèdre, dont on connaît 4 faces, et à compléter par 2 autres faces ... on a 2 possibilités, selon l'arête qu'on décide de choisir ... Et l'un est convexe, l'autre non ! Mais si on veut le convexe, alors y'a pas le choix ...

https://cjoint.com/doc/21_04/KDcqwnnalC … -04-02.ggb

Quelle référence as-tu pour dire : sauf convexe ? Merci !

Bernard-maths


Ma philosophie est immuable : l'immobilisme tue ...
Les Anciens ont trouvé le plus facile ... il nous reste le plus dur !

Hors ligne

#15 03-04-2021 08:14:34

Wiwaxia
Membre
Lieu : Paris 75013
Inscription : 21-12-2017
Messages : 409

Re : La réduction des polyèdres convexes à l'intersection de demi-espaces

Bonjour Bernard-maths,

Bernard-maths a écrit :

... Wiwaxia, je vois que tu es "devenu" raisonnable sur le fait que la donnée des sommets ne suffit pas à définir un polyèdre !

Si tu avais un léger doute, tu as rectifié en disant SI pour un polyèdre convexe ... Je suis en train de chercher un peu, et j'ai trouvé (cjoint suivant) le cas d'un polyèdre, dont on connaît 4 faces, et à compléter par 2 autres faces ... on a 2 possibilités, selon l'arête qu'on décide de choisir ... Et l'un est convexe, l'autre non ! Mais si on veut le convexe, alors y'a pas le choix ...

Quelle référence as-tu pour dire : sauf convexe ? ...

Je me suis effectivement laissé aller à une généralisation hâtive en ce qui concerne l'intervention systématique des vecteurs unitaires, qui ne concerne que les systèmes de points co-sphériques; il n'en reste pas moins que les faces (et donc les arêtes) de tout polyèdre convexe sont entièrement déterminées par la donnée des positions des sommets.
Cela tient au procédé de caractérisation des faces, qui revient à considérer le polyèdre comme l'enveloppe convexe du nuage de points; l'algorithme en a été donné au message #2:

Wiwaxia a écrit :

Il faut ensuite inventorier les diverses faces, lesquelles se caractérisent par:
# les indices respectifs (Ja, Jb, Jc) de leurs 3 sommets, donnés dans l'ordre croissant,
# les composantes du vecteur unitaire normal (Un), et
# la distance (Dc) les séparant de l'origine (O) du repère, et dans le cas présent centre de la sphère circonscrite au polyèdre.
Le critère de reconnaissance d'une face consiste en ceci que pour un triplet (i, j, k) donné, tous les autres points sont situés, comme l'origine, du même côté par rapport au plan (Mi, Mj, Mk);
par conséquent les produits mixtes (MiMj, MiMk, MiMl) et (MiMj, MiMk, MiO) sont de même signe pour tout (l) différent de (i, j) et (k).
Il n'y a ici que des faces triangulaires; la présence de faces à plus de 3 sommets n'introduit pas de difficulté insurmontable.

Le contre-exemple que tu donnes contrevient précisément à la règle de sélection décrite:
KDdgxGJaQpx_2-poly%C3%A8dres-ABCDE.png
Le triangle (BCE) n'est pas une face, parce que son plan sépare les deux autres points (A) et (D); les produits mixtes

(BC, BE, BA), (BC, BE, BD)

sont de signes contraires - idem pour le triangle (BDE).

Dernière modification par Wiwaxia (03-04-2021 08:20:43)

Hors ligne

#16 03-04-2021 08:27:24

Bernard-maths
Membre
Lieu : 34790 Grabels
Inscription : 18-12-2020
Messages : 1 316

Re : La réduction des polyèdres convexes à l'intersection de demi-espaces

Bonjour !

Pourtant on compte 6 Faces, 5 Sommets et 9 Arêtes, ce qui donne : F + S = A + 2, comme dirait ... Euler ?

Donc ce sont des polyèdres, mais le "bleu" n'est pas convexe, on est d'accord.

Le "coup de l'enveloppe convexe" est pas mal, oui ! Je n'arrive effectivement pas à produire 2 polyèdres convexes différents ...

Sinon, on a en général pas mal (?) de polyèdres non convexes différents pour des sommets donnés.

Joyeuses Pâques, et bon reconfinement !!!

Bernard-maths


Ma philosophie est immuable : l'immobilisme tue ...
Les Anciens ont trouvé le plus facile ... il nous reste le plus dur !

Hors ligne

#17 03-04-2021 10:10:00

Wiwaxia
Membre
Lieu : Paris 75013
Inscription : 21-12-2017
Messages : 409

Re : La réduction des polyèdres convexes à l'intersection de demi-espaces

Bernard-maths a écrit :

Pourtant on compte 6 Faces, 5 Sommets et 9 Arêtes, ce qui donne : F + S = A + 2, comme dirait ... Euler ?

Là n'est pas la question ! Tout polyèdre résultant de la partition d'une surface fermée vérifie la relation d'Euler-Poincaré

S + F - A = X ,

dont la caractéristique (X) dépend du genre de la surface considérée;
# X vaut 2 dans le cas d'une surface de genre nul, homéomorphe à la sphère et dépourvue de trou;
# X est nul dans le cas d'une surface de genre (1) homéomorphe au tore et présentant un trou, (-2) lorsqu'il y en a deux, etc.
Je laisse de côté les cas pathologiques dont l'imagination des mathématiciens se montre particulièrement friande.
http://villemin.gerard.free.fr/Wwwgvmm/ … lEuler.htm
https://fr.wikipedia.org/wiki/Caract%C3 … _d%27Euler
https://mathcurve.com/surfaces/eulerpoi … care.shtml

Bernard-maths a écrit :

... Sinon, on a en général pas mal (?) de polyèdres non convexes différents pour des sommets donnés ...

En insérant un point supplémentaire à l'intérieur d'un polyèdre convexe à (S) sommets et (F) faces, on obtient (F) polyèdres concaves à (S + 1) sommets.

Exemple de surface algébrique (mais si !) à 5 trous:

KDdjeicFJXx_Surface-de-genre-5.png

Bonne fête de Pâques à tous !

Hors ligne

#18 03-04-2021 16:44:54

Bernard-maths
Membre
Lieu : 34790 Grabels
Inscription : 18-12-2020
Messages : 1 316

Re : La réduction des polyèdres convexes à l'intersection de demi-espaces

Hello !

Très joli, mais combien de trous ? 4 ou ... 5 ... ou 6 ?

Et de "pseudo sommets" ?

Bof ! Un aquarium accidenté ... :) C'est Valdia qui serait contente ?

... mais, où sont passés les demi-espaces (plans) !?

B-m

Dernière modification par Bernard-maths (03-04-2021 16:47:45)


Ma philosophie est immuable : l'immobilisme tue ...
Les Anciens ont trouvé le plus facile ... il nous reste le plus dur !

Hors ligne

#19 04-04-2021 20:23:15

Wiwaxia
Membre
Lieu : Paris 75013
Inscription : 21-12-2017
Messages : 409

Re : La réduction des polyèdres convexes à l'intersection de demi-espaces

Bonsoir,

Bernard-maths a écrit :

... combien de trous ? 4 ou ... 5 ... ou 6 ?

C'était involontairement provocateur, mais je n'avais pas retrouvé de document plus simple dans le capharnaüm de mes fichiers.
Il suffit de détordre l'objet pour s'apercevoir que la surface fermée finale englobe les 12 arêtes rectilignes d'un cube, et présente 5 trous comme les précédentes:

KDesdcJ3oLx_Cube-torsad%C3%A9.png

Il s'agit d'une famille de surfaces algébriques de degré 28, de genre fixe (5) et vérifiant l'équation:

(x+2*a*z*y)^14+(y-2*a*z*x)^14+z^14-b*((x+2*a*z*y)^12+(y-2*a*z*x)^12+z^12)+c*b^14

avec b = 0.74 et c = 0.44 .

Inscrire lisiblement un polyèdre dans la surface la plus simple (a = 0) n'est pas facile.

Il y a une solution (S, F, A) = (32, 44, 84) conduisant à la caractéristique d'Euler

X = S + F - A = -8

conforme au genre de la surface: X = 2(1 - g) = 2(1 - 5) .

Hors ligne

#20 04-04-2021 21:00:09

Bernard-maths
Membre
Lieu : 34790 Grabels
Inscription : 18-12-2020
Messages : 1 316

Re : La réduction des polyèdres convexes à l'intersection de demi-espaces

Bonsoir !

Moi je dirai 6 trous ! Mais si c'est un aquarium, 1 seul trou ...

Pour l'enveloppe convexe ... j'ai pris un nuage de 10 points déterminés au hasard, et j'ai tracé un polyèdre convexe les contenant : 8 en sommets, 2 intérieurs. J'ai effacé les 2 intérieurs, et j'ai recommencé un polyèdre convexe ayant les 8 sommets : c'est le même !

Pour la suite, je te propose un tétraèdre régulier ... tu le fais en demi-espaces, et moi en tranches d'espace.

Je propose A(3,3,3), B(3,-3,-3), C(-3,3,-3) et D(-3,-3,3) ... OK ?

Bonne soirée, Bernard-maths

Dernière modification par Bernard-maths (04-04-2021 21:00:59)


Ma philosophie est immuable : l'immobilisme tue ...
Les Anciens ont trouvé le plus facile ... il nous reste le plus dur !

Hors ligne

#21 04-04-2021 21:25:13

Roro
Membre expert
Inscription : 07-10-2007
Messages : 1 552

Re : La réduction des polyèdres convexes à l'intersection de demi-espaces

Bonsoir,

Il y a de jolis dessins ici...

Bernard-maths a écrit :

Moi je dirai 6 trous ! Mais si c'est un aquarium, 1 seul trou ...

Mais comment comptez-vous les "trous" ???

Pour un aquarium, j'en compte 0. Et pour la figure du post précédent, j'en compte 5...

Roro.

Dernière modification par Roro (04-04-2021 21:34:20)

Hors ligne

#22 04-04-2021 21:34:02

Bernard-maths
Membre
Lieu : 34790 Grabels
Inscription : 18-12-2020
Messages : 1 316

Re : La réduction des polyèdres convexes à l'intersection de demi-espaces

Bonsoir Roro !

Dans cette figure tordue, et ramenée à un cube (!?) il n'y a que les arêtes. Donc les 6 faces absentes font 6 trous (pour moi :)).
...
Mais si c'est un aquarium, il y a 5 trous bouchés par des vitres ... :)

Bonne soirée ! B-m


Ma philosophie est immuable : l'immobilisme tue ...
Les Anciens ont trouvé le plus facile ... il nous reste le plus dur !

Hors ligne

#23 04-04-2021 21:35:52

Roro
Membre expert
Inscription : 07-10-2007
Messages : 1 552

Re : La réduction des polyèdres convexes à l'intersection de demi-espaces

Re-bonsoir,

Une idée sur le calcul du nombre de trous : ici

Pour le cas simple de l'aquarium (avec des bords "épais" sinon je ne sais pas ce que signifie "trou"), on peut le déformer continument en un morceau de plan. D'ailleurs, s'il y avait un trou, on ne pourrait pas mettre de l'eau dedans !

Roro.

Dernière modification par Roro (04-04-2021 21:46:26)

Hors ligne

#24 05-04-2021 08:09:51

Wiwaxia
Membre
Lieu : Paris 75013
Inscription : 21-12-2017
Messages : 409

Re : La réduction des polyèdres convexes à l'intersection de demi-espaces

Bonjour,

La déformation de la surface apparentée au cube (a = 0) en tronc de pyramide permet de vérifier la présence de 5 trous dans la surface fermée, conformément au schéma mis en lien par Roro.

Il s'agit bien d'une surface fermée de genre égal à 5:

KDfg64VYNFx_4-cubes.png

Hors ligne

#25 05-04-2021 08:59:27

Wiwaxia
Membre
Lieu : Paris 75013
Inscription : 21-12-2017
Messages : 409

Re : La réduction des polyèdres convexes à l'intersection de demi-espaces

Un polyèdre inscriptible dans une surface du genre précédemment décrit s'obtient en 3 étapes de duplication, accompagnées du raccordement des faces triangulaires mutuellement placées en regard.
En partant d'un tétraèdre (S0, F0, A0) = (4, 4, 6), la jonction des sommets de deux triangles par des segments parallèles:
a) double le nombre de sommets du fait de la reproduction de la structure précédente: Sn = 2 * Sn - 1 ;
b) introduit une face supplémentaire pour toute paire de triangles associés en raison du remplacement des deux faces concernées par 3 faces quadrangulaires (trapèzes, éventuellement rectangles): Fn = (2 * Fn - 1) + 2n - 1 ;
c) fait apparaître 3 arêtes supplémentaires pour chaque paire de triangles, d'où: An = 2 * An - 1 3 3 * 2n - 1 .
On voit ainsi apparaître:

(S1, F1, A1, X1) = (8, 9, 15, 2) - polyèdre ordinaire, de genre nul;
(S2, F2, A2, X2) = (16, 20, 36, 0) - polyèdre torique de genre 1;
(S3, F3, A3, X3) = (32, 44, 84, -8) - présentant la structure d'un cube.

KDfix2fRZKx_4-poly%C3%A8dres.png

PS: Erreur rectifiée.

Dernière modification par Wiwaxia (05-04-2021 09:28:08)

Hors ligne

Réponse rapide

Veuillez composer votre message et l'envoyer
Nom (obligatoire)

E-mail (obligatoire)

Message (obligatoire)

Programme anti-spam : Afin de lutter contre le spam, nous vous demandons de bien vouloir répondre à la question suivante. Après inscription sur le site, vous n'aurez plus à répondre à ces questions.

Quel est le résultat de l'opération suivante (donner le résultat en chiffres)?
soixante dix-sept plus quatre-vingt sept
Système anti-bot

Faites glisser le curseur de gauche à droite pour activer le bouton de confirmation.

Attention : Vous devez activer Javascript dans votre navigateur pour utiliser le système anti-bot.

Pied de page des forums