﻿ Separability of 2 simple polygons through single translation

The problem
 What's given What we want Formally: A polygons P with n vertices A polygon Q with m verticesBoth simple and disjoint The movability wedge of P w.r.t. Q i.e. all directions in which P can betaken 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