::  Intro  ::  P as a point I  ::  P as a point II  ::  P as an edge  ::  P as a polygon  ::  Barrier Regions  ::  Applet  ::  Conclusion  ::

The problem   What's given What we want Formally: A polygons P with n vertices A polygon Q with m vertices Both simple and disjoint The movability wedge of P w.r.t. Q i.e. all directions in which P can be taken arbitrarily far from Q in one shot Example: The main application The most obvious application is in the grasping problem in robotics. Consider Q as a 2D robot hand and P as an object: The wedge is NOT empty i.e. the hand is NOT grasping the object The wedge is empty i.e. the hand IS grasping the object The algorithm presented on this web site I will present an algorithm by Toussaint and Sack from 1987. We first consider P as being a single point, that in turn will help us find the wedge when P is an edge, and finally, we'll get to the case where P is a simple polygon. An applet is provided that generates the movability wedge for any valid P and Q drawn by the user.

Website created by Michel Langlois
COMP 507: Computational Geometry
Instructor: Godfried Toussaint, Teaching Assistant: Greg Aloupis
School of Computer Science, McGill University, Montreal, Fall 2003