Système de contraintes géométriques

En Conception Assistée par Ordinateur, et plus précisément en modélisation géométrique, un système de contraintes géométriques (SCG) est un ensemble de variables géométriques (points, droites, etc.) et de contraintes géométriques (distances, angles, etc.). Une solution d'un système de contraintes géométriques est un ensemble de coordonnées pour les variables géométriques tel que les contraintes géométriques sont respectées.

Formalisme

Univers géométrique

La syntaxe de l'univers que l'on souhaite décrire à travers des SCG est capturée par la notion de signature : une signature est un triplet Σ = (S,F,P) où S est un ensemble fini de symboles appelés sortes, F est un ensemble de symboles fonctionnels définis sur S, et P est un ensemble de symboles prédicatifs sur S. Pour une signature Σ, une Σ-algèbre est un modèle de Σ, associant à chaque sorte de S, à chaque fonction de F et à chaque prédicat de P un domaine d'interprétation (par exemple l'espace euclidien). La signature correspond à un langage formel de description, le modèle correspond à sa sémantique. Un univers géométrique est dès lors une paire (Σ,E) où Σ est une signature et E un modèle de Σ, une Σ-algèbre.

Système de contraintes géométriques

Pour une Σ-algèbre donnée, un système de contraintes géométriques est un triplet (C,X,A) où

• C (les contraintes) est un ensemble de termes prédicatifs construits sur Σ ;
• X (les variables) et A (les paramètres) sont deux ensembles disjoints de variables dont les sortes sont dans Σ ;
• les arguments apparaissant dans les termes de C sont des termes fonctionnels de Σ construits sur X${\displaystyle \cap }$A.

Par exemple, cette figure montre un énoncé sous forme graphique, qui représente le système de contraintes géométriques défini par :

• X = ${\displaystyle \{p_{1},p_{2},p_{3},l_{1},l_{2},l_{3}\}}$
• A = ${\displaystyle \{k_{1},K_{2},\alpha \}}$
• C = ${\displaystyle \{distpp(p_{1},p_{2},k_{1}),distpp(p_{2},p_{3},k_{2}),anglell(l_{1},l_{3},\alpha ),}$
  ${\displaystyle pointonline(p_{1},l_{1}),pointonline(p_{2},l_{1}),}$
  ${\displaystyle pointonline(p_{2},l_{2}),pointonline(p_{3},l_{2}),}$
  ${\displaystyle pointonline(p_{3},l_{3}),pointonline(p_{1},l_{3})\}}$

On peut définir des opérations d'addition, de soustraction et d'intersection de SCG.

Figure

Etant donné un univers (Σ,E) et un ensemble de variables X dont les sortes sont dans Σ, une figure est une valuation ${\displaystyle f:X\rightarrow E}$. Par exemple, quand le modèle E est le plan euclidien, une figure consiste à fournir des couples de coordonnées pour tous les points, des couples angle et abscisse à zéro pour les droites, etc.

Une figure correspondant à un SCG ne respecte pas nécessairement les contraintes de ce système : par exemple, une esquisse cotée associe bien à chaque variable du système des coordonnées et est donc une figure. Quand toutes les contraintes d'un système sont satisfaites quand elles sont interprétées dans le modèle pris en compte, on parle de figure solution ou simplement de solution.

Niveau de constriction

On distingue généralement trois niveaux de constriction d'un système de contraintes géométriques, étant donné une valuation de ses paramètres :

• sur-contraint : il n'existe pas de solution ;
• sous-contraint : il existe une infinité de solutions ;
• bien-contraint : il existe un nombre fini non nul de solutions.

La bonne constriction est parfois définie comme la dénombrabilité des solutions d'un SCG, ce qui autorise certains systèmes ayant une infinité de solutions.

Dans la plupart des méthodes de résolution, on considère comme bien-contraint un SCG définissant un objet rigide, c'est-à-dire ayant un nombre fini de solutions modulo les déplacements. On peut aussi considérer d'autres transformations telles que les homothéties, auquel cas un système sera considéré comme bien-contraint même si deux figures à des échelles différentes sont toutes deux solutions du système.

On évalue souvent la bonne constriction d'un système de contraintes géométriques de façon générique, c'est-à-dire sans se baser sur une valuation des paramètres. Par exemple, un système de contraintes géométriques défini par trois points et trois contraintes de distance point à point est génériquement rigide, mais pour certaines valeurs des contraintes, il n'existe pas de solutions (par exemple si une des trois contraintes de distance est strictement supérieure à la somme des deux autres).

