Simultaneous Containment of Several Polygons: Analysis of the Contact Configurations

Olivier Devillers 1
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : The main concern of this paper is the detection of double contact configurations for some polygons moving in translation in a polygonal environment. We first establish some general properties about such configurations and give conditions of existence of double contacts for two or three objects. For three convex polygons moving in a polygonal environment or three simple polygons moving in a rectangle there always exists a double contact. Two examples without possibility of double contacts are given, one with three polygons (not convex) moving in a polygonal environment, and one with four convex polygons moving in a rectangle. We deduce an algorithm detecting a double contact position in time O(n2) (resp. O(n3)) for two (resp three) convex polygons of constant sizes moving in a non-convex polygon of size n.
Type de document :
Article dans une revue
International Journal of Computational Geometry and Applications, World Scientific Publishing, 1993, 3 (4), pp.429-442
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00167170
Contributeur : Olivier Devillers <>
Soumis le : jeudi 16 août 2007 - 11:28:14
Dernière modification le : jeudi 11 janvier 2018 - 16:56:43
Document(s) archivé(s) le : vendredi 9 avril 2010 - 00:47:23

Fichier

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

Identifiants

  • HAL Id : inria-00167170, version 1

Collections

Citation

Olivier Devillers. Simultaneous Containment of Several Polygons: Analysis of the Contact Configurations. International Journal of Computational Geometry and Applications, World Scientific Publishing, 1993, 3 (4), pp.429-442. 〈inria-00167170〉

Partager

Métriques

Consultations de la notice

180

Téléchargements de fichiers

241