http://os-vps418.infomaniak.ch:1250/mediawiki/api.php?action=feedcontributions&feedformat=atom&user=Jdubois 2026-05-21T06:28:35Z Contributions MediaWiki 1.39.4 http://os-vps418.infomaniak.ch:1250/mediawiki/index.php?title=G%C3%A9om%C3%A9trie_discr%C3%A8te,_Convexit%C3%A9_des_polyominos,_Combinatoire_des_mots&diff=14278 2022-05-30T12:16:15Z

<p>Jdubois : /* Sources et références */</p> <hr /> <div>Les images numérisées sont constituées de pixels, de petits carrés de couleurs. Les formes dans ces images ont alors une forme très particulière puisqu'il n'y a que quatres chemins possibles. Impossible d'aller en diagonale ou avec un angle particulier, les points n'ont que des coordonnées entières. &lt;br/&gt;<br /> On peut alors retrouver les éléments de la géométrie Euclidienne classique dans Z² via un outil : '''les mots de Christoffel.''' &lt;br/&gt;<br /> Cet outil permet de discrétiser des droites dans Z² afin de trouver la pente de celles-ci avec pour but d'appliquer les calculs de la géométrie Euclidienne.<br /> <br /> ----<br /> <br /> == Mot de Christoffel ==<br /> <br /> On prend une droite de pente p/q et on veut dessiner une droite discrète de celle-ci en connectant des points de coordonnées entières dans Z².&lt;br/&gt;<br /> On peut décrire cette droite comme &quot;''commençant''&quot; au point de coordonnée (0,0), passant par le point (p,q) et n'ayant que deux choix de mouvements :<br /> &lt;ul&gt;<br /> &lt;li&gt;X pour se déplacer d'une unité à droite sur l'axe des abscisses.&lt;/li&gt;<br /> &lt;li&gt;Y pour se déplacer d'une unité en haut sur l'axe des ordonnées.&lt;/li&gt;<br /> &lt;/ul&gt;<br /> Ainsi par exemple, on peut discrétiser la pente 2/3 en faisant les mouvements '''[x,x,x,y,y]''' ou '''[y,y,x,x,x]'''.<br /> <br /> Un mot de Christoffel se base sur le même principe hormis qu'il va essayer de toujours être le plus proche possible de la ligne sans jamais la traverser.<br /> <br /> [[Fichier:74.jpg]]<br /> <br /> ''Mot de Christoffel &quot;bas&quot; [x,x,y,x,x,y,x,x,y,x,y] et &quot;haut&quot; [y,x,y,x,x,y,x,x,y,x,x] de la droite de pente 4/7.''<br /> <br /> '''Note''' : ''Le mot de Christoffel &quot;haut&quot; est le mot de Christoffel &quot;bas&quot; lu à l'envers.''&lt;br/&gt;<br /> '''Note 2''' : ''Si on retire la première et la dernière lettre d'un mot de Christoffel, on obtient un palindrome (lisible dans les deux sens)''<br /> '''Note 3''' : ''La première et la dernière lettre d'un mot de Christoffel sont forcément différentes.''<br /> <br /> === Algorithme de génération ===<br /> <br /> Il est possible de générer facilement et très rapidement le mot de Christoffel d'une pente grâce à une méthode simple :<br /> <br /> La suite U définie par : &lt;math&gt;U0 = 0 | Un+1= (Un+a) [a+b]&lt;/math&gt; donnera une suite de chiffre qui se répète.&lt;br/&gt;<br /> Si Un &gt; Un+1, on ajoute un x au mot, sinon on ajoute un y au mot.<br /> <br /> On applique cette méthode jusqu'à ce que Un+1 = 0 pour avoir le mot de Christoffel de la pente.<br /> <br /> ==== Exemple ====<br /> Avec une pente de 5/7, on obtient : &lt;br/&gt;<br /> 0 5 10 3 8 1 6 11 4 9 2 7 0&lt;br/&gt;<br /> Soit en appliquant la méthode : x x y x y x x y x y x y&lt;br/&gt;<br /> On retrouve bien le mot de Christoffel de la pente 5/7 : [x,x,y,x,y,x,x,y,x,y,x,y]<br /> <br /> ==== Implémentation Python ====<br /> [[Fichier:Algo.png]]<br /> <br /> == Mot de contour ==<br /> <br /> On peut définir un mot de contour comme un ensemble de mot de Christoffel étant orientés différemment les uns des autres.&lt;br/&gt;<br /> Dans le cadre du module visi201, j'ai utilisé un algorithme pour le générer ayant le principe suivant :<br /> &lt;ul&gt;<br /> &lt;li&gt;On considère en entrée une forme '''convexe''' noire sur un fond blanc.&lt;/li&gt;<br /> &lt;li&gt;On crée une matrice avec la couleur de chaque pixel, c'est cette matrice qu'on traitera par la suite.&lt;/li&gt;<br /> &lt;li&gt;On choisit deux points aléatoires jusqu'à ce qu'un d'eux soit noir et l'autre blanc.&lt;/li&gt;<br /> &lt;li&gt;On applique le principe de dichotomie jusqu'à trouver un point étant le contour de la figure&lt;/li&gt;<br /> &lt;li&gt;On parcourt la figure dans un sens arbitraire tout en restant &quot;collé&quot; à son contour&lt;/li&gt;<br /> &lt;li&gt;Chaque mouvement est ajouté à une chaine de caractère sous forme de chiffre. ''(0 pour la droite, 1 pour le bas, ...)''&lt;/li&gt;<br /> &lt;li&gt;Dès qu'on retombe sur le point de départ de la figure, on a généré le mot de contour ayant 4 lettres : 0,1,2 et 3 pour chacun des mouvements.&lt;/li&gt;<br /> &lt;/ul&gt;<br /> <br /> Note : Un mot de contour n'est donc pas unique, il dépend de là où on commence le parcours de la figure.<br /> <br /> == Détection de droite discrète ==<br /> <br /> La détection de la pente d'une droite discrète à partir d'un mot de Christoffel passe par un algorithme plus complexe que celui permettant de faire son opposé.<br /> <br /> === Algorithme ===<br /> <br /> Cet algorithme se base sur le principe de &quot;coincer&quot; la discrétisation entre deux droites afin qu'il n'y ait qu'un point entier en ordonnée entre les deux droites pour chaque abscisse (toujours dans Z²).<br /> <br /> ==== Initialisation ====<br /> <br /> &lt;math&gt;\mu = 0&lt;/math&gt; &lt;br/&gt;<br /> point d'appui haut minimal / upmin = (0,0) &lt;br/&gt;<br /> point d'appui bas minimal / downmin = (0,0) &lt;br/&gt;<br /> point d'appui haut maximal / upmax = 1er point du mot (donc (1,0) ou (0,1)) &lt;br/&gt;<br /> point d'appui bas maximal / downmax = 1er point du mot (donc (1,0) ou (0,1)) &lt;br/&gt;<br /> a=0/1 selon le premier point&lt;br/&gt;<br /> b=0/1 selon le premier point&lt;br/&gt;<br /> <br /> ===== Implémentation python =====<br /> <br /> [[Fichier:init.png]]<br /> <br /> ==== Itération : Implémentation python ====<br /> <br /> [[Fichier:iteration.png]]<br /> <br /> == Conclusion ==<br /> <br /> Avec la pente des droites qu'on récupère via l'algorithme de détection des droites, on peut alors considérer une droite discrètiser comme une droite banale de R² et donc retrouver les formes de R² à partir des formes dans la géométrie de Z² et ainsi aisément retrouver tout les éléments de la géométrie Euclidienne classique. Le périmètre, la convexité et les points d'intersection sont alors calculable par exemple.<br /> <br /> Les mots de Christoffel permettent donc un passage d'une géométrie de Z² à des éléments de la géométrie Euclidienne classique.<br /> <br /> == Sources et références ==<br /> 1. Lyndon + Christoffel = Convex Hull (bollu github)[https://bollu.github.io/lyndon-christoffel-convex-hull.html] &lt;br/&gt;<br /> 2. Géométrie discrète linéaire asymptotique et applications [https://www.lama.univ-savoie.fr/pagesmembres/lachaud/People/LACHAUD-JO/Talks/chambery-ejc-2010.pdf]</div>

Jdubois http://os-vps418.infomaniak.ch:1250/mediawiki/index.php?title=G%C3%A9om%C3%A9trie_discr%C3%A8te,_Convexit%C3%A9_des_polyominos,_Combinatoire_des_mots&diff=14277 2022-05-30T12:16:00Z

<p>Jdubois : </p> <hr /> <div>Les images numérisées sont constituées de pixels, de petits carrés de couleurs. Les formes dans ces images ont alors une forme très particulière puisqu'il n'y a que quatres chemins possibles. Impossible d'aller en diagonale ou avec un angle particulier, les points n'ont que des coordonnées entières. &lt;br/&gt;<br /> On peut alors retrouver les éléments de la géométrie Euclidienne classique dans Z² via un outil : '''les mots de Christoffel.''' &lt;br/&gt;<br /> Cet outil permet de discrétiser des droites dans Z² afin de trouver la pente de celles-ci avec pour but d'appliquer les calculs de la géométrie Euclidienne.<br /> <br /> ----<br /> <br /> == Mot de Christoffel ==<br /> <br /> On prend une droite de pente p/q et on veut dessiner une droite discrète de celle-ci en connectant des points de coordonnées entières dans Z².&lt;br/&gt;<br /> On peut décrire cette droite comme &quot;''commençant''&quot; au point de coordonnée (0,0), passant par le point (p,q) et n'ayant que deux choix de mouvements :<br /> &lt;ul&gt;<br /> &lt;li&gt;X pour se déplacer d'une unité à droite sur l'axe des abscisses.&lt;/li&gt;<br /> &lt;li&gt;Y pour se déplacer d'une unité en haut sur l'axe des ordonnées.&lt;/li&gt;<br /> &lt;/ul&gt;<br /> Ainsi par exemple, on peut discrétiser la pente 2/3 en faisant les mouvements '''[x,x,x,y,y]''' ou '''[y,y,x,x,x]'''.<br /> <br /> Un mot de Christoffel se base sur le même principe hormis qu'il va essayer de toujours être le plus proche possible de la ligne sans jamais la traverser.<br /> <br /> [[Fichier:74.jpg]]<br /> <br /> ''Mot de Christoffel &quot;bas&quot; [x,x,y,x,x,y,x,x,y,x,y] et &quot;haut&quot; [y,x,y,x,x,y,x,x,y,x,x] de la droite de pente 4/7.''<br /> <br /> '''Note''' : ''Le mot de Christoffel &quot;haut&quot; est le mot de Christoffel &quot;bas&quot; lu à l'envers.''&lt;br/&gt;<br /> '''Note 2''' : ''Si on retire la première et la dernière lettre d'un mot de Christoffel, on obtient un palindrome (lisible dans les deux sens)''<br /> '''Note 3''' : ''La première et la dernière lettre d'un mot de Christoffel sont forcément différentes.''<br /> <br /> === Algorithme de génération ===<br /> <br /> Il est possible de générer facilement et très rapidement le mot de Christoffel d'une pente grâce à une méthode simple :<br /> <br /> La suite U définie par : &lt;math&gt;U0 = 0 | Un+1= (Un+a) [a+b]&lt;/math&gt; donnera une suite de chiffre qui se répète.&lt;br/&gt;<br /> Si Un &gt; Un+1, on ajoute un x au mot, sinon on ajoute un y au mot.<br /> <br /> On applique cette méthode jusqu'à ce que Un+1 = 0 pour avoir le mot de Christoffel de la pente.<br /> <br /> ==== Exemple ====<br /> Avec une pente de 5/7, on obtient : &lt;br/&gt;<br /> 0 5 10 3 8 1 6 11 4 9 2 7 0&lt;br/&gt;<br /> Soit en appliquant la méthode : x x y x y x x y x y x y&lt;br/&gt;<br /> On retrouve bien le mot de Christoffel de la pente 5/7 : [x,x,y,x,y,x,x,y,x,y,x,y]<br /> <br /> ==== Implémentation Python ====<br /> [[Fichier:Algo.png]]<br /> <br /> == Mot de contour ==<br /> <br /> On peut définir un mot de contour comme un ensemble de mot de Christoffel étant orientés différemment les uns des autres.&lt;br/&gt;<br /> Dans le cadre du module visi201, j'ai utilisé un algorithme pour le générer ayant le principe suivant :<br /> &lt;ul&gt;<br /> &lt;li&gt;On considère en entrée une forme '''convexe''' noire sur un fond blanc.&lt;/li&gt;<br /> &lt;li&gt;On crée une matrice avec la couleur de chaque pixel, c'est cette matrice qu'on traitera par la suite.&lt;/li&gt;<br /> &lt;li&gt;On choisit deux points aléatoires jusqu'à ce qu'un d'eux soit noir et l'autre blanc.&lt;/li&gt;<br /> &lt;li&gt;On applique le principe de dichotomie jusqu'à trouver un point étant le contour de la figure&lt;/li&gt;<br /> &lt;li&gt;On parcourt la figure dans un sens arbitraire tout en restant &quot;collé&quot; à son contour&lt;/li&gt;<br /> &lt;li&gt;Chaque mouvement est ajouté à une chaine de caractère sous forme de chiffre. ''(0 pour la droite, 1 pour le bas, ...)''&lt;/li&gt;<br /> &lt;li&gt;Dès qu'on retombe sur le point de départ de la figure, on a généré le mot de contour ayant 4 lettres : 0,1,2 et 3 pour chacun des mouvements.&lt;/li&gt;<br /> &lt;/ul&gt;<br /> <br /> Note : Un mot de contour n'est donc pas unique, il dépend de là où on commence le parcours de la figure.<br /> <br /> == Détection de droite discrète ==<br /> <br /> La détection de la pente d'une droite discrète à partir d'un mot de Christoffel passe par un algorithme plus complexe que celui permettant de faire son opposé.<br /> <br /> === Algorithme ===<br /> <br /> Cet algorithme se base sur le principe de &quot;coincer&quot; la discrétisation entre deux droites afin qu'il n'y ait qu'un point entier en ordonnée entre les deux droites pour chaque abscisse (toujours dans Z²).<br /> <br /> ==== Initialisation ====<br /> <br /> &lt;math&gt;\mu = 0&lt;/math&gt; &lt;br/&gt;<br /> point d'appui haut minimal / upmin = (0,0) &lt;br/&gt;<br /> point d'appui bas minimal / downmin = (0,0) &lt;br/&gt;<br /> point d'appui haut maximal / upmax = 1er point du mot (donc (1,0) ou (0,1)) &lt;br/&gt;<br /> point d'appui bas maximal / downmax = 1er point du mot (donc (1,0) ou (0,1)) &lt;br/&gt;<br /> a=0/1 selon le premier point&lt;br/&gt;<br /> b=0/1 selon le premier point&lt;br/&gt;<br /> <br /> ===== Implémentation python =====<br /> <br /> [[Fichier:init.png]]<br /> <br /> ==== Itération : Implémentation python ====<br /> <br /> [[Fichier:iteration.png]]<br /> <br /> == Conclusion ==<br /> <br /> Avec la pente des droites qu'on récupère via l'algorithme de détection des droites, on peut alors considérer une droite discrètiser comme une droite banale de R² et donc retrouver les formes de R² à partir des formes dans la géométrie de Z² et ainsi aisément retrouver tout les éléments de la géométrie Euclidienne classique. Le périmètre, la convexité et les points d'intersection sont alors calculable par exemple.<br /> <br /> Les mots de Christoffel permettent donc un passage d'une géométrie de Z² à des éléments de la géométrie Euclidienne classique.<br /> <br /> == Sources et références ==<br /> 1. Lyndon + Christoffel = Convex Hull (bollu github)[https://bollu.github.io/lyndon-christoffel-convex-hull.html]<br /> 2. Géométrie discrète linéaire asymptotique et applications [https://www.lama.univ-savoie.fr/pagesmembres/lachaud/People/LACHAUD-JO/Talks/chambery-ejc-2010.pdf]</div>

Jdubois http://os-vps418.infomaniak.ch:1250/mediawiki/index.php?title=G%C3%A9om%C3%A9trie_discr%C3%A8te,_Convexit%C3%A9_des_polyominos,_Combinatoire_des_mots&diff=14276 2022-05-29T20:54:22Z

<p>Jdubois : </p> <hr /> <div>Les images numérisées sont constituées de pixels, de petits carrés de couleurs. Les formes dans ces images ont alors une forme très particulière puisqu'il n'y a que quatres chemins possibles. Impossible d'aller en diagonale ou avec un angle particulier, les points n'ont que des coordonnées entières. &lt;br/&gt;<br /> On peut alors retrouver les éléments de la géométrie Euclidienne classique dans Z² via un outil : '''les mots de Christoffel.''' &lt;br/&gt;<br /> Cet outil permet de discrétiser des droites dans Z² afin de trouver la pente de celles-ci avec pour but d'appliquer les calculs de la géométrie Euclidienne.<br /> <br /> ----<br /> <br /> == Mot de Christoffel ==<br /> <br /> On prend une droite de pente p/q et on veut dessiner une droite discrète de celle-ci en connectant des points de coordonnées entières dans Z².&lt;br/&gt;<br /> On peut décrire cette droite comme &quot;''commençant''&quot; au point de coordonnée (0,0), passant par le point (p,q) et n'ayant que deux choix de mouvements :<br /> &lt;ul&gt;<br /> &lt;li&gt;X pour se déplacer d'une unité à droite sur l'axe des abscisses.&lt;/li&gt;<br /> &lt;li&gt;Y pour se déplacer d'une unité en haut sur l'axe des ordonnées.&lt;/li&gt;<br /> &lt;/ul&gt;<br /> Ainsi par exemple, on peut discrétiser la pente 2/3 en faisant les mouvements '''[x,x,x,y,y]''' ou '''[y,y,x,x,x]'''.<br /> <br /> Un mot de Christoffel se base sur le même principe hormis qu'il va essayer de toujours être le plus proche possible de la ligne sans jamais la traverser.<br /> <br /> [[Fichier:74.jpg]]<br /> <br /> ''Mot de Christoffel &quot;bas&quot; [x,x,y,x,x,y,x,x,y,x,y] et &quot;haut&quot; [y,x,y,x,x,y,x,x,y,x,x] de la droite de pente 4/7.''<br /> <br /> '''Note''' : ''Le mot de Christoffel &quot;haut&quot; est le mot de Christoffel &quot;bas&quot; lu à l'envers.''&lt;br/&gt;<br /> '''Note 2''' : ''Si on retire la première et la dernière lettre d'un mot de Christoffel, on obtient un palindrome (lisible dans les deux sens)''<br /> '''Note 3''' : ''La première et la dernière lettre d'un mot de Christoffel sont forcément différentes.''<br /> <br /> === Algorithme de génération ===<br /> <br /> Il est possible de générer facilement et très rapidement le mot de Christoffel d'une pente grâce à une méthode simple :<br /> <br /> La suite U définie par : &lt;math&gt;U0 = 0 | Un+1= (Un+a) [a+b]&lt;/math&gt; donnera une suite de chiffre qui se répète.&lt;br/&gt;<br /> Si Un &gt; Un+1, on ajoute un x au mot, sinon on ajoute un y au mot.<br /> <br /> On applique cette méthode jusqu'à ce que Un+1 = 0 pour avoir le mot de Christoffel de la pente.<br /> <br /> ==== Exemple ====<br /> Avec une pente de 5/7, on obtient : &lt;br/&gt;<br /> 0 5 10 3 8 1 6 11 4 9 2 7 0&lt;br/&gt;<br /> Soit en appliquant la méthode : x x y x y x x y x y x y&lt;br/&gt;<br /> On retrouve bien le mot de Christoffel de la pente 5/7 : [x,x,y,x,y,x,x,y,x,y,x,y]<br /> <br /> ==== Implémentation Python ====<br /> [[Fichier:Algo.png]]<br /> <br /> == Mot de contour ==<br /> <br /> On peut définir un mot de contour comme un ensemble de mot de Christoffel étant orientés différemment les uns des autres.&lt;br/&gt;<br /> Dans le cadre du module visi201, j'ai utilisé un algorithme pour le générer ayant le principe suivant :<br /> &lt;ul&gt;<br /> &lt;li&gt;On considère en entrée une forme '''convexe''' noire sur un fond blanc.&lt;/li&gt;<br /> &lt;li&gt;On crée une matrice avec la couleur de chaque pixel, c'est cette matrice qu'on traitera par la suite.&lt;/li&gt;<br /> &lt;li&gt;On choisit deux points aléatoires jusqu'à ce qu'un d'eux soit noir et l'autre blanc.&lt;/li&gt;<br /> &lt;li&gt;On applique le principe de dichotomie jusqu'à trouver un point étant le contour de la figure&lt;/li&gt;<br /> &lt;li&gt;On parcourt la figure dans un sens arbitraire tout en restant &quot;collé&quot; à son contour&lt;/li&gt;<br /> &lt;li&gt;Chaque mouvement est ajouté à une chaine de caractère sous forme de chiffre. ''(0 pour la droite, 1 pour le bas, ...)''&lt;/li&gt;<br /> &lt;li&gt;Dès qu'on retombe sur le point de départ de la figure, on a généré le mot de contour ayant 4 lettres : 0,1,2 et 3 pour chacun des mouvements.&lt;/li&gt;<br /> &lt;/ul&gt;<br /> <br /> Note : Un mot de contour n'est donc pas unique, il dépend de là où on commence le parcours de la figure.<br /> <br /> == Détection de droite discrète ==<br /> <br /> La détection de la pente d'une droite discrète à partir d'un mot de Christoffel passe par un algorithme plus complexe que celui permettant de faire son opposé.<br /> <br /> === Algorithme ===<br /> <br /> Cet algorithme se base sur le principe de &quot;coincer&quot; la discrétisation entre deux droites afin qu'il n'y ait qu'un point entier en ordonnée entre les deux droites pour chaque abscisse (toujours dans Z²).<br /> <br /> ==== Initialisation ====<br /> <br /> &lt;math&gt;\mu = 0&lt;/math&gt; &lt;br/&gt;<br /> point d'appui haut minimal / upmin = (0,0) &lt;br/&gt;<br /> point d'appui bas minimal / downmin = (0,0) &lt;br/&gt;<br /> point d'appui haut maximal / upmax = 1er point du mot (donc (1,0) ou (0,1)) &lt;br/&gt;<br /> point d'appui bas maximal / downmax = 1er point du mot (donc (1,0) ou (0,1)) &lt;br/&gt;<br /> a=0/1 selon le premier point&lt;br/&gt;<br /> b=0/1 selon le premier point&lt;br/&gt;<br /> <br /> ===== Implémentation python =====<br /> <br /> [[Fichier:init.png]]<br /> <br /> ==== Itération : Implémentation python ====<br /> <br /> [[Fichier:iteration.png]]<br /> <br /> == Conclusion ==<br /> <br /> Avec la pente des droites qu'on récupère via l'algorithme de détection des droites, on peut alors considérer une droite discrètiser comme une droite banale de R² et donc retrouver les formes de R² à partir des formes dans la géométrie de Z² et ainsi aisément retrouver tout les éléments de la géométrie Euclidienne classique. Le périmètre, la convexité et les points d'intersection sont alors calculable par exemple.<br /> <br /> Les mots de Christoffel permettent donc un passage d'une géométrie de Z² à des éléments de la géométrie Euclidienne classique.</div>

Jdubois http://os-vps418.infomaniak.ch:1250/mediawiki/index.php?title=G%C3%A9om%C3%A9trie_discr%C3%A8te,_Convexit%C3%A9_des_polyominos,_Combinatoire_des_mots&diff=14272 2022-05-29T20:29:08Z

<p>Jdubois : /* Détection de droite discrète */</p> <hr /> <div>Les images numérisées sont constituées de pixels, de petits carrés de couleurs. Les formes dans ces images ont alors une forme très particulière puisqu'il n'y a que quatres chemins possibles. Impossible d'aller en diagonale ou avec un angle particulier, les points n'ont que des coordonnées entières. &lt;br/&gt;<br /> On peut alors retrouver les éléments de la géométrie Euclidienne classique dans Z² via un outil : '''les mots de Christoffel.''' &lt;br/&gt;<br /> Cet outil permet de discrétiser des droites dans Z² afin de trouver la pente de celles-ci avec pour but d'appliquer les calculs de la géométrie Euclidienne.<br /> <br /> ----<br /> <br /> == Mot de Christoffel ==<br /> <br /> On prend une droite de pente p/q et on veut dessiner une droite discrète de celle-ci en connectant des points de coordonnées entières dans Z².&lt;br/&gt;<br /> On peut décrire cette droite comme &quot;''commençant''&quot; au point de coordonnée (0,0), passant par le point (p,q) et n'ayant que deux choix de mouvements :<br /> &lt;ul&gt;<br /> &lt;li&gt;X pour se déplacer d'une unité à droite sur l'axe des abscisses.&lt;/li&gt;<br /> &lt;li&gt;Y pour se déplacer d'une unité en haut sur l'axe des ordonnées.&lt;/li&gt;<br /> &lt;/ul&gt;<br /> Ainsi par exemple, on peut discrétiser la pente 2/3 en faisant les mouvements '''[x,x,x,y,y]''' ou '''[y,y,x,x,x]'''.<br /> <br /> Un mot de Christoffel se base sur le même principe hormis qu'il va essayer de toujours être le plus proche possible de la ligne sans jamais la traverser.<br /> <br /> [[Fichier:74.jpg]]<br /> <br /> ''Mot de Christoffel &quot;bas&quot; [x,x,y,x,x,y,x,x,y,x,y] et &quot;haut&quot; [y,x,y,x,x,y,x,x,y,x,x] de la droite de pente 4/7.''<br /> <br /> '''Note''' : ''Le mot de Christoffel &quot;haut&quot; est le mot de Christoffel &quot;bas&quot; lu à l'envers.''&lt;br/&gt;<br /> '''Note 2''' : ''Si on retire la première et la dernière lettre d'un mot de Christoffel, on obtient un palindrome (lisible dans les deux sens)''<br /> '''Note 3''' : ''La première et la dernière lettre d'un mot de Christoffel sont forcément différentes.''<br /> <br /> === Algorithme de génération ===<br /> <br /> Il est possible de générer facilement et très rapidement le mot de Christoffel d'une pente grâce à une méthode simple :<br /> <br /> La suite U définie par : &lt;math&gt;U0 = 0 | Un+1= (Un+a) [a+b]&lt;/math&gt; donnera une suite de chiffre qui se répète.&lt;br/&gt;<br /> Si Un &gt; Un+1, on ajoute un x au mot, sinon on ajoute un y au mot.<br /> <br /> On applique cette méthode jusqu'à ce que Un+1 = 0 pour avoir le mot de Christoffel de la pente.<br /> <br /> ==== Exemple ====<br /> Avec une pente de 5/7, on obtient : &lt;br/&gt;<br /> 0 5 10 3 8 1 6 11 4 9 2 7 0&lt;br/&gt;<br /> Soit en appliquant la méthode : x x y x y x x y x y x y&lt;br/&gt;<br /> On retrouve bien le mot de Christoffel de la pente 5/7 : [x,x,y,x,y,x,x,y,x,y,x,y]<br /> <br /> ==== Implémentation Python ====<br /> [[Fichier:Algo.png]]<br /> <br /> == Mot de contour ==<br /> <br /> On peut définir un mot de contour comme un ensemble de mot de Christoffel étant orientés différemment les uns des autres.&lt;br/&gt;<br /> Dans le cadre du module visi201, j'ai utilisé un algorithme pour le générer ayant le principe suivant :<br /> &lt;ul&gt;<br /> &lt;li&gt;On considère en entrée une forme '''convexe''' noire sur un fond blanc.&lt;/li&gt;<br /> &lt;li&gt;On crée une matrice avec la couleur de chaque pixel, c'est cette matrice qu'on traitera par la suite.&lt;/li&gt;<br /> &lt;li&gt;On choisit deux points aléatoires jusqu'à ce qu'un d'eux soit noir et l'autre blanc.&lt;/li&gt;<br /> &lt;li&gt;On applique le principe de dichotomie jusqu'à trouver un point étant le contour de la figure&lt;/li&gt;<br /> &lt;li&gt;On parcourt la figure dans un sens arbitraire tout en restant &quot;collé&quot; à son contour&lt;/li&gt;<br /> &lt;li&gt;Chaque mouvement est ajouté à une chaine de caractère sous forme de chiffre. ''(0 pour la droite, 1 pour le bas, ...)''&lt;/li&gt;<br /> &lt;li&gt;Dès qu'on retombe sur le point de départ de la figure, on a généré le mot de contour ayant 4 lettres : 0,1,2 et 3 pour chacun des mouvements.&lt;/li&gt;<br /> &lt;/ul&gt;<br /> <br /> Note : Un mot de contour n'est donc pas unique, il dépend de là où on commence le parcours de la figure.<br /> <br /> == Détection de droite discrète ==<br /> <br /> La détection de la pente d'une droite discrète à partir d'un mot de Christoffel passe par un algorithme plus complexe que celui permettant de faire son opposé.<br /> <br /> === Algorithme ===<br /> <br /> Cet algorithme se base sur le principe de &quot;coincer&quot; la discrétisation entre deux droites afin qu'il n'y ait qu'un point entier en ordonnée entre les deux droites pour chaque abscisse (toujours dans Z²).<br /> <br /> ==== Initialisation ====<br /> <br /> &lt;math&gt;\mu = 0&lt;/math&gt; &lt;br/&gt;<br /> point d'appui haut minimal / upmin = (0,0) &lt;br/&gt;<br /> point d'appui bas minimal / downmin = (0,0) &lt;br/&gt;<br /> point d'appui haut maximal / upmax = 1er point du mot (donc (1,0) ou (0,1)) &lt;br/&gt;<br /> point d'appui bas maximal / downmax = 1er point du mot (donc (1,0) ou (0,1)) &lt;br/&gt;<br /> a=0/1 selon le premier point&lt;br/&gt;<br /> b=0/1 selon le premier point&lt;br/&gt;<br /> <br /> ===== Implémentation python =====<br /> <br /> [[Fichier:init.png]]<br /> <br /> ==== Itération : Implémentation python ====<br /> <br /> [[Fichier:iteration.png]]</div>

Jdubois http://os-vps418.infomaniak.ch:1250/mediawiki/index.php?title=Fichier:Iteration.png&diff=14271 2022-05-29T20:28:57Z

<p>Jdubois : Jdubois a téléversé une nouvelle version de Fichier:Iteration.png</p> <hr /> <div></div>

Jdubois http://os-vps418.infomaniak.ch:1250/mediawiki/index.php?title=Fichier:Iteration.png&diff=14270 2022-05-29T20:27:41Z

<p>Jdubois : </p> <hr /> <div></div>

Jdubois http://os-vps418.infomaniak.ch:1250/mediawiki/index.php?title=Fichier:Init.png&diff=14263 2022-05-29T20:11:47Z

<p>Jdubois : </p> <hr /> <div></div>

Jdubois http://os-vps418.infomaniak.ch:1250/mediawiki/index.php?title=G%C3%A9om%C3%A9trie_discr%C3%A8te,_Convexit%C3%A9_des_polyominos,_Combinatoire_des_mots&diff=14255 2022-05-29T19:45:34Z

<p>Jdubois : /* Détection de droite discrète */</p> <hr /> <div>Les images numérisées sont constituées de pixels, de petits carrés de couleurs. Les formes dans ces images ont alors une forme très particulière puisqu'il n'y a que quatres chemins possibles. Impossible d'aller en diagonale ou avec un angle particulier, les points n'ont que des coordonnées entières. &lt;br/&gt;<br /> On peut alors retrouver les éléments de la géométrie Euclidienne classique dans Z² via un outil : '''les mots de Christoffel.''' &lt;br/&gt;<br /> Cet outil permet de discrétiser des droites dans Z² afin de trouver la pente de celles-ci avec pour but d'appliquer les calculs de la géométrie Euclidienne.<br /> <br /> ----<br /> <br /> == Mot de Christoffel ==<br /> <br /> On prend une droite de pente p/q et on veut dessiner une droite discrète de celle-ci en connectant des points de coordonnées entières dans Z².&lt;br/&gt;<br /> On peut décrire cette droite comme &quot;''commençant''&quot; au point de coordonnée (0,0), passant par le point (p,q) et n'ayant que deux choix de mouvements :<br /> &lt;ul&gt;<br /> &lt;li&gt;X pour se déplacer d'une unité à droite sur l'axe des abscisses.&lt;/li&gt;<br /> &lt;li&gt;Y pour se déplacer d'une unité en haut sur l'axe des ordonnées.&lt;/li&gt;<br /> &lt;/ul&gt;<br /> Ainsi par exemple, on peut discrétiser la pente 2/3 en faisant les mouvements '''[x,x,x,y,y]''' ou '''[y,y,x,x,x]'''.<br /> <br /> Un mot de Christoffel se base sur le même principe hormis qu'il va essayer de toujours être le plus proche possible de la ligne sans jamais la traverser.<br /> <br /> [[Fichier:74.jpg]]<br /> <br /> ''Mot de Christoffel &quot;bas&quot; [x,x,y,x,x,y,x,x,y,x,y] et &quot;haut&quot; [y,x,y,x,x,y,x,x,y,x,x] de la droite de pente 4/7.''<br /> <br /> '''Note''' : ''Le mot de Christoffel &quot;haut&quot; est le mot de Christoffel &quot;bas&quot; lu à l'envers.''&lt;br/&gt;<br /> '''Note 2''' : ''Si on retire la première et la dernière lettre d'un mot de Christoffel, on obtient un palindrome (lisible dans les deux sens)''<br /> '''Note 3''' : ''La première et la dernière lettre d'un mot de Christoffel sont forcément différentes.''<br /> <br /> === Algorithme de génération ===<br /> <br /> Il est possible de générer facilement et très rapidement le mot de Christoffel d'une pente grâce à une méthode simple :<br /> <br /> La suite U définie par : &lt;math&gt;U0 = 0 | Un+1= (Un+a) [a+b]&lt;/math&gt; donnera une suite de chiffre qui se répète.&lt;br/&gt;<br /> Si Un &gt; Un+1, on ajoute un x au mot, sinon on ajoute un y au mot.<br /> <br /> On applique cette méthode jusqu'à ce que Un+1 = 0 pour avoir le mot de Christoffel de la pente.<br /> <br /> ==== Exemple ====<br /> Avec une pente de 5/7, on obtient : &lt;br/&gt;<br /> 0 5 10 3 8 1 6 11 4 9 2 7 0&lt;br/&gt;<br /> Soit en appliquant la méthode : x x y x y x x y x y x y&lt;br/&gt;<br /> On retrouve bien le mot de Christoffel de la pente 5/7 : [x,x,y,x,y,x,x,y,x,y,x,y]<br /> <br /> ==== Implémentation Python ====<br /> [[Fichier:Algo.png]]<br /> <br /> == Mot de contour ==<br /> <br /> On peut définir un mot de contour comme un ensemble de mot de Christoffel étant orientés différemment les uns des autres.&lt;br/&gt;<br /> Dans le cadre du module visi201, j'ai utilisé un algorithme pour le générer ayant le principe suivant :<br /> &lt;ul&gt;<br /> &lt;li&gt;On considère en entrée une forme '''convexe''' noire sur un fond blanc.&lt;/li&gt;<br /> &lt;li&gt;On crée une matrice avec la couleur de chaque pixel, c'est cette matrice qu'on traitera par la suite.&lt;/li&gt;<br /> &lt;li&gt;On choisit deux points aléatoires jusqu'à ce qu'un d'eux soit noir et l'autre blanc.&lt;/li&gt;<br /> &lt;li&gt;On applique le principe de dichotomie jusqu'à trouver un point étant le contour de la figure&lt;/li&gt;<br /> &lt;li&gt;On parcourt la figure dans un sens arbitraire tout en restant &quot;collé&quot; à son contour&lt;/li&gt;<br /> &lt;li&gt;Chaque mouvement est ajouté à une chaine de caractère sous forme de chiffre. ''(0 pour la droite, 1 pour le bas, ...)''&lt;/li&gt;<br /> &lt;li&gt;Dès qu'on retombe sur le point de départ de la figure, on a généré le mot de contour ayant 4 lettres : 0,1,2 et 3 pour chacun des mouvements.&lt;/li&gt;<br /> &lt;/ul&gt;<br /> <br /> Note : Un mot de contour n'est donc pas unique, il dépend de là où on commence le parcours de la figure.<br /> <br /> == Détection de droite discrète ==<br /> <br /> La détection de la pente d'une droite discrète à partir d'un mot de Christoffel passe par un algorithme plus complexe que celui permettant de faire son opposé.[[Mot de Christoffel]]</div>

Jdubois http://os-vps418.infomaniak.ch:1250/mediawiki/index.php?title=G%C3%A9om%C3%A9trie_discr%C3%A8te,_Convexit%C3%A9_des_polyominos,_Combinatoire_des_mots&diff=14254 2022-05-29T19:45:11Z

<p>Jdubois : /* Détection de droite discrète */</p> <hr /> <div>Les images numérisées sont constituées de pixels, de petits carrés de couleurs. Les formes dans ces images ont alors une forme très particulière puisqu'il n'y a que quatres chemins possibles. Impossible d'aller en diagonale ou avec un angle particulier, les points n'ont que des coordonnées entières. &lt;br/&gt;<br /> On peut alors retrouver les éléments de la géométrie Euclidienne classique dans Z² via un outil : '''les mots de Christoffel.''' &lt;br/&gt;<br /> Cet outil permet de discrétiser des droites dans Z² afin de trouver la pente de celles-ci avec pour but d'appliquer les calculs de la géométrie Euclidienne.<br /> <br /> ----<br /> <br /> == Mot de Christoffel ==<br /> <br /> On prend une droite de pente p/q et on veut dessiner une droite discrète de celle-ci en connectant des points de coordonnées entières dans Z².&lt;br/&gt;<br /> On peut décrire cette droite comme &quot;''commençant''&quot; au point de coordonnée (0,0), passant par le point (p,q) et n'ayant que deux choix de mouvements :<br /> &lt;ul&gt;<br /> &lt;li&gt;X pour se déplacer d'une unité à droite sur l'axe des abscisses.&lt;/li&gt;<br /> &lt;li&gt;Y pour se déplacer d'une unité en haut sur l'axe des ordonnées.&lt;/li&gt;<br /> &lt;/ul&gt;<br /> Ainsi par exemple, on peut discrétiser la pente 2/3 en faisant les mouvements '''[x,x,x,y,y]''' ou '''[y,y,x,x,x]'''.<br /> <br /> Un mot de Christoffel se base sur le même principe hormis qu'il va essayer de toujours être le plus proche possible de la ligne sans jamais la traverser.<br /> <br /> [[Fichier:74.jpg]]<br /> <br /> ''Mot de Christoffel &quot;bas&quot; [x,x,y,x,x,y,x,x,y,x,y] et &quot;haut&quot; [y,x,y,x,x,y,x,x,y,x,x] de la droite de pente 4/7.''<br /> <br /> '''Note''' : ''Le mot de Christoffel &quot;haut&quot; est le mot de Christoffel &quot;bas&quot; lu à l'envers.''&lt;br/&gt;<br /> '''Note 2''' : ''Si on retire la première et la dernière lettre d'un mot de Christoffel, on obtient un palindrome (lisible dans les deux sens)''<br /> '''Note 3''' : ''La première et la dernière lettre d'un mot de Christoffel sont forcément différentes.''<br /> <br /> === Algorithme de génération ===<br /> <br /> Il est possible de générer facilement et très rapidement le mot de Christoffel d'une pente grâce à une méthode simple :<br /> <br /> La suite U définie par : &lt;math&gt;U0 = 0 | Un+1= (Un+a) [a+b]&lt;/math&gt; donnera une suite de chiffre qui se répète.&lt;br/&gt;<br /> Si Un &gt; Un+1, on ajoute un x au mot, sinon on ajoute un y au mot.<br /> <br /> On applique cette méthode jusqu'à ce que Un+1 = 0 pour avoir le mot de Christoffel de la pente.<br /> <br /> ==== Exemple ====<br /> Avec une pente de 5/7, on obtient : &lt;br/&gt;<br /> 0 5 10 3 8 1 6 11 4 9 2 7 0&lt;br/&gt;<br /> Soit en appliquant la méthode : x x y x y x x y x y x y&lt;br/&gt;<br /> On retrouve bien le mot de Christoffel de la pente 5/7 : [x,x,y,x,y,x,x,y,x,y,x,y]<br /> <br /> ==== Implémentation Python ====<br /> [[Fichier:Algo.png]]<br /> <br /> == Mot de contour ==<br /> <br /> On peut définir un mot de contour comme un ensemble de mot de Christoffel étant orientés différemment les uns des autres.&lt;br/&gt;<br /> Dans le cadre du module visi201, j'ai utilisé un algorithme pour le générer ayant le principe suivant :<br /> &lt;ul&gt;<br /> &lt;li&gt;On considère en entrée une forme '''convexe''' noire sur un fond blanc.&lt;/li&gt;<br /> &lt;li&gt;On crée une matrice avec la couleur de chaque pixel, c'est cette matrice qu'on traitera par la suite.&lt;/li&gt;<br /> &lt;li&gt;On choisit deux points aléatoires jusqu'à ce qu'un d'eux soit noir et l'autre blanc.&lt;/li&gt;<br /> &lt;li&gt;On applique le principe de dichotomie jusqu'à trouver un point étant le contour de la figure&lt;/li&gt;<br /> &lt;li&gt;On parcourt la figure dans un sens arbitraire tout en restant &quot;collé&quot; à son contour&lt;/li&gt;<br /> &lt;li&gt;Chaque mouvement est ajouté à une chaine de caractère sous forme de chiffre. ''(0 pour la droite, 1 pour le bas, ...)''&lt;/li&gt;<br /> &lt;li&gt;Dès qu'on retombe sur le point de départ de la figure, on a généré le mot de contour ayant 4 lettres : 0,1,2 et 3 pour chacun des mouvements.&lt;/li&gt;<br /> &lt;/ul&gt;<br /> <br /> Note : Un mot de contour n'est donc pas unique, il dépend de là où on commence le parcours de la figure.<br /> <br /> == Détection de droite discrète ==<br /> <br /> La détection de la pente d'une droite discrète à partir d'un mot de Christoffel passe par un algorithme plus complexe que celui permettant de faire son opposé.[[Algorithme de génération]]</div>

Jdubois http://os-vps418.infomaniak.ch:1250/mediawiki/index.php?title=G%C3%A9om%C3%A9trie_discr%C3%A8te,_Convexit%C3%A9_des_polyominos,_Combinatoire_des_mots&diff=14252 2022-05-29T19:44:31Z

<p>Jdubois : /* Détection de droite discrète */</p> <hr /> <div>Les images numérisées sont constituées de pixels, de petits carrés de couleurs. Les formes dans ces images ont alors une forme très particulière puisqu'il n'y a que quatres chemins possibles. Impossible d'aller en diagonale ou avec un angle particulier, les points n'ont que des coordonnées entières. &lt;br/&gt;<br /> On peut alors retrouver les éléments de la géométrie Euclidienne classique dans Z² via un outil : '''les mots de Christoffel.''' &lt;br/&gt;<br /> Cet outil permet de discrétiser des droites dans Z² afin de trouver la pente de celles-ci avec pour but d'appliquer les calculs de la géométrie Euclidienne.<br /> <br /> ----<br /> <br /> == Mot de Christoffel ==<br /> <br /> On prend une droite de pente p/q et on veut dessiner une droite discrète de celle-ci en connectant des points de coordonnées entières dans Z².&lt;br/&gt;<br /> On peut décrire cette droite comme &quot;''commençant''&quot; au point de coordonnée (0,0), passant par le point (p,q) et n'ayant que deux choix de mouvements :<br /> &lt;ul&gt;<br /> &lt;li&gt;X pour se déplacer d'une unité à droite sur l'axe des abscisses.&lt;/li&gt;<br /> &lt;li&gt;Y pour se déplacer d'une unité en haut sur l'axe des ordonnées.&lt;/li&gt;<br /> &lt;/ul&gt;<br /> Ainsi par exemple, on peut discrétiser la pente 2/3 en faisant les mouvements '''[x,x,x,y,y]''' ou '''[y,y,x,x,x]'''.<br /> <br /> Un mot de Christoffel se base sur le même principe hormis qu'il va essayer de toujours être le plus proche possible de la ligne sans jamais la traverser.<br /> <br /> [[Fichier:74.jpg]]<br /> <br /> ''Mot de Christoffel &quot;bas&quot; [x,x,y,x,x,y,x,x,y,x,y] et &quot;haut&quot; [y,x,y,x,x,y,x,x,y,x,x] de la droite de pente 4/7.''<br /> <br /> '''Note''' : ''Le mot de Christoffel &quot;haut&quot; est le mot de Christoffel &quot;bas&quot; lu à l'envers.''&lt;br/&gt;<br /> '''Note 2''' : ''Si on retire la première et la dernière lettre d'un mot de Christoffel, on obtient un palindrome (lisible dans les deux sens)''<br /> '''Note 3''' : ''La première et la dernière lettre d'un mot de Christoffel sont forcément différentes.''<br /> <br /> === Algorithme de génération ===<br /> <br /> Il est possible de générer facilement et très rapidement le mot de Christoffel d'une pente grâce à une méthode simple :<br /> <br /> La suite U définie par : &lt;math&gt;U0 = 0 | Un+1= (Un+a) [a+b]&lt;/math&gt; donnera une suite de chiffre qui se répète.&lt;br/&gt;<br /> Si Un &gt; Un+1, on ajoute un x au mot, sinon on ajoute un y au mot.<br /> <br /> On applique cette méthode jusqu'à ce que Un+1 = 0 pour avoir le mot de Christoffel de la pente.<br /> <br /> ==== Exemple ====<br /> Avec une pente de 5/7, on obtient : &lt;br/&gt;<br /> 0 5 10 3 8 1 6 11 4 9 2 7 0&lt;br/&gt;<br /> Soit en appliquant la méthode : x x y x y x x y x y x y&lt;br/&gt;<br /> On retrouve bien le mot de Christoffel de la pente 5/7 : [x,x,y,x,y,x,x,y,x,y,x,y]<br /> <br /> ==== Implémentation Python ====<br /> [[Fichier:Algo.png]]<br /> <br /> == Mot de contour ==<br /> <br /> On peut définir un mot de contour comme un ensemble de mot de Christoffel étant orientés différemment les uns des autres.&lt;br/&gt;<br /> Dans le cadre du module visi201, j'ai utilisé un algorithme pour le générer ayant le principe suivant :<br /> &lt;ul&gt;<br /> &lt;li&gt;On considère en entrée une forme '''convexe''' noire sur un fond blanc.&lt;/li&gt;<br /> &lt;li&gt;On crée une matrice avec la couleur de chaque pixel, c'est cette matrice qu'on traitera par la suite.&lt;/li&gt;<br /> &lt;li&gt;On choisit deux points aléatoires jusqu'à ce qu'un d'eux soit noir et l'autre blanc.&lt;/li&gt;<br /> &lt;li&gt;On applique le principe de dichotomie jusqu'à trouver un point étant le contour de la figure&lt;/li&gt;<br /> &lt;li&gt;On parcourt la figure dans un sens arbitraire tout en restant &quot;collé&quot; à son contour&lt;/li&gt;<br /> &lt;li&gt;Chaque mouvement est ajouté à une chaine de caractère sous forme de chiffre. ''(0 pour la droite, 1 pour le bas, ...)''&lt;/li&gt;<br /> &lt;li&gt;Dès qu'on retombe sur le point de départ de la figure, on a généré le mot de contour ayant 4 lettres : 0,1,2 et 3 pour chacun des mouvements.&lt;/li&gt;<br /> &lt;/ul&gt;<br /> <br /> Note : Un mot de contour n'est donc pas unique, il dépend de là où on commence le parcours de la figure.<br /> <br /> == Détection de droite discrète ==<br /> <br /> La détection de la pente d'une droite discrète à partir d'un mot de Christoffel passe par un algorithme plus complexe que celui permettant de faire son opposé.[[Titre du lien]]</div>

Jdubois http://os-vps418.infomaniak.ch:1250/mediawiki/index.php?title=G%C3%A9om%C3%A9trie_discr%C3%A8te,_Convexit%C3%A9_des_polyominos,_Combinatoire_des_mots&diff=14249 2022-05-29T19:41:36Z

<p>Jdubois : /* Algorithme de génération */</p> <hr /> <div>Les images numérisées sont constituées de pixels, de petits carrés de couleurs. Les formes dans ces images ont alors une forme très particulière puisqu'il n'y a que quatres chemins possibles. Impossible d'aller en diagonale ou avec un angle particulier, les points n'ont que des coordonnées entières. &lt;br/&gt;<br /> On peut alors retrouver les éléments de la géométrie Euclidienne classique dans Z² via un outil : '''les mots de Christoffel.''' &lt;br/&gt;<br /> Cet outil permet de discrétiser des droites dans Z² afin de trouver la pente de celles-ci avec pour but d'appliquer les calculs de la géométrie Euclidienne.<br /> <br /> ----<br /> <br /> == Mot de Christoffel ==<br /> <br /> On prend une droite de pente p/q et on veut dessiner une droite discrète de celle-ci en connectant des points de coordonnées entières dans Z².&lt;br/&gt;<br /> On peut décrire cette droite comme &quot;''commençant''&quot; au point de coordonnée (0,0), passant par le point (p,q) et n'ayant que deux choix de mouvements :<br /> &lt;ul&gt;<br /> &lt;li&gt;X pour se déplacer d'une unité à droite sur l'axe des abscisses.&lt;/li&gt;<br /> &lt;li&gt;Y pour se déplacer d'une unité en haut sur l'axe des ordonnées.&lt;/li&gt;<br /> &lt;/ul&gt;<br /> Ainsi par exemple, on peut discrétiser la pente 2/3 en faisant les mouvements '''[x,x,x,y,y]''' ou '''[y,y,x,x,x]'''.<br /> <br /> Un mot de Christoffel se base sur le même principe hormis qu'il va essayer de toujours être le plus proche possible de la ligne sans jamais la traverser.<br /> <br /> [[Fichier:74.jpg]]<br /> <br /> ''Mot de Christoffel &quot;bas&quot; [x,x,y,x,x,y,x,x,y,x,y] et &quot;haut&quot; [y,x,y,x,x,y,x,x,y,x,x] de la droite de pente 4/7.''<br /> <br /> '''Note''' : ''Le mot de Christoffel &quot;haut&quot; est le mot de Christoffel &quot;bas&quot; lu à l'envers.''&lt;br/&gt;<br /> '''Note 2''' : ''Si on retire la première et la dernière lettre d'un mot de Christoffel, on obtient un palindrome (lisible dans les deux sens)''<br /> '''Note 3''' : ''La première et la dernière lettre d'un mot de Christoffel sont forcément différentes.''<br /> <br /> === Algorithme de génération ===<br /> <br /> Il est possible de générer facilement et très rapidement le mot de Christoffel d'une pente grâce à une méthode simple :<br /> <br /> La suite U définie par : &lt;math&gt;U0 = 0 | Un+1= (Un+a) [a+b]&lt;/math&gt; donnera une suite de chiffre qui se répète.&lt;br/&gt;<br /> Si Un &gt; Un+1, on ajoute un x au mot, sinon on ajoute un y au mot.<br /> <br /> On applique cette méthode jusqu'à ce que Un+1 = 0 pour avoir le mot de Christoffel de la pente.<br /> <br /> ==== Exemple ====<br /> Avec une pente de 5/7, on obtient : &lt;br/&gt;<br /> 0 5 10 3 8 1 6 11 4 9 2 7 0&lt;br/&gt;<br /> Soit en appliquant la méthode : x x y x y x x y x y x y&lt;br/&gt;<br /> On retrouve bien le mot de Christoffel de la pente 5/7 : [x,x,y,x,y,x,x,y,x,y,x,y]<br /> <br /> ==== Implémentation Python ====<br /> [[Fichier:Algo.png]]<br /> <br /> == Mot de contour ==<br /> <br /> On peut définir un mot de contour comme un ensemble de mot de Christoffel étant orientés différemment les uns des autres.&lt;br/&gt;<br /> Dans le cadre du module visi201, j'ai utilisé un algorithme pour le générer ayant le principe suivant :<br /> &lt;ul&gt;<br /> &lt;li&gt;On considère en entrée une forme '''convexe''' noire sur un fond blanc.&lt;/li&gt;<br /> &lt;li&gt;On crée une matrice avec la couleur de chaque pixel, c'est cette matrice qu'on traitera par la suite.&lt;/li&gt;<br /> &lt;li&gt;On choisit deux points aléatoires jusqu'à ce qu'un d'eux soit noir et l'autre blanc.&lt;/li&gt;<br /> &lt;li&gt;On applique le principe de dichotomie jusqu'à trouver un point étant le contour de la figure&lt;/li&gt;<br /> &lt;li&gt;On parcourt la figure dans un sens arbitraire tout en restant &quot;collé&quot; à son contour&lt;/li&gt;<br /> &lt;li&gt;Chaque mouvement est ajouté à une chaine de caractère sous forme de chiffre. ''(0 pour la droite, 1 pour le bas, ...)''&lt;/li&gt;<br /> &lt;li&gt;Dès qu'on retombe sur le point de départ de la figure, on a généré le mot de contour ayant 4 lettres : 0,1,2 et 3 pour chacun des mouvements.&lt;/li&gt;<br /> &lt;/ul&gt;<br /> <br /> Note : Un mot de contour n'est donc pas unique, il dépend de là où on commence le parcours de la figure.<br /> <br /> == Détection de droite discrète ==</div>

Jdubois http://os-vps418.infomaniak.ch:1250/mediawiki/index.php?title=G%C3%A9om%C3%A9trie_discr%C3%A8te,_Convexit%C3%A9_des_polyominos,_Combinatoire_des_mots&diff=14248 2022-05-29T19:41:13Z

<p>Jdubois : /* Algorithme de génération */</p> <hr /> <div>Les images numérisées sont constituées de pixels, de petits carrés de couleurs. Les formes dans ces images ont alors une forme très particulière puisqu'il n'y a que quatres chemins possibles. Impossible d'aller en diagonale ou avec un angle particulier, les points n'ont que des coordonnées entières. &lt;br/&gt;<br /> On peut alors retrouver les éléments de la géométrie Euclidienne classique dans Z² via un outil : '''les mots de Christoffel.''' &lt;br/&gt;<br /> Cet outil permet de discrétiser des droites dans Z² afin de trouver la pente de celles-ci avec pour but d'appliquer les calculs de la géométrie Euclidienne.<br /> <br /> ----<br /> <br /> == Mot de Christoffel ==<br /> <br /> On prend une droite de pente p/q et on veut dessiner une droite discrète de celle-ci en connectant des points de coordonnées entières dans Z².&lt;br/&gt;<br /> On peut décrire cette droite comme &quot;''commençant''&quot; au point de coordonnée (0,0), passant par le point (p,q) et n'ayant que deux choix de mouvements :<br /> &lt;ul&gt;<br /> &lt;li&gt;X pour se déplacer d'une unité à droite sur l'axe des abscisses.&lt;/li&gt;<br /> &lt;li&gt;Y pour se déplacer d'une unité en haut sur l'axe des ordonnées.&lt;/li&gt;<br /> &lt;/ul&gt;<br /> Ainsi par exemple, on peut discrétiser la pente 2/3 en faisant les mouvements '''[x,x,x,y,y]''' ou '''[y,y,x,x,x]'''.<br /> <br /> Un mot de Christoffel se base sur le même principe hormis qu'il va essayer de toujours être le plus proche possible de la ligne sans jamais la traverser.<br /> <br /> [[Fichier:74.jpg]]<br /> <br /> ''Mot de Christoffel &quot;bas&quot; [x,x,y,x,x,y,x,x,y,x,y] et &quot;haut&quot; [y,x,y,x,x,y,x,x,y,x,x] de la droite de pente 4/7.''<br /> <br /> '''Note''' : ''Le mot de Christoffel &quot;haut&quot; est le mot de Christoffel &quot;bas&quot; lu à l'envers.''&lt;br/&gt;<br /> '''Note 2''' : ''Si on retire la première et la dernière lettre d'un mot de Christoffel, on obtient un palindrome (lisible dans les deux sens)''<br /> '''Note 3''' : ''La première et la dernière lettre d'un mot de Christoffel sont forcément différentes.''<br /> <br /> === Algorithme de génération ===<br /> <br /> Il est possible de générer facilement et très rapidement le mot de Christoffel d'une pente grâce à une méthode simple :<br /> <br /> La suite &lt;math&gt;U0 = 0 | Un+1= (Un+a) [a+b]&lt;/math&gt; donnera une suite de chiffre qui se répète.&lt;br/&gt;<br /> Si Un &gt; Un+1, on ajoute un x au mot, sinon on ajoute un y au mot.<br /> <br /> On applique cette méthode jusqu'à ce que Un+1 = 0 pour avoir le mot de Christoffel de la pente.<br /> <br /> ==== Exemple ====<br /> Avec une pente de 5/7, on obtient : &lt;br/&gt;<br /> 0 5 10 3 8 1 6 11 4 9 2 7 0&lt;br/&gt;<br /> Soit en appliquant la méthode : x x y x y x x y x y x y&lt;br/&gt;<br /> On retrouve bien le mot de Christoffel de la pente 5/7 : [x,x,y,x,y,x,x,y,x,y,x,y]<br /> <br /> ==== Implémentation Python ====<br /> [[Fichier:Algo.png]]<br /> <br /> == Mot de contour ==<br /> <br /> On peut définir un mot de contour comme un ensemble de mot de Christoffel étant orientés différemment les uns des autres.&lt;br/&gt;<br /> Dans le cadre du module visi201, j'ai utilisé un algorithme pour le générer ayant le principe suivant :<br /> &lt;ul&gt;<br /> &lt;li&gt;On considère en entrée une forme '''convexe''' noire sur un fond blanc.&lt;/li&gt;<br /> &lt;li&gt;On crée une matrice avec la couleur de chaque pixel, c'est cette matrice qu'on traitera par la suite.&lt;/li&gt;<br /> &lt;li&gt;On choisit deux points aléatoires jusqu'à ce qu'un d'eux soit noir et l'autre blanc.&lt;/li&gt;<br /> &lt;li&gt;On applique le principe de dichotomie jusqu'à trouver un point étant le contour de la figure&lt;/li&gt;<br /> &lt;li&gt;On parcourt la figure dans un sens arbitraire tout en restant &quot;collé&quot; à son contour&lt;/li&gt;<br /> &lt;li&gt;Chaque mouvement est ajouté à une chaine de caractère sous forme de chiffre. ''(0 pour la droite, 1 pour le bas, ...)''&lt;/li&gt;<br /> &lt;li&gt;Dès qu'on retombe sur le point de départ de la figure, on a généré le mot de contour ayant 4 lettres : 0,1,2 et 3 pour chacun des mouvements.&lt;/li&gt;<br /> &lt;/ul&gt;<br /> <br /> Note : Un mot de contour n'est donc pas unique, il dépend de là où on commence le parcours de la figure.<br /> <br /> == Détection de droite discrète ==</div>

Jdubois http://os-vps418.infomaniak.ch:1250/mediawiki/index.php?title=G%C3%A9om%C3%A9trie_discr%C3%A8te,_Convexit%C3%A9_des_polyominos,_Combinatoire_des_mots&diff=14247 2022-05-29T19:40:48Z

<p>Jdubois : /* Exemple */</p> <hr /> <div>Les images numérisées sont constituées de pixels, de petits carrés de couleurs. Les formes dans ces images ont alors une forme très particulière puisqu'il n'y a que quatres chemins possibles. Impossible d'aller en diagonale ou avec un angle particulier, les points n'ont que des coordonnées entières. &lt;br/&gt;<br /> On peut alors retrouver les éléments de la géométrie Euclidienne classique dans Z² via un outil : '''les mots de Christoffel.''' &lt;br/&gt;<br /> Cet outil permet de discrétiser des droites dans Z² afin de trouver la pente de celles-ci avec pour but d'appliquer les calculs de la géométrie Euclidienne.<br /> <br /> ----<br /> <br /> == Mot de Christoffel ==<br /> <br /> On prend une droite de pente p/q et on veut dessiner une droite discrète de celle-ci en connectant des points de coordonnées entières dans Z².&lt;br/&gt;<br /> On peut décrire cette droite comme &quot;''commençant''&quot; au point de coordonnée (0,0), passant par le point (p,q) et n'ayant que deux choix de mouvements :<br /> &lt;ul&gt;<br /> &lt;li&gt;X pour se déplacer d'une unité à droite sur l'axe des abscisses.&lt;/li&gt;<br /> &lt;li&gt;Y pour se déplacer d'une unité en haut sur l'axe des ordonnées.&lt;/li&gt;<br /> &lt;/ul&gt;<br /> Ainsi par exemple, on peut discrétiser la pente 2/3 en faisant les mouvements '''[x,x,x,y,y]''' ou '''[y,y,x,x,x]'''.<br /> <br /> Un mot de Christoffel se base sur le même principe hormis qu'il va essayer de toujours être le plus proche possible de la ligne sans jamais la traverser.<br /> <br /> [[Fichier:74.jpg]]<br /> <br /> ''Mot de Christoffel &quot;bas&quot; [x,x,y,x,x,y,x,x,y,x,y] et &quot;haut&quot; [y,x,y,x,x,y,x,x,y,x,x] de la droite de pente 4/7.''<br /> <br /> '''Note''' : ''Le mot de Christoffel &quot;haut&quot; est le mot de Christoffel &quot;bas&quot; lu à l'envers.''&lt;br/&gt;<br /> '''Note 2''' : ''Si on retire la première et la dernière lettre d'un mot de Christoffel, on obtient un palindrome (lisible dans les deux sens)''<br /> '''Note 3''' : ''La première et la dernière lettre d'un mot de Christoffel sont forcément différentes.''<br /> <br /> === Algorithme de génération ===<br /> <br /> Il est possible de générer facilement et très rapidement le mot de Christoffel d'une pente grâce à une méthode simple :<br /> <br /> La suite &lt;math&gt;U0 = 0 | Un+1=Un+a [a+b]&lt;/math&gt; donnera une suite de chiffre qui se répète.&lt;br/&gt;<br /> Si Un &gt; Un+1, on ajoute un x au mot, sinon on ajoute un y au mot.<br /> <br /> On applique cette méthode jusqu'à ce que Un+1 = 0 pour avoir le mot de Christoffel de la pente.<br /> <br /> ==== Exemple ====<br /> Avec une pente de 5/7, on obtient : &lt;br/&gt;<br /> 0 5 10 3 8 1 6 11 4 9 2 7 0&lt;br/&gt;<br /> Soit en appliquant la méthode : x x y x y x x y x y x y&lt;br/&gt;<br /> On retrouve bien le mot de Christoffel de la pente 5/7 : [x,x,y,x,y,x,x,y,x,y,x,y]<br /> <br /> ==== Implémentation Python ====<br /> [[Fichier:Algo.png]]<br /> <br /> == Mot de contour ==<br /> <br /> On peut définir un mot de contour comme un ensemble de mot de Christoffel étant orientés différemment les uns des autres.&lt;br/&gt;<br /> Dans le cadre du module visi201, j'ai utilisé un algorithme pour le générer ayant le principe suivant :<br /> &lt;ul&gt;<br /> &lt;li&gt;On considère en entrée une forme '''convexe''' noire sur un fond blanc.&lt;/li&gt;<br /> &lt;li&gt;On crée une matrice avec la couleur de chaque pixel, c'est cette matrice qu'on traitera par la suite.&lt;/li&gt;<br /> &lt;li&gt;On choisit deux points aléatoires jusqu'à ce qu'un d'eux soit noir et l'autre blanc.&lt;/li&gt;<br /> &lt;li&gt;On applique le principe de dichotomie jusqu'à trouver un point étant le contour de la figure&lt;/li&gt;<br /> &lt;li&gt;On parcourt la figure dans un sens arbitraire tout en restant &quot;collé&quot; à son contour&lt;/li&gt;<br /> &lt;li&gt;Chaque mouvement est ajouté à une chaine de caractère sous forme de chiffre. ''(0 pour la droite, 1 pour le bas, ...)''&lt;/li&gt;<br /> &lt;li&gt;Dès qu'on retombe sur le point de départ de la figure, on a généré le mot de contour ayant 4 lettres : 0,1,2 et 3 pour chacun des mouvements.&lt;/li&gt;<br /> &lt;/ul&gt;<br /> <br /> Note : Un mot de contour n'est donc pas unique, il dépend de là où on commence le parcours de la figure.<br /> <br /> == Détection de droite discrète ==</div>

Jdubois http://os-vps418.infomaniak.ch:1250/mediawiki/index.php?title=G%C3%A9om%C3%A9trie_discr%C3%A8te,_Convexit%C3%A9_des_polyominos,_Combinatoire_des_mots&diff=14246 2022-05-29T19:40:29Z

<p>Jdubois : /* Exemple */</p> <hr /> <div>Les images numérisées sont constituées de pixels, de petits carrés de couleurs. Les formes dans ces images ont alors une forme très particulière puisqu'il n'y a que quatres chemins possibles. Impossible d'aller en diagonale ou avec un angle particulier, les points n'ont que des coordonnées entières. &lt;br/&gt;<br /> On peut alors retrouver les éléments de la géométrie Euclidienne classique dans Z² via un outil : '''les mots de Christoffel.''' &lt;br/&gt;<br /> Cet outil permet de discrétiser des droites dans Z² afin de trouver la pente de celles-ci avec pour but d'appliquer les calculs de la géométrie Euclidienne.<br /> <br /> ----<br /> <br /> == Mot de Christoffel ==<br /> <br /> On prend une droite de pente p/q et on veut dessiner une droite discrète de celle-ci en connectant des points de coordonnées entières dans Z².&lt;br/&gt;<br /> On peut décrire cette droite comme &quot;''commençant''&quot; au point de coordonnée (0,0), passant par le point (p,q) et n'ayant que deux choix de mouvements :<br /> &lt;ul&gt;<br /> &lt;li&gt;X pour se déplacer d'une unité à droite sur l'axe des abscisses.&lt;/li&gt;<br /> &lt;li&gt;Y pour se déplacer d'une unité en haut sur l'axe des ordonnées.&lt;/li&gt;<br /> &lt;/ul&gt;<br /> Ainsi par exemple, on peut discrétiser la pente 2/3 en faisant les mouvements '''[x,x,x,y,y]''' ou '''[y,y,x,x,x]'''.<br /> <br /> Un mot de Christoffel se base sur le même principe hormis qu'il va essayer de toujours être le plus proche possible de la ligne sans jamais la traverser.<br /> <br /> [[Fichier:74.jpg]]<br /> <br /> ''Mot de Christoffel &quot;bas&quot; [x,x,y,x,x,y,x,x,y,x,y] et &quot;haut&quot; [y,x,y,x,x,y,x,x,y,x,x] de la droite de pente 4/7.''<br /> <br /> '''Note''' : ''Le mot de Christoffel &quot;haut&quot; est le mot de Christoffel &quot;bas&quot; lu à l'envers.''&lt;br/&gt;<br /> '''Note 2''' : ''Si on retire la première et la dernière lettre d'un mot de Christoffel, on obtient un palindrome (lisible dans les deux sens)''<br /> '''Note 3''' : ''La première et la dernière lettre d'un mot de Christoffel sont forcément différentes.''<br /> <br /> === Algorithme de génération ===<br /> <br /> Il est possible de générer facilement et très rapidement le mot de Christoffel d'une pente grâce à une méthode simple :<br /> <br /> La suite &lt;math&gt;U0 = 0 | Un+1=Un+a [a+b]&lt;/math&gt; donnera une suite de chiffre qui se répète.&lt;br/&gt;<br /> Si Un &gt; Un+1, on ajoute un x au mot, sinon on ajoute un y au mot.<br /> <br /> On applique cette méthode jusqu'à ce que Un+1 = 0 pour avoir le mot de Christoffel de la pente.<br /> <br /> ==== Exemple ====<br /> Avec une pente de 5/7, on obtient : &lt;br/&gt;<br /> 0 5 10 3 8 1 6 11 4 9 2 7 0&lt;br/&gt;<br /> Soit : x x y x y x x y x y x y&lt;br/&gt;<br /> On retrouve bien le mot de Christoffel de la pente 5/7 : [x,x,y,x,y,x,x,y,x,y,x,y]<br /> <br /> ==== Implémentation Python ====<br /> [[Fichier:Algo.png]]<br /> <br /> == Mot de contour ==<br /> <br /> On peut définir un mot de contour comme un ensemble de mot de Christoffel étant orientés différemment les uns des autres.&lt;br/&gt;<br /> Dans le cadre du module visi201, j'ai utilisé un algorithme pour le générer ayant le principe suivant :<br /> &lt;ul&gt;<br /> &lt;li&gt;On considère en entrée une forme '''convexe''' noire sur un fond blanc.&lt;/li&gt;<br /> &lt;li&gt;On crée une matrice avec la couleur de chaque pixel, c'est cette matrice qu'on traitera par la suite.&lt;/li&gt;<br /> &lt;li&gt;On choisit deux points aléatoires jusqu'à ce qu'un d'eux soit noir et l'autre blanc.&lt;/li&gt;<br /> &lt;li&gt;On applique le principe de dichotomie jusqu'à trouver un point étant le contour de la figure&lt;/li&gt;<br /> &lt;li&gt;On parcourt la figure dans un sens arbitraire tout en restant &quot;collé&quot; à son contour&lt;/li&gt;<br /> &lt;li&gt;Chaque mouvement est ajouté à une chaine de caractère sous forme de chiffre. ''(0 pour la droite, 1 pour le bas, ...)''&lt;/li&gt;<br /> &lt;li&gt;Dès qu'on retombe sur le point de départ de la figure, on a généré le mot de contour ayant 4 lettres : 0,1,2 et 3 pour chacun des mouvements.&lt;/li&gt;<br /> &lt;/ul&gt;<br /> <br /> Note : Un mot de contour n'est donc pas unique, il dépend de là où on commence le parcours de la figure.<br /> <br /> == Détection de droite discrète ==</div>

Jdubois http://os-vps418.infomaniak.ch:1250/mediawiki/index.php?title=G%C3%A9om%C3%A9trie_discr%C3%A8te,_Convexit%C3%A9_des_polyominos,_Combinatoire_des_mots&diff=14245 2022-05-29T19:40:16Z

<p>Jdubois : /* Exemple */</p> <hr /> <div>Les images numérisées sont constituées de pixels, de petits carrés de couleurs. Les formes dans ces images ont alors une forme très particulière puisqu'il n'y a que quatres chemins possibles. Impossible d'aller en diagonale ou avec un angle particulier, les points n'ont que des coordonnées entières. &lt;br/&gt;<br /> On peut alors retrouver les éléments de la géométrie Euclidienne classique dans Z² via un outil : '''les mots de Christoffel.''' &lt;br/&gt;<br /> Cet outil permet de discrétiser des droites dans Z² afin de trouver la pente de celles-ci avec pour but d'appliquer les calculs de la géométrie Euclidienne.<br /> <br /> ----<br /> <br /> == Mot de Christoffel ==<br /> <br /> On prend une droite de pente p/q et on veut dessiner une droite discrète de celle-ci en connectant des points de coordonnées entières dans Z².&lt;br/&gt;<br /> On peut décrire cette droite comme &quot;''commençant''&quot; au point de coordonnée (0,0), passant par le point (p,q) et n'ayant que deux choix de mouvements :<br /> &lt;ul&gt;<br /> &lt;li&gt;X pour se déplacer d'une unité à droite sur l'axe des abscisses.&lt;/li&gt;<br /> &lt;li&gt;Y pour se déplacer d'une unité en haut sur l'axe des ordonnées.&lt;/li&gt;<br /> &lt;/ul&gt;<br /> Ainsi par exemple, on peut discrétiser la pente 2/3 en faisant les mouvements '''[x,x,x,y,y]''' ou '''[y,y,x,x,x]'''.<br /> <br /> Un mot de Christoffel se base sur le même principe hormis qu'il va essayer de toujours être le plus proche possible de la ligne sans jamais la traverser.<br /> <br /> [[Fichier:74.jpg]]<br /> <br /> ''Mot de Christoffel &quot;bas&quot; [x,x,y,x,x,y,x,x,y,x,y] et &quot;haut&quot; [y,x,y,x,x,y,x,x,y,x,x] de la droite de pente 4/7.''<br /> <br /> '''Note''' : ''Le mot de Christoffel &quot;haut&quot; est le mot de Christoffel &quot;bas&quot; lu à l'envers.''&lt;br/&gt;<br /> '''Note 2''' : ''Si on retire la première et la dernière lettre d'un mot de Christoffel, on obtient un palindrome (lisible dans les deux sens)''<br /> '''Note 3''' : ''La première et la dernière lettre d'un mot de Christoffel sont forcément différentes.''<br /> <br /> === Algorithme de génération ===<br /> <br /> Il est possible de générer facilement et très rapidement le mot de Christoffel d'une pente grâce à une méthode simple :<br /> <br /> La suite &lt;math&gt;U0 = 0 | Un+1=Un+a [a+b]&lt;/math&gt; donnera une suite de chiffre qui se répète.&lt;br/&gt;<br /> Si Un &gt; Un+1, on ajoute un x au mot, sinon on ajoute un y au mot.<br /> <br /> On applique cette méthode jusqu'à ce que Un+1 = 0 pour avoir le mot de Christoffel de la pente.<br /> <br /> ==== Exemple ====<br /> Avec une pente de 5/7, on obtient : &lt;br/&gt;<br /> 0 5 10 3 8 1 6 11 4 9 2 7 0&lt;br/&gt;<br /> Soit :&lt;br/&gt;<br /> x x y x y x x y x y x y&lt;br/&gt;<br /> On retrouve bien le mot de Christoffel de la pente 5/7 : [x,x,y,x,y,x,x,y,x,y,x,y]<br /> <br /> ==== Implémentation Python ====<br /> [[Fichier:Algo.png]]<br /> <br /> == Mot de contour ==<br /> <br /> On peut définir un mot de contour comme un ensemble de mot de Christoffel étant orientés différemment les uns des autres.&lt;br/&gt;<br /> Dans le cadre du module visi201, j'ai utilisé un algorithme pour le générer ayant le principe suivant :<br /> &lt;ul&gt;<br /> &lt;li&gt;On considère en entrée une forme '''convexe''' noire sur un fond blanc.&lt;/li&gt;<br /> &lt;li&gt;On crée une matrice avec la couleur de chaque pixel, c'est cette matrice qu'on traitera par la suite.&lt;/li&gt;<br /> &lt;li&gt;On choisit deux points aléatoires jusqu'à ce qu'un d'eux soit noir et l'autre blanc.&lt;/li&gt;<br /> &lt;li&gt;On applique le principe de dichotomie jusqu'à trouver un point étant le contour de la figure&lt;/li&gt;<br /> &lt;li&gt;On parcourt la figure dans un sens arbitraire tout en restant &quot;collé&quot; à son contour&lt;/li&gt;<br /> &lt;li&gt;Chaque mouvement est ajouté à une chaine de caractère sous forme de chiffre. ''(0 pour la droite, 1 pour le bas, ...)''&lt;/li&gt;<br /> &lt;li&gt;Dès qu'on retombe sur le point de départ de la figure, on a généré le mot de contour ayant 4 lettres : 0,1,2 et 3 pour chacun des mouvements.&lt;/li&gt;<br /> &lt;/ul&gt;<br /> <br /> Note : Un mot de contour n'est donc pas unique, il dépend de là où on commence le parcours de la figure.<br /> <br /> == Détection de droite discrète ==</div>

Jdubois http://os-vps418.infomaniak.ch:1250/mediawiki/index.php?title=G%C3%A9om%C3%A9trie_discr%C3%A8te,_Convexit%C3%A9_des_polyominos,_Combinatoire_des_mots&diff=14244 2022-05-29T19:39:41Z

<p>Jdubois : /* Mot de contour */</p> <hr /> <div>Les images numérisées sont constituées de pixels, de petits carrés de couleurs. Les formes dans ces images ont alors une forme très particulière puisqu'il n'y a que quatres chemins possibles. Impossible d'aller en diagonale ou avec un angle particulier, les points n'ont que des coordonnées entières. &lt;br/&gt;<br /> On peut alors retrouver les éléments de la géométrie Euclidienne classique dans Z² via un outil : '''les mots de Christoffel.''' &lt;br/&gt;<br /> Cet outil permet de discrétiser des droites dans Z² afin de trouver la pente de celles-ci avec pour but d'appliquer les calculs de la géométrie Euclidienne.<br /> <br /> ----<br /> <br /> == Mot de Christoffel ==<br /> <br /> On prend une droite de pente p/q et on veut dessiner une droite discrète de celle-ci en connectant des points de coordonnées entières dans Z².&lt;br/&gt;<br /> On peut décrire cette droite comme &quot;''commençant''&quot; au point de coordonnée (0,0), passant par le point (p,q) et n'ayant que deux choix de mouvements :<br /> &lt;ul&gt;<br /> &lt;li&gt;X pour se déplacer d'une unité à droite sur l'axe des abscisses.&lt;/li&gt;<br /> &lt;li&gt;Y pour se déplacer d'une unité en haut sur l'axe des ordonnées.&lt;/li&gt;<br /> &lt;/ul&gt;<br /> Ainsi par exemple, on peut discrétiser la pente 2/3 en faisant les mouvements '''[x,x,x,y,y]''' ou '''[y,y,x,x,x]'''.<br /> <br /> Un mot de Christoffel se base sur le même principe hormis qu'il va essayer de toujours être le plus proche possible de la ligne sans jamais la traverser.<br /> <br /> [[Fichier:74.jpg]]<br /> <br /> ''Mot de Christoffel &quot;bas&quot; [x,x,y,x,x,y,x,x,y,x,y] et &quot;haut&quot; [y,x,y,x,x,y,x,x,y,x,x] de la droite de pente 4/7.''<br /> <br /> '''Note''' : ''Le mot de Christoffel &quot;haut&quot; est le mot de Christoffel &quot;bas&quot; lu à l'envers.''&lt;br/&gt;<br /> '''Note 2''' : ''Si on retire la première et la dernière lettre d'un mot de Christoffel, on obtient un palindrome (lisible dans les deux sens)''<br /> '''Note 3''' : ''La première et la dernière lettre d'un mot de Christoffel sont forcément différentes.''<br /> <br /> === Algorithme de génération ===<br /> <br /> Il est possible de générer facilement et très rapidement le mot de Christoffel d'une pente grâce à une méthode simple :<br /> <br /> La suite &lt;math&gt;U0 = 0 | Un+1=Un+a [a+b]&lt;/math&gt; donnera une suite de chiffre qui se répète.&lt;br/&gt;<br /> Si Un &gt; Un+1, on ajoute un x au mot, sinon on ajoute un y au mot.<br /> <br /> On applique cette méthode jusqu'à ce que Un+1 = 0 pour avoir le mot de Christoffel de la pente.<br /> <br /> ==== Exemple ====<br /> Avec une pente de 5/7, on obtient : <br /> 0 5 10 3 8 1 6 11 4 9 2 7 0<br /> Soit :<br /> x x y x y x x y x y x y<br /> On retrouve bien le mot de Christoffel de la pente 5/7 : [x,x,y,x,y,x,x,y,x,y,x,y]<br /> <br /> ==== Implémentation Python ====<br /> [[Fichier:Algo.png]]<br /> <br /> == Mot de contour ==<br /> <br /> On peut définir un mot de contour comme un ensemble de mot de Christoffel étant orientés différemment les uns des autres.&lt;br/&gt;<br /> Dans le cadre du module visi201, j'ai utilisé un algorithme pour le générer ayant le principe suivant :<br /> &lt;ul&gt;<br /> &lt;li&gt;On considère en entrée une forme '''convexe''' noire sur un fond blanc.&lt;/li&gt;<br /> &lt;li&gt;On crée une matrice avec la couleur de chaque pixel, c'est cette matrice qu'on traitera par la suite.&lt;/li&gt;<br /> &lt;li&gt;On choisit deux points aléatoires jusqu'à ce qu'un d'eux soit noir et l'autre blanc.&lt;/li&gt;<br /> &lt;li&gt;On applique le principe de dichotomie jusqu'à trouver un point étant le contour de la figure&lt;/li&gt;<br /> &lt;li&gt;On parcourt la figure dans un sens arbitraire tout en restant &quot;collé&quot; à son contour&lt;/li&gt;<br /> &lt;li&gt;Chaque mouvement est ajouté à une chaine de caractère sous forme de chiffre. ''(0 pour la droite, 1 pour le bas, ...)''&lt;/li&gt;<br /> &lt;li&gt;Dès qu'on retombe sur le point de départ de la figure, on a généré le mot de contour ayant 4 lettres : 0,1,2 et 3 pour chacun des mouvements.&lt;/li&gt;<br /> &lt;/ul&gt;<br /> <br /> Note : Un mot de contour n'est donc pas unique, il dépend de là où on commence le parcours de la figure.<br /> <br /> == Détection de droite discrète ==</div>

Jdubois http://os-vps418.infomaniak.ch:1250/mediawiki/index.php?title=G%C3%A9om%C3%A9trie_discr%C3%A8te,_Convexit%C3%A9_des_polyominos,_Combinatoire_des_mots&diff=14152 2022-05-29T13:14:14Z

<p>Jdubois : /* Mot de Christoffel */</p> <hr /> <div>Les images numérisées sont constituées de pixels, de petits carrés de couleurs. Les formes dans ces images ont alors une forme très particulière puisqu'il n'y a que quatres chemins possibles. Impossible d'aller en diagonale ou avec un angle particulier, les points n'ont que des coordonnées entières. &lt;br/&gt;<br /> On peut alors retrouver les éléments de la géométrie Euclidienne classique dans Z² via un outil : '''les mots de Christoffel.''' &lt;br/&gt;<br /> Cet outil permet de discrétiser des droites dans Z² afin de trouver la pente de celles-ci avec pour but d'appliquer les calculs de la géométrie Euclidienne.<br /> <br /> ----<br /> <br /> == Mot de Christoffel ==<br /> <br /> On prend une droite de pente p/q et on veut dessiner une droite discrète de celle-ci en connectant des points de coordonnées entières dans Z².&lt;br/&gt;<br /> On peut décrire cette droite comme &quot;''commençant''&quot; au point de coordonnée (0,0), passant par le point (p,q) et n'ayant que deux choix de mouvements :<br /> &lt;ul&gt;<br /> &lt;li&gt;X pour se déplacer d'une unité à droite sur l'axe des abscisses.&lt;/li&gt;<br /> &lt;li&gt;Y pour se déplacer d'une unité en haut sur l'axe des ordonnées.&lt;/li&gt;<br /> &lt;/ul&gt;<br /> Ainsi par exemple, on peut discrétiser la pente 2/3 en faisant les mouvements '''[x,x,x,y,y]''' ou '''[y,y,x,x,x]'''.<br /> <br /> Un mot de Christoffel se base sur le même principe hormis qu'il va essayer de toujours être le plus proche possible de la ligne sans jamais la traverser.<br /> <br /> [[Fichier:74.jpg]]<br /> <br /> ''Mot de Christoffel &quot;bas&quot; [x,x,y,x,x,y,x,x,y,x,y] et &quot;haut&quot; [y,x,y,x,x,y,x,x,y,x,x] de la droite de pente 4/7.''<br /> <br /> '''Note''' : ''Le mot de Christoffel &quot;haut&quot; est le mot de Christoffel &quot;bas&quot; lu à l'envers.''&lt;br/&gt;<br /> '''Note 2''' : ''Si on retire la première et la dernière lettre d'un mot de Christoffel, on obtient un palindrome (lisible dans les deux sens)''<br /> '''Note 3''' : ''La première et la dernière lettre d'un mot de Christoffel sont forcément différentes.''<br /> <br /> === Algorithme de génération ===<br /> <br /> Il est possible de générer facilement et très rapidement le mot de Christoffel d'une pente grâce à une méthode simple :<br /> <br /> La suite &lt;math&gt;U0 = 0 | Un+1=Un+a [a+b]&lt;/math&gt; donnera une suite de chiffre qui se répète.&lt;br/&gt;<br /> Si Un &gt; Un+1, on ajoute un x au mot, sinon on ajoute un y au mot.<br /> <br /> On applique cette méthode jusqu'à ce que Un+1 = 0 pour avoir le mot de Christoffel de la pente.<br /> <br /> ==== Exemple ====<br /> Avec une pente de 5/7, on obtient : <br /> 0 5 10 3 8 1 6 11 4 9 2 7 0<br /> Soit :<br /> x x y x y x x y x y x y<br /> On retrouve bien le mot de Christoffel de la pente 5/7 : [x,x,y,x,y,x,x,y,x,y,x,y]<br /> <br /> ==== Implémentation Python ====<br /> [[Fichier:Algo.png]]<br /> <br /> == Mot de contour ==<br /> <br /> == Détection de droite discrète ==</div>

Jdubois http://os-vps418.infomaniak.ch:1250/mediawiki/index.php?title=G%C3%A9om%C3%A9trie_discr%C3%A8te,_Convexit%C3%A9_des_polyominos,_Combinatoire_des_mots&diff=14151 2022-05-29T13:11:49Z

<p>Jdubois : /* Implémentation Python */</p> <hr /> <div>Les images numérisées sont constituées de pixels, de petits carrés de couleurs. Les formes dans ces images ont alors une forme très particulière puisqu'il n'y a que quatres chemins possibles. Impossible d'aller en diagonale ou avec un angle particulier, les points n'ont que des coordonnées entières. &lt;br/&gt;<br /> On peut alors retrouver les éléments de la géométrie Euclidienne classique dans Z² via un outil : '''les mots de Christoffel.''' &lt;br/&gt;<br /> Cet outil permet de discrétiser des droites dans Z² afin de trouver la pente de celles-ci avec pour but d'appliquer les calculs de la géométrie Euclidienne.<br /> <br /> ----<br /> <br /> == Mot de Christoffel ==<br /> <br /> On prend une droite de pente p/q et on veut dessiner une droite discrète de celle-ci en connectant des points de coordonnées entières dans Z².&lt;br/&gt;<br /> On peut décrire cette droite comme &quot;''commençant''&quot; au point de coordonnée (0,0), passant par le point (p,q) et n'ayant que deux choix de mouvements :<br /> &lt;ul&gt;<br /> &lt;li&gt;X pour se déplacer d'une unité à droite sur l'axe des abscisses.&lt;/li&gt;<br /> &lt;li&gt;Y pour se déplacer d'une unité en haut sur l'axe des ordonnées.&lt;/li&gt;<br /> &lt;/ul&gt;<br /> Ainsi par exemple, on peut discrétiser la pente 2/3 en faisant les mouvements '''[x,x,x,y,y]''' ou '''[y,y,x,x,x]'''.<br /> <br /> Un mot de Christoffel se base sur le même principe hormis qu'il va essayer de toujours être le plus proche possible de la ligne sans jamais la traverser.<br /> <br /> [[Fichier:74.jpg]]<br /> <br /> ''Mot de Christoffel &quot;bas&quot; [x,x,y,x,x,y,x,x,y,x,y] et &quot;haut&quot; [y,x,y,x,x,y,x,x,y,x,x] de la droite de pente 4/7.''<br /> <br /> '''Note''' : ''Le mot de Christoffel &quot;haut&quot; est le mot de Christoffel &quot;bas&quot; lu à l'envers.''&lt;br/&gt;<br /> '''Seconde Note''' : ''Si on retire la première et la dernière lettre d'un mot de Christoffel, on obtient un palindrome (lisible dans les deux sens)''<br /> <br /> === Algorithme de génération ===<br /> <br /> Il est possible de générer facilement et très rapidement le mot de Christoffel d'une pente grâce à une méthode simple :<br /> <br /> La suite &lt;math&gt;U0 = 0 | Un+1=Un+a [a+b]&lt;/math&gt; donnera une suite de chiffre qui se répète.&lt;br/&gt;<br /> Si Un &gt; Un+1, on ajoute un x au mot, sinon on ajoute un y au mot.<br /> <br /> On applique cette méthode jusqu'à ce que Un+1 = 0 pour avoir le mot de Christoffel de la pente.<br /> <br /> ==== Exemple ====<br /> Avec une pente de 5/7, on obtient : <br /> 0 5 10 3 8 1 6 11 4 9 2 7 0<br /> Soit :<br /> x x y x y x x y x y x y<br /> On retrouve bien le mot de Christoffel de la pente 5/7 : [x,x,y,x,y,x,x,y,x,y,x,y]<br /> <br /> ==== Implémentation Python ====<br /> [[Fichier:Algo.png]]<br /> <br /> == Mot de contour ==<br /> <br /> == Détection de droite discrète ==</div>

Jdubois http://os-vps418.infomaniak.ch:1250/mediawiki/index.php?title=Fichier:Algo.png&diff=14149 2022-05-29T13:11:36Z

<p>Jdubois : </p> <hr /> <div></div>

Jdubois http://os-vps418.infomaniak.ch:1250/mediawiki/index.php?title=G%C3%A9om%C3%A9trie_discr%C3%A8te,_Convexit%C3%A9_des_polyominos,_Combinatoire_des_mots&diff=14146 2022-05-29T13:10:38Z

<p>Jdubois : /* Mot de Christoffel */</p> <hr /> <div>Les images numérisées sont constituées de pixels, de petits carrés de couleurs. Les formes dans ces images ont alors une forme très particulière puisqu'il n'y a que quatres chemins possibles. Impossible d'aller en diagonale ou avec un angle particulier, les points n'ont que des coordonnées entières. &lt;br/&gt;<br /> On peut alors retrouver les éléments de la géométrie Euclidienne classique dans Z² via un outil : '''les mots de Christoffel.''' &lt;br/&gt;<br /> Cet outil permet de discrétiser des droites dans Z² afin de trouver la pente de celles-ci avec pour but d'appliquer les calculs de la géométrie Euclidienne.<br /> <br /> ----<br /> <br /> == Mot de Christoffel ==<br /> <br /> On prend une droite de pente p/q et on veut dessiner une droite discrète de celle-ci en connectant des points de coordonnées entières dans Z².&lt;br/&gt;<br /> On peut décrire cette droite comme &quot;''commençant''&quot; au point de coordonnée (0,0), passant par le point (p,q) et n'ayant que deux choix de mouvements :<br /> &lt;ul&gt;<br /> &lt;li&gt;X pour se déplacer d'une unité à droite sur l'axe des abscisses.&lt;/li&gt;<br /> &lt;li&gt;Y pour se déplacer d'une unité en haut sur l'axe des ordonnées.&lt;/li&gt;<br /> &lt;/ul&gt;<br /> Ainsi par exemple, on peut discrétiser la pente 2/3 en faisant les mouvements '''[x,x,x,y,y]''' ou '''[y,y,x,x,x]'''.<br /> <br /> Un mot de Christoffel se base sur le même principe hormis qu'il va essayer de toujours être le plus proche possible de la ligne sans jamais la traverser.<br /> <br /> [[Fichier:74.jpg]]<br /> <br /> ''Mot de Christoffel &quot;bas&quot; [x,x,y,x,x,y,x,x,y,x,y] et &quot;haut&quot; [y,x,y,x,x,y,x,x,y,x,x] de la droite de pente 4/7.''<br /> <br /> '''Note''' : ''Le mot de Christoffel &quot;haut&quot; est le mot de Christoffel &quot;bas&quot; lu à l'envers.''&lt;br/&gt;<br /> '''Seconde Note''' : ''Si on retire la première et la dernière lettre d'un mot de Christoffel, on obtient un palindrome (lisible dans les deux sens)''<br /> <br /> === Algorithme de génération ===<br /> <br /> Il est possible de générer facilement et très rapidement le mot de Christoffel d'une pente grâce à une méthode simple :<br /> <br /> La suite &lt;math&gt;U0 = 0 | Un+1=Un+a [a+b]&lt;/math&gt; donnera une suite de chiffre qui se répète.&lt;br/&gt;<br /> Si Un &gt; Un+1, on ajoute un x au mot, sinon on ajoute un y au mot.<br /> <br /> On applique cette méthode jusqu'à ce que Un+1 = 0 pour avoir le mot de Christoffel de la pente.<br /> <br /> ==== Exemple ====<br /> Avec une pente de 5/7, on obtient : <br /> 0 5 10 3 8 1 6 11 4 9 2 7 0<br /> Soit :<br /> x x y x y x x y x y x y<br /> On retrouve bien le mot de Christoffel de la pente 5/7 : [x,x,y,x,y,x,x,y,x,y,x,y]<br /> <br /> ==== Implémentation Python ====<br /> [[Fichier:Algo.jpg]]<br /> <br /> == Mot de contour ==<br /> <br /> == Détection de droite discrète ==</div>

Jdubois http://os-vps418.infomaniak.ch:1250/mediawiki/index.php?title=Fichier:74.jpg&diff=14119 2022-05-29T11:18:56Z

<p>Jdubois : Mots de Christoffel de la pente 4/7</p> <hr /> <div>Mots de Christoffel de la pente 4/7</div>

Jdubois http://os-vps418.infomaniak.ch:1250/mediawiki/index.php?title=G%C3%A9om%C3%A9trie_discr%C3%A8te,_Convexit%C3%A9_des_polyominos,_Combinatoire_des_mots&diff=14118 2022-05-29T11:18:08Z

<p>Jdubois : /* Mot de Christoffel */</p> <hr /> <div>Les images numérisées sont constituées de pixels, de petits carrés de couleurs. Les formes dans ces images ont alors une forme très particulière puisqu'il n'y a que quatres chemins possibles. Impossible d'aller en diagonale ou avec un angle particulier, les points n'ont que des coordonnées entières. &lt;br/&gt;<br /> On peut alors retrouver les éléments de la géométrie Euclidienne classique dans Z² via un outil : '''les mots de Christoffel.''' &lt;br/&gt;<br /> Cet outil permet de discrétiser des droites dans Z² afin de trouver la pente de celles-ci avec pour but d'appliquer les calculs de la géométrie Euclidienne.<br /> <br /> ----<br /> <br /> == Mot de Christoffel ==<br /> <br /> On prend une droite de pente p/q et on veut dessiner une droite discrète de celle-ci en connectant des points de coordonnées entières dans Z².&lt;br/&gt;<br /> On peut décrire cette droite comme &quot;''commençant''&quot; au point de coordonnée (0,0), passant par le point (p,q) et n'ayant que deux choix de mouvements :<br /> &lt;ul&gt;<br /> &lt;li&gt;X pour se déplacer d'une unité à droite sur l'axe des abscisses.&lt;/li&gt;<br /> &lt;li&gt;Y pour se déplacer d'une unité en haut sur l'axe des ordonnées.&lt;/li&gt;<br /> &lt;/ul&gt;<br /> Ainsi par exemple, on peut discrétiser la pente 2/3 en faisant les mouvements '''[x,x,x,y,y]''' ou '''[y,y,x,x,x]'''.<br /> <br /> Un mot de Christoffel se base sur le même principe hormis qu'il va essayer de toujours être le plus proche possible de la ligne sans jamais la traverser.<br /> <br /> [[Fichier:74.jpg]]<br /> <br /> ''Mot de Christoffel &quot;haut&quot; et &quot;bas&quot; de la droite de pente 4/7.''<br /> <br /> == Mot de contour ==<br /> <br /> == Détection de droite discrète ==</div>

Jdubois http://os-vps418.infomaniak.ch:1250/mediawiki/index.php?title=G%C3%A9om%C3%A9trie_discr%C3%A8te,_Convexit%C3%A9_des_polyominos,_Combinatoire_des_mots&diff=14117 2022-05-29T10:37:52Z

<p>Jdubois : </p> <hr /> <div>Les images numérisées sont constituées de pixels, de petits carrés de couleurs. Les formes dans ces images ont alors une forme très particulière puisqu'il n'y a que quatres chemins possibles. Impossible d'aller en diagonale ou avec un angle particulier, les points n'ont que des coordonnées entières. &lt;br/&gt;<br /> On peut alors retrouver les éléments de la géométrie Euclidienne classique dans Z² via un outil : '''les mots de Christoffel.''' &lt;br/&gt;<br /> Cet outil permet de discrétiser des droites dans Z² afin de trouver la pente de celles-ci avec pour but d'appliquer les calculs de la géométrie Euclidienne.<br /> <br /> ----<br /> <br /> == Mot de Christoffel ==<br /> <br /> <br /> == Mot de contour ==<br /> <br /> == Détection de droite discrète ==</div>

Jdubois http://os-vps418.infomaniak.ch:1250/mediawiki/index.php?title=G%C3%A9om%C3%A9trie_discr%C3%A8te,_Convexit%C3%A9_des_polyominos,_Combinatoire_des_mots&diff=14116 2022-05-29T10:37:09Z

<p>Jdubois : </p> <hr /> <div>Les images numérisées sont constituées de pixels, de petits carrés de couleurs. Les formes dans ces images ont alors une forme très particulière puisqu'il n'y a que quatres chemins possibles. Impossible d'aller en diagonale ou avec un angle particulier, les points n'ont que des coordonnées entières. &lt;br/&gt;<br /> On peut alors retrouver les éléments de la géométrie Euclidienne classique dans Z² via un outil : '''les mots de Christoffel.''' &lt;br/&gt;<br /> Cet outil permet de discrétiser des droites dans Z² afin de trouver la pente de celles-ci avec pour but d'appliquer les calculs de la géométrie Euclidienne.<br /> <br /> ----</div>

Jdubois http://os-vps418.infomaniak.ch:1250/mediawiki/index.php?title=G%C3%A9om%C3%A9trie_discr%C3%A8te,_Convexit%C3%A9_des_polyominos,_Combinatoire_des_mots&diff=14115 2022-05-29T10:35:13Z

<p>Jdubois : </p> <hr /> <div>Les images numérisées sont constituées de pixels, de petits carrés de couleurs. Les formes dans ces images ont alors une forme très particulière puisqu'il n'y a que quatres chemins possibles, impossible d'aller en diagonale ou avec un angle particulier, les points n'ont que des coordonnées entières. <br /> On peut alors retrouver les éléments de la géométrie Euclidienne classique dans Z² via un outil : les mots de Christoffel. &lt;br/&gt;<br /> Cet outil permet de discrétiser des droites dans Z² afin de trouver la pente de celles-ci avec pour but d'appliquer les calculs de la géométrie Euclidienne.</div>

Jdubois http://os-vps418.infomaniak.ch:1250/mediawiki/index.php?title=G%C3%A9om%C3%A9trie_discr%C3%A8te,_Convexit%C3%A9_des_polyominos,_Combinatoire_des_mots&diff=14114 2022-05-29T10:34:54Z

<p>Jdubois : </p> <hr /> <div>Les images numérisées sont constituées de pixels, de petits carrés de couleurs. Les formes dans ces images ont alors une forme très particulière puisqu'il n'y a que quatres chemins possibles, impossible d'aller en diagonale ou avec un angle particulier, les points n'ont que des coordonnées entières. <br /> On peut alors retrouver les éléments de la géométrie Euclidienne classique dans Z² via un outil : les mots de Christoffel. <br /> Cet outil permet de discrétiser des droites dans Z² afin de trouver la pente de celles-ci avec pour but d'appliquer les calculs de la géométrie Euclidienne.</div>

Jdubois http://os-vps418.infomaniak.ch:1250/mediawiki/index.php?title=G%C3%A9om%C3%A9trie_discr%C3%A8te,_Convexit%C3%A9_des_polyominos,_Combinatoire_des_mots&diff=14113 2022-05-29T10:33:26Z

<p>Jdubois : Page créée avec « Les images numérisées sont constituées de pixels, de petits carrés de couleurs. Les formes dans ces images ont alors une forme très particulière puisqu&#039;il n&#039;y a que... »</p> <hr /> <div>Les images numérisées sont constituées de pixels, de petits carrés de couleurs. Les formes dans ces images ont alors une forme très particulière puisqu'il n'y a que quatres chemins possibles, impossible d'aller en diagonale ou avec un angle particulier, les points n'ont que des coordonnées entières. <br /> On peut alors retrouver les éléments de la géométrie Euclidienne classique dans Z² via un outil : les mots de Christoffel. Cet outil permet de discrétiser des droites dans Z² afin de trouver la pente de celles-ci avec pour but d'appliquer les calculs de la géométrie Euclidienne.</div>

Jdubois