Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [8 references]  Display  Hide  Download
Contributor : Olivier Devillers Connect in order to contact the contributor
Submitted on : Thursday, August 16, 2007 - 11:28:14 AM
Last modification on : Friday, February 4, 2022 - 3:24:53 AM
Long-term archiving on: : Friday, April 9, 2010 - 12:47:23 AM


Files produced by the author(s)




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. ⟨10.1142/S0218195993000270⟩. ⟨inria-00167170⟩



Record views


Files downloads