Simultaneous Containment of Several Polygons: Analysis of the Contact Configurations - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue International Journal of Computational Geometry and Applications Année : 1993

Simultaneous Containment of Several Polygons: Analysis of the Contact Configurations

Olivier Devillers

Résumé

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.
Fichier principal
Vignette du fichier
hal.pdf (161.92 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00167170 , version 1 (16-08-2007)

Identifiants

Citer

Olivier Devillers. Simultaneous Containment of Several Polygons: Analysis of the Contact Configurations. International Journal of Computational Geometry and Applications, 1993, 3 (4), pp.429-442. ⟨10.1142/S0218195993000270⟩. ⟨inria-00167170⟩
85 Consultations
249 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More