Aller au contenu

Arbre quaternaire pour image

Deux exercices totalement indépendants

  • le premier est plus difficile,
  • le second est plus accessible.

Définition

Un arbre quaternaire est une structure qui ressemble aux arbres binaires, mais au lieu de deux sous-arbres s'il est non terminal, c'est quatre sous-arbres.

🧭 Quatre directions

Dans cet exercice, on travaille avec une image carrée dont la taille du côté est une puissance de deux, en pixels.

  • Soit c'est un pixel seul, élément terminal (ou feuille).
  • Soit on peut couper en quatre carreaux, comme pour une fenêtre, on utilisera les quatre directions :
    • NE (nord-est),
    • NO (nord-ouest),
    • SO (sud-ouest),
    • SE (sud-est).

Des images en pixel art

  • Ces images sont des carrés de 8 pixels par 8 pixels.
  • 8 est une puissance de deux : \(8 = 2^3\).
  • Il y a, ici, trois couleurs et des pixels transparents.
  • Vous pouvez passer la souris sur chaque case pour avoir des informations.

Format matriciel

    • une palette de couleurs : chat_palette = [None, (242, 214, 146), (239, 185, 68), (193, 145, 40)]
      • ici, l'indice 0 est associé à un pixel transparent,
      • ici, l'indice 1 est associé à une couleur RVB (242, 214, 146)
      • ...
    • une matrice de couleurs : chat_matrice

    Cette image peut être stockée via :

    🐍 Script Python
    chat_matrice = [
    [0, 0, 0, 1, 0, 0, 0, 1, ],
    [0, 0, 0, 2, 1, 1, 1, 2, ],
    [1, 0, 0, 2, 0, 2, 0, 2, ],
    [2, 0, 0, 2, 2, 3, 2, 2, ],
    [2, 1, 1, 2, 2, 2, 2, 0, ],
    [2, 2, 2, 2, 2, 2, 2, 0, ],
    [2, 0, 2, 0, 2, 0, 2, 0, ],
    [3, 0, 3, 0, 3, 0, 3, 0, ],
]

Nouvelle modélisation

Cet exercice n'utilise pas la classe Noeud pour construire un arbre.

Cet exercice utilise :

  • Pour désigner un nœud non terminal : un tuple (NE, NO, SO, SE) :
    • pointant vers quatre sous-arbres : au NE, au NO, au SO et au SE.
  • Pour désigner un pixel (élément terminal) :
    • ou bien un tuple (r, v, b) : la couleur de fond du pixel,
    • ou bien None : pour indiquer un pixel transparent.

Exercice 1

Coder une fonction vers_quad qui prend en paramètres une image sous format matriciel image_mat et une palette de couleur sous forme d'une liste de couleurs RVB (avec éventuellement None pour désigner la transparence) et qui renvoie image_quad : l'image sous forme d'un arbre quaternaire.

👍 On garantit que :

  • l'image fournie est carrée,
  • la taille de son côté est une puissance de deux,
  • les indices sont tous valides pour la palette,
  • la palette est une liste qui contient ou bien None et/ou des couleurs au format RVB,
  • tout est prévu pour fonctionner sans avoir besoin de vérifier l'entrée utilisateur.

👍 Vous disposez du matériel :

  • la fonction dessine pour visualiser votre résultat avant de valider.
    • La fonction dessine prend en paramètre une image au format d'arbre quaternaire uniquement !
  • L'image du chat, accessible sous format matriciel avec les variables chat_palette et chat_matrice.
  • Les images de la chauve-souris (avec chauve_souris_...), mais aussi hippocampe_...
  • Créez vous-même des images matricielles... Tant qu'elles sont carrées avec des côtés qui sont des puissances de deux. Avec une palette au choix.
