Re: enveloppe principale

Le 31/01/2025 à 13:10, Julien Arlandis a écrit :

Le 31/01/2025 à 12:15, Olivier Miakinen a écrit :

Le 31/01/2025 10:47, Julien Arlandis a écrit :

>
Soit une fonction discrète f(x_i) définie sur un intervalle de points régulièrement espacés entre [0;1] et qui prend ses valeurs dans [0;1].

>
Du coup, tu as n+1 points de la forme (i/n, f(i/n)) où i ∈ ⟦0,n⟧ ?

 Oui c'est ça.

Il s'agit d'un problème d'enveloppe convexe. L'algorithme naif est d'ordre O(N^2)
mais il existe des algorithmes d'ordre O(N log(N)). Ce qui suit en est un, particulièrement simple, tiré de l'algo python de même nom dans
https://www.geeksforgeeks.org/convex-hull-in-python, qui contient tous les algos classiques.
J'en ai fait une version dans le langage maxima, en tenant compte des simplifications autorisées par le problème en question.
Comme les autres algos on utilise le produit vectoriel vp(p1,p2,p)
pour savoir si p est au dessus ou au dessous de la ligne p1p2 et avoir sa distance à
la ligne. On choisit le point au dessus de la ligne à la plus grande distance. Ensuite
on applique récursivement ceci comme dans l'algorithme quicksort. A la fin
on trie les points extrémaux et on retire les doublons.  J'ai testé l'algo un bon nombre de fois, N=1000 donne encore une réponse rapide. N=10000 prend
quelques secondes.
hull:[]$
vp(p1,p2,p) := block([val],
   val: (p[2] - p1[2]) * (p2[1] - p1[1]) - (p2[2] - p1[2]) * (p[1] - p1[1]),
   [sign(val),abs(val)])$
quickhull(a,n1,n2) := block([index:-1,max_dist:0,temp],
   for i from n1+1 thru n2-1 do (
     temp:vp(a[n1],a[n2],a[i]),
     if ( temp[1] = pos and temp[2] > max_dist ) then (index:i, max_dist:temp[2])),
   if (index = -1) then (
     hull:append([n1,n2],hull),return),
   else (quickhull(a,n1,index), quickhull(a,index,n2)))$
printhull(a) := block([N:length(a)],
   quickhull(a,1,N),
   hull:listify(setify(hull)),
   map(lambda([n],a[n]),hull))$
/* Test du programme */
N:10$
a:[]$
for i from 0 thru N do a:endcons([float(i/N),random(1.0)],a)$
b:printhull(a);
plot2d([[discrete,a],[discrete,b]]);
--
Michel Talon