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 metadatas

Cited literature [8 references]  Display  Hide  Download

https://hal.inria.fr/inria-00167170
Contributor : Olivier Devillers <>
Submitted on : Thursday, August 16, 2007 - 11:28:14 AM
Last modification on : Wednesday, March 7, 2018 - 10:24:03 AM
Long-term archiving on : Friday, April 9, 2010 - 12:47:23 AM

File

hal.pdf
Files produced by the author(s)

Identifiers

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

Share

Metrics

Record views

252

Files downloads

317