lambdaway :: barycentre

3 | list | login |load

| |

{uncover https://figurinepop.com/public/agnes1_2.jpg 100 800 Agnes loves the de Casteljau algorithm.}

_h1 barycentre

_p Retour sur l'algorithme de [[de Casteljau|?view=decasteljau]], sur l'exemple d'une cubique.

_h2 1) principe

_img http://b2b3.free.fr/confs/data/angles/2/casteljau/pL4.gif

_p L'expression algébrique vectorielle paramétrique d'une cubique est

{center {code
{b p}(t) = (1-t){sup 3}{b p{sub 0}} + 3(1-t){sup 2}t{b p{sub 1}} + 3(1-t)t{sup 2}{b p{sub 2}} + t{sup 3}{b p{sub 3}}
}}
_p où {b p} est un point de R{sup n} et {b t} est dans l'intervalle [0,1] de R.

_h2 2) algorithme

_p L'algorithme de de Casteljau consiste en une séquence d'interpolations linéaires aboutissant au point {b P(t)}. Pour t=1/2 :
{pre
.     [{b p0}  p1  p2  {b p3}]     the control polygon
        [{b q0}  q1  {b q2}]       q{sub i} = (p{sub i}+p{sub i+1})/2  i in [0,1,2]
          [{b r0}  {b r1}]         r{sub i} = (q{sub i}+q{sub i+1})/2  i in [0,1]
            [{b s0}]           s{sub 1} = (r{sub i}+r{sub i+1})/2  i in [0]
}

_p On peut y voir quelques parentés avec l'algorithme de [[horner_newton]] évitant les calculs sur des polynômes générant des débordements numériques quand le degré est élevé.

_h2 code

_h3 1) Les trois fonctions essentielles

{pre

'{def p.interpol         // interpole 2 points en 2D
 {lambda {:p0 :p1 :t}
  {A.new {+ {* {A.first :p0} {- 1 :t}}
            {* {A.first :p1} :t}}
         {+ {* {A.last :p0} {- 1 :t}}
            {* {A.last :p1} :t}} } }} 
-> {def p.interpol 
 {lambda {:p0 :p1 :t}
  {A.new {+ {* {A.first :p0} {- 1 :t}}
            {* {A.first :p1} :t}}
         {+ {* {A.last :p0} {- 1 :t}}
            {* {A.last :p1} :t}} } }}

'{def a.sub              // le premier sous-polygone [q0 q1 q2]
 {def a.sub.rec
  {lambda {:a0 :a1 :t}
   {if {< {A.length :a0} 2}
    then :a1
    else {a.sub.rec
          {A.rest :a0} 
          {A.addlast! {p.interpol {A.get 0 :a0}
                                  {A.get 1 :a0} :t} :a1} :t} }}}
 {lambda {:a :t}
  {a.sub.rec :a {A.new} :t}}} 
-> {def a.sub
 {def a.sub.rec
  {lambda {:a0 :a1 :t}
   {if {< {A.length :a0} 2}
    then :a1
    else {a.sub.rec
          {A.rest :a0} 
          {A.addlast! {p.interpol {A.get 0 :a0}
                                  {A.get 1 :a0} :t} :a1} :t} }}}
 {lambda {:a :t}
  {a.sub.rec :a {A.new} :t}}}

'{def a.interpol         // le point "milieu" s0
 {lambda {:a :t}
  {if {= {A.length :a} 1}
   then {A.first :a}
   else {a.interpol {a.sub :a :t} :t}}}}
-> {def a.interpol
 {lambda {:a :t}
  {if {= {A.length :a} 1}
   then {A.first :a}
   else {a.interpol {a.sub :a :t} :t}}}}
}

_p Ces trois fonctions sont suffisantes pour tracer la courbe {b de façon continue} dans un intervalle {b t ∈ [a,b]}.

_h3 2) Trois de plus en bonus

{pre
'{def a.split            // [p0 q0 r0 s0] ou [s0 r1 q2 p3]
 {def a.split.rec
  {lambda {:a0 :a1 :t :lr}
   {if {< {A.length :a0} 1}
    then :a1
    else {a.split.rec
          {a.sub :a0 :t}
          {if :lr
           then {A.addlast! {A.first :a0} :a1}
           else {A.addfirst! {A.last :a0} :a1} } :t :lr} }}}
 {lambda {:a :t :lr}
  {a.split.rec :a {A.new} :t :lr}}} 
-> {def a.split
 {def a.split.rec
  {lambda {:a0 :a1 :t :lr}
   {if {< {A.length :a0} 1}
    then :a1
    else {a.split.rec
          {a.sub :a0 :t}
          {if :lr
           then {A.addlast! {A.first :a0} :a1}
           else {A.addfirst! {A.last :a0} :a1} } :t :lr} }}}
 {lambda {:a :t :lr}
  {a.split.rec :a {A.new} :t :lr}}}

'{def a.stretch          // de [0,1] à [t0,t1]
 {lambda {:a :t0 :t1}
  {A.reverse 
   {a.split 
    m{a.split :a :t0 true} {/ :t1 :t0} false}}}}
