Bonjour,
Je ne suis pas experts en algorithmique mais concernant l'aspect mathématique du passage:

"Jean-Marc Bourguet a écrit :

[...]
si je ne me trompe pas, utiliser
l'angle droit peut s'interpreter comme la contrainte qu'aucun point
exterieur a l'enveloppe n'est plus proche d'un point interieur a celle-ci
que d'un sommet de l'enveloppe, ce qui semble aussi un assez bon critere en
soi)."

Cette condition est impossible à satisfaire (aussi bien avec l'enveloppe que tu charches qu'avec l'enveloppe convexe) et quel que soit l'angle.
En effet si un point extérieur est suffisamment proche, par exemple, du milieu d'un segment, il pourra être aussi proche qu'on veut d'un point intérieur (par exemple son symétrique par rapport au segment).
La seule propriété de l'angle droit est est que si les sommets A, B, C se suivent sur ton enveloppe , A et C étant sur l'enveloppe convexe, ABC angle droit ou obtus, alors les point situés sur le segment AC sont plus près (ou aussi près) de B que de A ou C selon leur position. En effet B est sur le cercle de diamètre AC si l'angle est droit (et à l'intérieur du "demi-disque" si l'angle est obtus).

Mais il faut faire attention que si on accepte PLUSIEURS sommets successifs qui ne sont pas sur l'enveloppe convexe, avec des conditions d'angles il n'y a aucune garantie sur la profondeur d'une "crevasse" !
En effet il est facile de fabriquer un exemple en choisissant, pour définir un nuage, des points suffisamment proches les uns des autres sur une courbe simple fermée différentiable (pour éviter les angles vifs) et de forme appropriée (par exemple un le bord d'un U (sans sérif, lissé).
Ensuite évidemment en joignant les points successifs par des segments, on a un nuage entièrement situé sur le polygone obtenu.

Donc les méthodes déjà envisagées du style "contrainte de distance à l'enveloppe convexe" sont nécessaires.
Pour une contrainte indépendante de l'échelle et des rotations, une condition en pourcentage du diamètre du nuage ferait l'affaire.
Ensuite on peut aussi vérifier les angles pour éviter par exemple les arabesques, etc (mais c'est un peu compliqué).

Mais tout est ici affaire de goût, à moins qu'il n'y ait des conditions techniques à respecter à priori.