[comp.graphics] problem: fitting one polygon inside another

cain@ics.uci.edu (Timothy Cain) (09/20/89)

I would appreciate any pointers to papers or books addressing the
following problem (or if you have a solution yourself, great!):

You are given 2 closed 2D polygons, called hole and shape, and they
may be either convex or concave. They are each represented as a linked
list of vertices (but I could change this). The location of the hole
is fixed, but the shape may be placed anywhere.

Problem: can the shape be placed in the hole, and if so, where? By "placed",
         I mean the shape fits entirely within the hole, although the
         shape's edges may touch the hole's edges.

Again, any references to solutions would be appreciated.

Thanks,

Tim.

	
--
Timothy D. Cain     Department of Information and Computer Science, UC Irvine
                                          cain@ics.uci.edu             (ARPA)