La « double banane » est un exemple de mise en défaut de solveurs analysant le niveau de constriction générique : le nombre de variables et le nombre de contraintes semble indiquer un système bien contraint. Toutefois, chacune des deux « bananes » est rigide, ce qui signifie que la distance entre les deux points de contact peut être déduite de chacun des deux sous-systèmes. Le système est donc génériquement sur-contraint car il ne possède de solutions que si la valuation des paramètres rend les distances compatibles. Dans le même temps, le système est sous-contraint car, quand les valeurs des paramètres permettent des solutions, les deux « bananes » sont articulées autour de l'axe de leurs deux points de contact.

Solveur

Etant donnés un univers géométrique (Σ,E) et un système de contraintes géométriques S=(C,X,A), un solveur est une fonction qui à S associe un ensemble de figures de S. On dit qu'il est correct si les figures en question sont des solutions de S, et qu'il est complet s'il fournit toutes les solutions de S.

Méthodes de résolution

Méthodes symboliques

Les méthodes symboliques consistent à traduire les SCG sous forme d'équations et à manipuler directement le système d'équations résultant. L'approche générale est alors de trianguler le système d'équations puis de résoudre chacune des équations obtenues. Les méthodes symboliques ont l'avantage de leur généralisme, mais l'inconvénient de leur coût algorithmique.

Méthodes numériques

Les méthodes numériques ont l'avantage de leur efficacité : elles effectuent des calculs itératifs pour s'approcher peu à peu des solutions. Elles entrent donc dans la catégorie des problèmes d'optimisation.

La plus connue de ces méthodes et la méthode de Newton-Raphson. Elle consiste à dériver la matrice correspondant au système de contraintes pour approcher la solution. La méthode utilisant une inversion de matrices, elle ne fonctionne que sur des matrices carrées, correspondant à des systèmes bien-contraints.

La méthode de Newton-Raphson étant sensible aux optimums locaux, d'autres approches ont été proposées, par exemple l'homologie appliquée aux SCG^,.

Les autres approches numériques incluent les algorithmes génétiques^, ou encore les systèmes ressorts-particules (en).

Méthodes à base de graphe

Les méthodes à base de graphe consistent à traduire le système de contraintes géométriques sous la forme d'un graphe de contraintes. Elles fonctionnent par des décomptes de degrés de liberté des différents éléments du graphe.

Trois grandes approches existent parmi les méthodes à base de graphe : la propagation des degrés de liberté, les graphes de flux et les méthodes de décomposition.

Propagation des degrés de liberté

Le principe de la propagation des degrés de liberté est de fixer un élément du système (un point, un segment, une droite…) puis à itérativement chercher ce qui est constructible^,. À l'inverse, la rétro-propagation consiste à partir du graphe complet et à en retirer itérativement les nœuds qui ont autant de contraintes que de degrés de liberté, jusqu'à atteindre un système que l'on doit savoir résoudre.

Graphes de flux

Les méthodes à base de graphe de flux consistent à traduire le système de contraintes géométriques sous la forme d'un graphe de flux et à chercher à optimiser le flot y circulant^,. Le théorème de König indique que l'existence d'un couplage parfait est équivalente à la bonne constriction du système de contraintes géométriques.

Méthodes de décomposition

Les méthodes de décomposition consistent à chercher des sous-graphes avec des caractéristiques particulières qui permettent de garantir la possibilité de les résoudre. On peut ainsi chercher des paires d'articulation du graphe pour décomposer le graphe en composantes tri-connexes ou procéder par recherche de clusters.

Méthodes à base de règles

Les méthodes à base de règles utilisent des systèmes experts avec comme base de règles des raisonnements géométriques, afin de produire des plans de construction géométriques, tels que des constructions à la règle et au compas.

Applications

La résolution de systèmes de contraintes géométriques a des applications en conception mécanique assistée par ordinateur et plus généralement en conception et fabrication assistées par ordinateur, dans les domaines de la mécanique ou de l'architecture. On retrouve par exemple des algorithmes de résolution de contraintes géométriques dans des logiciels comme CATIA.

Références

• Portail de la géométrie
• Portail de l'informatique théorique