::  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
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.


P as a point I
P as a point II
P as an edge
P as a polygon
Barrier Regions




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