Algorithms for Computing Intersection and Union of Toleranced Polygons With Applications

Frédéric Cazals 1, * Gd Ramkumar 2
* Auteur correspondant
1 iMAGIS - Models, Algorithms and Geometry for Computer Generated Image Graphics
GRAVIR - IMAG - Graphisme, Vision et Robotique, Inria Grenoble - Rhône-Alpes
Abstract : Since mechanical operations are performed only up to a certain precision, the geometry of parts involved in real life products is never known precisely. But if tolerance models for specifying acceptable variations have received a substantial attention, operations on toleranced objects have not been studied extensively. That is the reason why we address in this paper the computation of the union and the intersection of toleranced simple polygons, under a simple and already known tolerance model. Firstly, we provide a practical and efficient algorithm that stores in an implicit data structure the information necessary to answer a request for specific values of the tolerances without performing a computation from scratch. If the polygons are of sizes m and n, and s is the number of intersections between edges occurring for all the combinations of tolerance values, the pre-processed data structure takes O(s) space and the algorithm that computes a union/intersection from it takes O((n+m) log s+ k ′ +k log k) time where k is the number of vertices of the union/intersection and k k ′ s. Although the algorithm is not output sensitive, we show that the expectations of k and k ′ remain within a constant factor , a function of the input geometry. Secondly, we define and study the stability of union or intersection features. Thirdly, we list interesting applications of the algorithms related to feasibility of assembly and assembly sequencing of real assemblies.
Type de document :
Article dans une revue
Artificial Intelligence for Engineering Design, Analysis and Manufacturing, Cambridge Journals, 1997
Liste complète des métadonnées

Littérature citée [23 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00509985
Contributeur : Team Evasion <>
Soumis le : jeudi 19 août 2010 - 12:12:02
Dernière modification le : jeudi 11 janvier 2018 - 06:20:04
Document(s) archivé(s) le : samedi 20 novembre 2010 - 02:30:33

Fichiers

aiedam.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00509985, version 1

Collections

INRIA | UGA | IMAG

Citation

Frédéric Cazals, Gd Ramkumar. Algorithms for Computing Intersection and Union of Toleranced Polygons With Applications. Artificial Intelligence for Engineering Design, Analysis and Manufacturing, Cambridge Journals, 1997. 〈inria-00509985〉

Partager

Métriques

Consultations de la notice

105

Téléchargements de fichiers

472