Note publique d'information : LES OPERATIONS BOOLEENNES - UNION, INTERSECTION, DIFFERENCE, ETC. - SUR DES OBJETS
GEOMETRIQUES SONT LA BASE DE BIEN DES TRAITEMENTS EN MODELISATION GEOMETRIQUE. ELLES
CORRESPONDENT A L'ENVIE DE MANIPULER, DE MANIERE NATURELLE, DES ENSEMBLES DE POINTS
ET SONT LA CONTREPARTIE MATHEMATIQUE DE TECHNIQUES D'USINAGE CONCRETES - SOUDURE,
FRAISAGE, PERCAGE, ETC. - DONT CHAQUE INDIVIDU POSSEDE AU MOINS L'INTUITION. ELLES
ONT ETE ETUDIEES A DE NOMBREUSES REPRISES, MAIS DES PROBLEMES SE POSENT TOUJOURS QUANT
A LEUR DEFINITION PRECISE ET COMPLETE ET QUANT A LEUR ROBUSTESSE. D'ABORD, LES OPERATIONS
BOOLEENNES ONT SOUVENT ETE DEFINIES POUR DES OBJETS DONT LA STRUCTURE TOPOLOGIQUE
N'ETAIT PAS EXPLICITEMENT REPRESENTEE, C'EST-A-DIRE DES OBJETS UNIQUEMENT CONSIDERES
COMME DES ENSEMBLES DE POINTS, DE SEGMENTS OU DE FACETTES. DANS CES APPROCHES, LA
TOPOLOGIE N'EST INTRODUITE SOUVENT QUE DE MANIERE AD HOC, APRES COUP ET POUR DES RAISONS
DE COMPLEXITE ALGORITHMIQUE. CE TRAVAIL SE SITUE DANS UN CADRE DE MODELISATION A BASE
TOPOLOGIQUE, OU LES RELATIONS D'INCIDENCE ET D'ADJACENCE ENTRE LES PARTIES DES OBJETS
SONT PRIMORDIALES ET DOIVENT ETRE MAINTENUES TOUT AU LONG DES TRANSFORMATIONS SUBIES
PAR LES OBJETS. CES RELATIONS TOPOLOGIQUES FACILITENT LES ACCES ET LES PARCOURS DE
CELLULES, NON SEULEMENT POUR LES OPERATIONS BOOLEENNES, MAIS DANS TOUS LES AUTRES
TRAITEMENTS A EFFECTUER PAR AILLEURS, NOTAMMENT INTERACTIFS. UNE GRANDE PARTIE DE
NOTRE TRAVAIL CONSISTE A RECONSTITUER UNE TOPOLOGIE CORRECTE POUR DES OBJETS AYANT
SUBI DES OPERATIONS BOOLEENNES, CE QUI DISTINGUE NOTRE APPROCHE DE LA PLUPART DES
PRECEDENTES. DE PLUS, COMME SOUVENT EN GEOMETRIE ALGORITHMIQUE, L'ANALYSE, LA CONCEPTION
ET L'IMPLANTATION DES ALGORITHMES CORRESPONDANTS SONT LONGUES ET DIFFICILES. MEME
SI UNE SOLUTION NAIVE PEUT ETRE DECRITE EN QUELQUES MOTS DANS LE CAS GENERAL, LES
CAS PARTICULIERS A PRENDRE EN COMPTE ET LA NATURE DES STRUCTURES DE DONNEES UTILISEES
CONDUISENT A DES PROGRAMMES VOLUMINEUX, DIFFICILES A MAINTEN IR ET DONT LA CORRECTION
EST QUASIMENT IMPOSSIBLE A PROUVER. CE MEMOIRE DE THESE TENTE D'APPORTER DES REPONSES
A CES PREOCCUPATIONS, PAR L'UTILISATION DE METHODES FORMELLES A TOUS LES STADES DE
LA MODELISATION DES OBJETS ET DES OPERATIONS ET DE LA CONCEPTION DES PROGRAMMES CORRESPONDANTS,
C'EST-A-DIRE DE L'ANALYSE A L'IMPLANTATION. EN PREMIER LIEU, DANS LE DOMAINE DE LA
MODELISATION, NOUS PROPOSONS UNE EXTENSION DES CARTES COMBINATOIRES PLONGEES PAR L'INTRODUCTION
DE LABELS, POUR MODELISER UN ENSEMBLE D'OBJETS GEOMETRIQUES COMPLEXES EN DIMENSION
2 OU 3. NOUS DONNONS UNE DESCRIPTION MATHEMATIQUE, FORMELLE ET RIGOUREUSE DE CES OBJETS,
DE LEURS PROPRIETES TOPOLOGIQUES ET GEOMETRIQUES ET DE LEURS CONTRAINTES D'INTEGRITE.
CECI NOUS PERMET DE DEFINIR, DE MANIERE TRES GENERALE, LES OPERATIONS BOOLEENNES SUR
UN NOMBRE QUELCONQUE D'OBJETS, GRACE A LA COMBINAISON DE DEUX PUISSANTES OPERATIONS
APPELEES RAFFINEMENT ET COMPLETION DES LABELS. DEUXIEMEMENT, NOTRE TRAVAIL SE SITUE
DANS LA CONTINUITE DES RECHERCHES MENEES A STRASBOURG SUR LA SPECIFICATION FORMELLE
D'UNIVERS D'OBJETS ET D'OPERATIONS GEOMETRIQUES, AYANT NOTAMMENT CONDUIT A LA CONCEPTION
ET AU DEVELOPPEMENT D'UN MODELEUR A BASE TOPOLOGIQUE. NOUS DECRIVONS FORMELLEMENT,
PAR UN ENSEMBLE DE SPECIFICATIONS ALGEBRIQUES, LES OPERATIONS PERMETTANT LA CONSTRUCTION
ET LA MANIPULATION DE NOS OBJETS GEOMETRIQUES, TOUT EN GARANTISSANT LA CONSERVATION
DE LEURS CONTRAINTES D'INTEGRITE. TROISIEMEMENT, GRACE A UNE UTILISATION NOUVELLE
DE LA REECRITURE, NOUS DECRIVONS LE PROCESSUS GENERIQUE DE RAFFINEMENT ET DE COMPLETION
DES LABELS, A LA BASE DES OPERATIONS BOOLEENNES. A CE NIVEAU, LES PROPRIETES DE TERMINAISON
ET DE CONFLUENCE DES TRANSFORMATIONS ELEMENTAIRES SOUS-JACENTES PEUVENT ETRE ETUDIEES
ET PROUVEES, CE QUE NOUS AVONS FAIT EN DIMENSION 2. PUIS NOUS DERIVONS, AU SENS DU
GENIE LOGICIEL, PAR DES TRANSFORMATIONS SUCCESSIVES DES SYSTEMES DE REECRITURE ET
PAR L'INTRODUCTION DE STRUCTURES DE CONTROLE ADEQUATES, UN ENSEMBLE DE STRATEGIES
D'EVALUATION DE PLUS EN PLUS EFFICACES. CETTE APPROCHE NOUS PERMET D'ETUDIER SYSTEMATIQUEMENT
LA REDUCTION DE LA COMPLEXITE ALGORITHMIQUE JUSQU'A L'OBTENTION D'UNE STRATEGIE OPTIMALE.
ENFIN, ELLE NOUS AIDE A REALISER FACILEMENT LE PASSAGE A UN PROTOTYPE, PUIS A UNE
IMPLANTATION REELLE.
paprika.idref.fr
data.idref.fr
Documentation