###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : ∞/∞
.128013]x,59/fq78r;nb _o=ylaepcwgu)vd*4613k×RméhtsP(S0+2j[i:U050E0w0Q0v0!0u0R0p0y0u0v0R0R0s010Q0!0x010406050R0B0N0N0v0l0t040U0r0u0B0`0r0n0p020v0N0x0m0p0M0w140l0i0B0w0R050g111315170 0x04051C1v1F0g1C0 0E0!0D0/0;0?0^0P0!0A0P0u1T0P0Q0}050*0o0u0w1O0=0@011S1U1W1U0Q1$1(1!0Q0l1D0Q0P1*1Q010h0,0w0n1i0w010/1a0R0x0v0n0^0X1!2a2c1~1,211(240N26040a0p0S0l0r0x0r0R0!1d1f0(280l0l0w0y2A1v2h0n1D0g1|2M1_1{1`1#0E2j0^1W0n232x1!1L1N0:1+2W0!2Y0n0r2$1!0x2F1D2K2M2@102b1f2(1 2-0l140u0}0p0I2J2{0~2`2i2}1,2 31330X362c382K2V013d0v32040p0J3h2L0 3k3b0^3n3p0p0G3t3j2{3l3z330e3D3v3F3x3m0r303o330H3K392|1P3c3P3e3q0j3U3w3X3y3Z3R3q0k3%3M3)3O3Q3A0f3/3a3;3H040I0V3_3W2)3=3!0I351w373L3`423|0I3g473i49412~3+3p0I3s4f3u3V3G4k0}0I3C4o3E4a4j3?4t3J4w4h4r4A3}3T4D4q3N4c3$4J3(4b4s3}3.4O3:4Q4G0I3^4U4y3Y4G0X3 4!4i4$3!0X462_1I2=1v2$2P0E1{2U3N0y2.2p0%1M1D2;0w2?373D054}0(554#0^0K0}0(0h574P1 0z335i4V2~0h0}0D0w0l0R0q1r0v0E5n5c010|040T5A4+3y0}0!140A0w0q141_0!0y0w5G3l5D0d3D0p4K3{5J5L5N2b1(1=5T4w5!425D0C0#3K0p5@5Z5j1,0R2f04011n0n0D0r0!1)0;0p5s5u0!1e0p2C0u005K0v5M0p0R0r0B0.0h3Z1)0E00150o2F0p5x0Q5t240!2F013K065^5_5o1,5e045g5U3N5l3q6N3{5q040v0B0c0,0!0+2F6R5/0}5F5-5`5I040!6$1 5W5Y5.2~0}0Y6/1,6;4w6H5B0n0}0n6`0^5:5=4*3l6P6G6G73010R0E0}017h403l7e337a5@6062640p6e0w0c1_0+0Q6c656f5%6j6l6n6p6c6s0l6u1)6x6z6!5,2@4E3N7l3q7n7z0x0B0!0.1(0p2w2+7y0T0!0d0p0Y0C7z7s7B6h6q003P1T2+7P486?5{7f7U7n0)7:0*0,7#0y150l0O1)0n0L72777S807V0p7h6D4D8j7~5d5J5h6}8p3m716=6+010r0}0s0s8x6I0^0N0!4t7c5D767Q8j7b8y6K2F0Q0B0l8f2@6~5H8v6-5%0q5)0)6y8K0}0Z8E6 5$7?5O0v5Q5S8+048-6*8F8!6.8|5B5D0b8{2_8y70046_908Z928.9b0}0b5?7V8u6K0w0-7|3i8u8L9h8O8Y3G0}0N9d3l8A048D8t968w9C8}9z0g0g9x3N8H0}4e8N9s9t3N8R0)8U8W379R3;5D6)9P9Q5^8u976V6X1W7O8_9#569D6-8_5X6}8P8}97998X8u9z0W9K5#049w9a5V0}9^9~9=a5958}5:a9489%9`8/6U6W6Y9.a63N9!7c978 ad91a85Yaj8Z9|9@ay9(ab8_0Cag4gaiaE9{0}9+an6B9n2L9p6(as5Ja242a0aX6@a4aC9Fak9}9;aeax9_aLakaca+aw04aH9rai9)aNam9-aQ9/aV9?a(8ZaZb39ua$ap9Za-aaaM98a!1,b5bca:a%biaA9vaGaI3u9%aTa@6Eaz3l9T8T8Vbf6,aOa~6#b96%5E7c9M044)av9e04bp6Q8ybJbLa=bNbP9Y4b0o0}2mb0bFa#6g5M8=8@aR5bbN0C0C3U0g59541G4=0g4@1v0Q4_b}2S2N0v1%b^b{511Bb.3l2F0N0q0h0v0K5N0P0J0}1n1p1r1t0p8M561I381C0$2Y675t2y6b0v5s0y0p0B2|4~0pce2H7_0R0Ocp1G382$3l1.1V1X1Zc93N2l23250}2r0U0y0l0{7y0S0t1|1e5753b.2^56b@cX3;6K6Mb%1,79as6T685v5x5zc~74aUd78~8$5Pc*8^da6|blb7b)5(3o8)b-bs5;a_8u5|7g7p63650vcx696b6d7=6i6k6mcI7G6r6t6v7M8V7O8m7Q6Fa/8Zc|0w8sbM785mda0n6TbC6Za dgd9dX4LaWd*bObA8!a*9o8ydh9Xa{049Wd@a,a@cq4g8u799ida7T8l7j8h7m7ndv7r7t7v0l7x7:6edk7DdG6o307@dK7L0B8?7Nd)7Qds8i7V0(7X7Z7s1)7%0n7)7+7-7/dCel6r7_0A7{e93;7T8j832C850u87898b0p8dd}4p8yeU7Ve88n9i8Q8rd;97e)bQ9G8B9Bdi9L8I3}8_e1bq9Q9j0}8S9Ve?8:b*8(5+8_94d`9=dkb+dedod^8,b1aubUa70493b1d?aSfmfsd;9ce/7nf5049l0Rfld f20~braFb63N9ze|fgbde^bX1 9H9JfN3;bJ9Oahf49=cC6y8U1ufYaY8Bfz8,9:d~5BbSbkfRf@e 4/fqaq0}a^f-6:d+f~fZe bTf?bVd;f^d/g1e}babHdabJf}g9frbW8ugcd,gggef`bNf=fw8}gjf_3ifU1,gygd9gfB8OfDf7bzg23cbZ048T0x1(b$9$a`9=d%aogqbGgvc`4bd.gff.04a1gL6,a;gA9 0}0Ff96Lfpglf d:g,d=d;bhgtb7g.2LgB0^9zg=g|970Efvg#g3g{g(a#h2hc6{g0a_fL8}6Keof:ghgYa#1Lgzh3d{haaGg~6P2+g?f)0wf+hle:d b;4DdR5@gI9UgKhf3ca|9,d(bEhshjhrg542gph!hdgnbRg7hve_6 gNb#d/g!d{fidd5RfHa?b:b=c_b_c54@0 b{0)0+0-04.

Exercice 2

Coder une fonction quart_tour qui prend en paramètre une image (sous la forme d'un arbre quaternaire) et qui renvoie une nouvelle image (aussi sous forme d'un arbre quaternaire) obtenue par rotation d'un quart de tour dans le sens direct (sens antihoraire).

Vous pourrez utiliser la fonction dessine pour visualiser votre résultat avant de valider.

Vous pourrez remplacer chat par chauve_souris ou par hippocampe pour jouer...

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : ∞/∞
.339.128013x,59/f.q78rnb N_oO=ylaepcwgu)vd4613kRméhtsP(S0L2-i:E050G0y0Q0x0Z0w0R0p0A0w0x0R0R0u010Q0Z0z010406050R0D0N0N0x0m0v040U0s0w0D0_0s0n050g101214160~0z04051m1f1p0g1m0~0G0Z0F0.0:0=0@0P0Z0C0P0w1D0P0Q0|050)0o0w0y1y0;0?011C1E1G1E0Q1M1O1K0Q0m1n0Q0P1Q1A010h0+0y0n0x0N0y010.190R0z0x0n0@0X1K1{1}1+1S1.1O1;1?0|0b0p0S0m0s0z0s0R0Z1c0n0p0%1_0m0m0y0A2k1f220n1n0g1)2x1$1(1%1L0G240@1G0n1:2h1K1v1x0/1R2H0Z2J0n0s2N1K0z2q1n2v2x2#0 1|2l2P1,2U0m130w0|0p0J2u2)0}2(232+1S2-2/2;0X2@1}2_2v2G012~0x2:040p0K322w0~352|0@383a0p0H3e342)363k2;0e3o3g3q3i370s2.392;0I3v2`2*1z2}3A2 3b0k3F3h3I3j3K3C3b0l3O3x3Q3z3B3l0f3W2{3Y3s040J0V3%3H2Q3Z3L0J2?1g2^3w3(3:3*0J313^333`3/2,3S3a0J3d403f3G3r450|0J3n493p3{443!4e3u4h424c4l3+3E4o4b3y3}3N4h1q2Z1f2N2A0G1(2F3y0A2V1@1n4D1o4B2%4z4J0%2!3X3:0L0|0%0h3o4v3Y0B2;4#3P3|0h0|0j0D140Q0r0Q0s0D0m4*4V1,0{040T4{4j2}0|0Z130C0y0r4/0x0G51431S4~0E0!3.364(3b0p5n5d360R0G0|015u5j3y5r2;5n0p0M1:0F0s0Z1P0w00550x570p4@4_0n0O1P0G000D2l5a0m0Q2m1P5O0m2m1}0-1O0p0R1:0-1}0_0P3A0*2q5w3Y5y5m5n0W0y0-0%0D0c0p5K570-0R1d5Z680D0-0h3K5S00140o2q0p5a0Q0y0m1;0Z2q0i5_3:5{5A0p5u013v6x4$4W544!4h0p6D4}0|504z4+2,5456585a5c6H6J1S0s5l0Z0R3o6I6O1S0L0A0|0q1d0y5p3y5g6$6W0@6Y0|3A6?6(0@4~6M2%6}370o0|276:3Y6 773|6Q5L6S4:6U714|5f0|0E6|7i6^0|0u0u7m520@0N0Z0|487h7t015g5i4o6x6C720A0J0|030p0z0Z0c0y0w5N0m5)1|2q0n5Z4^0p0x0F2r0p5V1P4J0D1O4_0p0T2e0D570d0p7$5Y7@1N0y0D7l7E7F5o724X042q0Q5P7s5e3j7c57597f6B5A6@01847Q5-7a6K047D2#0681827n017I7K0p0n0a0D2F2g2S0)7X7^6o0-6m6k6b0R0Y6i2q6#80818i0n6,0#8n7j040d893r6,0t8Z6~0|8$6V728W178*6N8v4~8.2#6%8v8;0U8Y8/8v0s7p8%4w8c7e5b8g8U830|8688917A798T8t8u7A8;5X4=5$8+7B6L9r8~907z8a9s040E8`3_9k7G8}4.4:5Y4?4^4`8@9h9t9N9y8;0q9w2^8i5g9C419E8h8:9H4;9K4_9r9i9x8(040q8?9-6;7k9Y3f9!9l9R9%9J9q9Q369,9V9$8=9+9@9a7F9W7k3F0g4S0y2x2Yaf4C1w4E2A2D2y0x7|2x4D0~0g0%0)0+0R04.