Système de contraintes géométriques
La mise en forme de cet article est à améliorer ().
La mise en forme du texte ne suit pas les recommandations de Wikipédia : il faut le « wikifier ».
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[modifier | modifier le code]
Univers géométrique[modifier | modifier le code]
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.
Considérons la signature définie par :
sortes
angle, longueur, point, droite
prédicats
distpp : point point longueur
anglell: droite droite angle
incpl: point droite
Système de contraintes géométriques[modifier | modifier le code]
Pour une Σ-algèbre donnée, un système de contraintes géométriques est un triplet (C,X,A)[1] 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 XA.
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 =
- A =
- C =
On peut définir des opérations d'addition, de soustraction et d'intersection de SCG.
Figure[modifier | modifier le code]
Etant donné un univers (Σ,E) et un ensemble de variables X dont les sortes sont dans Σ, une figure est une valuation . 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[modifier | modifier le code]
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[2], 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[3].
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[modifier | modifier le code]
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[4].
Méthodes de résolution[modifier | modifier le code]
Méthodes symboliques[modifier | modifier le code]
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[5]. 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[modifier | modifier le code]
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[6]. 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[7],[8].
Les autres approches numériques incluent les algorithmes génétiques[9],[10] ou encore les systèmes ressorts-particules (en)[11].
Méthodes à base de graphe[modifier | modifier le code]
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é[modifier | modifier le code]
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[12],[13]. À 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[modifier | modifier le code]
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[14],[15]. 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[modifier | modifier le code]
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[16]. On peut ainsi chercher des paires d'articulation du graphe pour décomposer le graphe en composantes tri-connexes[17] ou procéder par recherche de clusters[18].
Méthodes à base de règles[modifier | modifier le code]
Les méthodes à base de règles utilisent des systèmes experts avec comme base de règles des raisonnements géométriques[19], afin de produire des plans de construction géométriques, tels que des constructions à la règle et au compas.
Applications[modifier | modifier le code]
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[modifier | modifier le code]
- (en) Pascal Mathis et Simon E.B. Thierry, « A formalization of geometric constraint systems and their decomposition », Formal Aspects of Computing, vol. 22, no 2, , p. 129-151 (DOI 10.1007/s00165-009-0117-8)
- Christophe Jermann, Résolution de contraintes géométriques par rigidification récursives et propagation d'intervalles (Thèse de doctorat en informatique), Université de Nice Sophia-Antipolis, (présentation en ligne)
- (en) Pascal Schreck et Etienne Schramm, « Using the invariance under the similarity group to solve geometric constraints systems », Computer-Aided Design, vol. 38, no 5, , p. 475-484 (DOI 10.1016/j.cad.2006.01.002)
- Simon E.B. Thierry, Décomposition et paramétrisation de systèmes de contraintes géométriques (Thèse de doctorat en informatique), Université de Strasbourg, (présentation en ligne)
- B. Buchberger, G.E. Collins et B. Kutzler, « Algebraic methods for geometric reasoning », Annual Review of Computer Science, vol. 3, , p. 85-120 (DOI 10.1146/annurev.cs.03.060188.000505)
- T.J. Ypma, « Historical development of the Newton-Raphson method », SIAM Review, vol. 37, no 4, , p. 531-551
- Hervé Lamure et Dominique Michelucci, « Solving geometric constraints by homotopy », IEEE Transactions on Visualization and Computer Graphics, vol. 2, no 1, , p. 28-34 (DOI 10.1109/2945.489384)
- C. Durand et C.M. Hoffmann, « A systematic framework for solving geometric constraints analytically », Journal of Symbolic Computation, vol. 30, no 5, , p. 493-519 (DOI 10.1006/jsco.2000.0392)
- C.A. Coello-Coello, « Theoretical and numerical constraint-handling techniques used with evolutionary algorithms: a survey of the state of the art », Computer Methods in Applied Mechanics and Engineering, vol. 191, nos 11-12, , p. 1245-1287 (DOI 10.1016/S0045-7825(01)00323-1)
- C.H. Cao, W.H. Li et B. Cong, « The geometric constraint solving based on hybrid genetic algorithm of conjugate gradient », Computational Methods, , p. 1117-1121 (DOI 10.1007/978-1-4020-3953-9_17)
- Simon E.B. Thierry, « A particle-spring approach to geometric constraints solving », Proceedings of the 2011 ACM Symposium on Applied Computing, , p. 1100-1105 (DOI 10.1145/1982185.1982428)
- Glenn A. Kramer, « Using degrees of freedom analysis to solve geometric constraint systems », Proceedings of the first ACM symposium on Solid modeling foundations and CAD/CAM applications, , p. 371-378 (DOI 10.1145/112515.112566)
- Jae Yeol Lee et Kwangsoo Kim, « A 2-D geometric constraint solver using DOF-based graph reduction », Computer-Aided Design, vol. 30, no 11, , p. 883-896 (DOI 10.1016/S0010-4485(98)00045-1)
- R.S. Latham et A.E. Middleditch, « Connectivity analysis: a tool for processing geometric constraints », Computer-Aided Design, vol. 28, no 11, , p. 917-928 (DOI 10.1016/0010-4485(96)00023-1)
- Christophe Jermann, Bertrand Neveu et Gilles Trombettoni, « Algorithms for identifying rigid subsystems in geometric constraints systems », Proceedings of the 18th international joint conference on Artificial intelligence, , p. 233-238 (DOI 10.5555/1630659.1630693)
- Christophe Jermann, Gilles Trombettoni, Bertrand Neveu et Pascal Mathis, « Decomposition of Geometric Constraint Systems: a Survey », International Journal of Computational Geometry and Applications, vol. 16, nos 5-6, , p. 379-414 (DOI 10.1142/S0218195906002105, lire en ligne)
- J.C. Owen, « Algebraic solution for geometry from dimensional constraints », Proceedings of the first ACM symposium on Solid modeling foundations and CAD/CAM applications, , p. 397-407 (DOI 10.1145/112515.112573)
- R. Joan-Arinyo, A. Soto-Riera, S. Vila-Marta et J. Vilaplana-Pasto, « Revisiting decomposition analysis of geometric constraint graphs », Computer-Aided Design, vol. 36, no 2, , p. 123-140 (DOI 10.1016/S0010-4485(03)00057-5)
- R. Joan-Arinyo et A. Soto-Riera, « A correct rule-based geometric constraint solver », Computer&Graphics, vol. 21, no 5, , p. 599-609 (DOI 10.1016/S0097-8493(97)00038-1)