-> {def a.stretch
 {lambda {:a :t0 :t1}
  {A.reverse {a.split {a.split :a :t0 true} {/ :t1 :t0} false}}}}

'{def a.blossom          // arbre des sous-polygones de contrôle
 {lambda {:a :n}
  {if {< :n 1}
   then :a
   else {A.new {a.blossom {a.split :a 0.5 true} {- :n 1}}
               {a.blossom {a.split :a 0.5 false} {- :n 1}} }}}}
-> {def a.blossom 
 {lambda {:a :n}
  {if {< :n 1}
   then :a
   else {A.new {a.blossom
                {a.split :a 0.5 true} {- :n 1}}
               {a.blossom
                {a.split :a 0.5 false} {- :n 1}} }}}}
}

_p Ces trois fonctions supplémentaires nous permettent de tracer la courbe comme partition de l'unité. Il est à noter que la partition de l'unité obtenue par divisions par 2 récursivement appliquée à gauche et à droite produit un ensemble {b dense} et non continu. Les valeurs {b 1/2, 1/4, 1/8, ...} en font partie mais une infinité de valeurs en sont exclues, comme  {b 1/3, 1/π, 1/e, ...}.

_h3 3) Un peu de SVG

_p Lambdatalk possède quelques fonctions SVG permettant de tracer effectivement les courbes dans la page wiki.

{pre
'{def svgpoint          // du tableau [x,y] au format SVG "x,y"
 {lambda {:p} {A.first :p},{A.last :p}}}
-> {def svgpoint {lambda {:p} {A.first :p},{A.last :p}}}

'{def dot               // cercle SVG à :p, couleur :c, rayon :r
 {lambda {:p :c :r} 
  {circle 
   {@ cx="{A.first :p}px"
      cy="{A.last :p}px"
      r=":rpx"
      fill=":c"}}}}
-> {def dot 
 {lambda {:p :c :r} 
  {circle {@ cx="{A.first :p}px" cy="{A.last :p}px" r=":rpx" fill=":c"}}}}

'{def bloss2svg         // de l'arbre aux points SVG
 {lambda {:b}  
  {S.replace , by space in 
  {S.replace \s,\s by space in 
  {S.replace \[+ by space in 
  {S.replace \]+ by space in {A.disp :b}}}}}}}
-> {def bloss2svg
 {lambda {:b}  
  {S.replace , by space in 
  {S.replace \s,\s by space in 
  {S.replace \[+ by space in 
  {S.replace \]+ by space in {A.disp :b}}}}}}}

}

_h2 3) application

_p Noter que nous ne sommes pas limité à la cubique, le nombre de points de contrôle est libre.

_h3 1) définition des cubiques

{prewrap
'{def p0 {A.new 150 150}} 
-> {def p0 {A.new 150 150}} = {p0}
'{def p1 {A.new 20 20}} 
-> {def p1 {A.new 20 20}} = {p1}
'{def p2 {A.new 480 20}} 
-> {def p2 {A.new 480 20}} = {p2}
'{def p3 {A.new 150 480}} 
-> {def p3 {A.new 150 480}} = {p2}

'{def cubic {A.new {p0} {p1} {p2} {p3}}} 
-> {def cubic {A.new {p0} {p1} {p2} {p3}}} = {cubic}

'{def scubic {a.stretch {cubic} 0.1 0.9}} 
-> {def scubic {a.stretch {cubic} 0.1 0.9}} = {scubic}
}

_h3 2) tracé récursif
_p On construit récursivement avec la fonction {b blossom} les sous-polynomes à gauche et à droite à un niveau de profondeur/récursion choisi, et on les trace.

