inria-00075449, version 1
Probing a scene of non convex polyhedra
Jean-Daniel Boissonnat
1Mariette Yvinec
2
N° RR-1110 (1989)
Résumé : We show, in this paper, how one can compute the exact shapes of a class of polyhedral scenes by means of a simple sensory device issuing probes. A scene in this class consists of disjoint polyhedra with no collinear edges, no coplanar faces and such that no edge is contained in the supporting plane of a non incident face. The basic step of our method is a strategy for probing a single simple polygon with no collinear edges. When each probe outcome consists of a contact point and the normal to the object at the point, we present a strategy that allows to compute the exact shape of a simple polygon with no collinear edges by means of at most 3n - 3 probes, where n is the number of edges of the polygon. This is optimal in the worst-case. This strategy can be extended to probe a family of disjoint polygons. It can also be applied in planar sections of a scene of polyhedra of the class above to find out, in turn, each edge of the scene. If the scene consists of k polyhedra with altogether n faces and m edges, we show that (10,3) n(m + k) - 2m - 3k probes are sufficient to compute the exact shapes of the polyhedra.
- 1 : PRISME (INRIA Sophia Antipolis)
- INRIA
- 2 : Laboratoire d'informatique de l'école normale supérieure (LIENS)
- CNRS : UMR8548 – Ecole Normale Supérieure de Paris - ENS Paris
- Domaine : Informatique/Autre
- Référence interne : RR-1110
- inria-00075449, version 1
- http://hal.inria.fr/inria-00075449
- oai:hal.inria.fr:inria-00075449
- Contributeur : Rapport De Recherche Inria
- Soumis le : Mercredi 24 Mai 2006, 18:14:45
- Dernière modification le : Vendredi 7 Mai 2010, 09:40:46






Documents associés

Exporter