{prewrap

'{svg {@ style="width:580px; height:580px; background:#ddd;"}
 {g {@ transform="translate(40,40)"}

{dot {p0} #f00 10}
  {dot {p1} #f00 10}
  {dot {p2} #f00 10}
  {dot {p3} #f00 10}

{dot {A.get 0 {scubic}} #fff 12}
  {dot {A.get 1 {scubic}} #fff 12}
  {dot {A.get 2 {scubic}} #fff 12}
  {dot {A.get 3 {scubic}} #fff 12}

// les deux cubiques
 {polyline
  {@ points="{bloss2svg {a.blossom {scubic} 4}}"
     stroke="#f00" fill="transparent" stroke-width="5px"
 }}
  {polyline
  {@ points="{bloss2svg {a.blossom {cubic} 4}}"
     stroke="#ff0" fill="transparent"
 }}

// récursion 0 : polygone de controle
 {polyline
  {@ points="{bloss2svg {a.blossom {scubic} 0}}"       
     stroke="#888" fill="transparent" stroke-width="1px"
 }}

// récursion 1 : deux polygones de controle
 {polyline
  {@ points="{bloss2svg {a.blossom {scubic} 1}}"
     stroke="#888" fill="transparent" stroke-width="1px"
 }}

// récursion 2 : quatre polygones de controle
 {polyline
  {@ points="{bloss2svg {a.blossom {scubic} 2}}"
     stroke="#888" fill="transparent" stroke-width="1px"
 }}

}}

}

_p Ce code affiche

{svg {@ style="width:580px; height:580px; background:#ddd;"}
 {g {@ transform="translate(40,40)"}

{dot {p0} #f00 10}
  {dot {p1} #f00 10}
  {dot {p2} #f00 10}
  {dot {p3} #f00 10}

{dot {A.get 0 {scubic}} #fff 12}
  {dot {A.get 1 {scubic}} #fff 12}
  {dot {A.get 2 {scubic}} #fff 12}
  {dot {A.get 3 {scubic}} #fff 12}

{polyline
  {@ points="{bloss2svg {a.blossom {scubic} 4}}"
     stroke="#f00" fill="transparent" stroke-width="7px"
 }}

{polyline
  {@ points="{bloss2svg {a.blossom {scubic} 4}}"
     stroke="#f00" fill="transparent" stroke-width="7px"
 }}
 {polyline
  {@ points="{bloss2svg {a.blossom {cubic} 4}}"
     stroke="#000" fill="transparent" stroke-width="2px"
 }}

{polyline
  {@ points="{bloss2svg {a.blossom {scubic} 0}}"
     stroke="#888" fill="transparent" stroke-width="1px"
 }}
 {polyline
  {@ points="{bloss2svg {a.blossom {scubic} 1}}"
     stroke="#888" fill="transparent" stroke-width="1px"
 }}
 {polyline
  {@ points="{bloss2svg {a.blossom {scubic} 2}}"
     stroke="#888" fill="transparent" stroke-width="1px"
 }}
 
}}

_h3 3) tracé itératif
_p En utilisant la fonction {b a.interpol} qui retourne le point interpolant la courbe en t on construit la séquence de points dans un intervalle donné, [0,1] et [0.1,0.9].

{pre
'{svg {@ style="width:580px; height:580px; background:#ddd;"}
 {g {@ transform="translate(40,40)"}

{dot {p0} #f00 10}
  {dot {p1} #f00 10}
  {dot {p2} #f00 10}
  {dot {p3} #f00 10}

{dot {A.get 0 {scubic}} #0ff 8}
  {dot {A.get 1 {scubic}} #0ff 8}
  {dot {A.get 2 {scubic}} #0ff 8}
  {dot {A.get 3 {scubic}} #0ff 8}

// deux séries de points 
  {S.map {lambda {:i} {dot {a.interpol {scubic} :i} #888 6}}
         {S.serie 0 1 {/ 1 32}}} 
  {S.map {lambda {:i} {dot {a.interpol {cubic} :i} #f00 5}} 
         {S.serie 0 1 {/ 1 32}}}

// deux polylignes
 {polyline
  {@ points="{S.map {lambda {:i}
                            {svgpoint {a.interpol {scubic} :i}}}
                    {S.serie 0 1 {/ 1 32}}}"
     stroke="#000" stroke-width="5px" fill="transparent"
 }} 
 {polyline
  {@ points="{S.map {lambda {:i} 
                            {svgpoint {a.interpol {cubic} :i}}}
                    {S.serie 0 1 {/ 1 32}}}" 
     stroke="#ff0" fill="transparent"
 }}
}}
}

_p Ce code affiche

{svg {@ style="width:580px; height:580px; background:#ddd;"}
 {g {@ transform="translate(40,40)"}

{dot {p0} #f00 10}
  {dot {p1} #f00 10}
  {dot {p2} #f00 10}
  {dot {p3} #f00 10}

{dot {A.get 0 {scubic}} #fff 12}
  {dot {A.get 1 {scubic}} #fff 12}
  {dot {A.get 2 {scubic}} #fff 12}
  {dot {A.get 3 {scubic}} #fff 12}

{S.map {lambda {:i} {dot {a.interpol {scubic} :i} #888 8}} {S.serie 0 1 {/ 1 32}}} 
  {S.map {lambda {:i} {dot {a.interpol {cubic} :i} #f00 5}} {S.serie 0 1 {/ 1 32}}}

{polyline {@ points="{S.map {lambda {:i} {svgpoint {a.interpol {scubic} :i}}}
    {S.serie 0 1 {/ 1 32}}}" stroke="#000" stroke-width="5px" fill="transparent"}} 
 {polyline {@ points="{S.map {lambda {:i} {svgpoint {a.interpol {cubic} :i}}}
    {S.serie 0 1 {/ 1 32}}}" stroke="#fff" fill="transparent"}}
}}
 
_h2 notes
_ul l'approche itérative conduit à une courbe {b continue}, en bijection avec {b R}, tandis que l'approche récursive conduit à une courbe {b dense}, en bijection avec la partition de l'unité. Une sorte de quantification, de fractalisation. Qui pourrait mener à une unification entre la relativité générale (univers continu) et la mécanique quantique (univers dense), confer [[relativite_complexe]], qui sait ?
_ul Dans l'approche récursive l'interpolation peut se réduire à la division par 2 et pourrait faire l'objet d'une optimisation. A suivre ...

_p {i alain marty | 2022/10/01}