Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!ucsd!orion.cf.uci.edu!uci-ics!cain
From: cain@ics.uci.edu (Timothy Cain)
Newsgroups: comp.graphics
Subject: problem: fitting one polygon inside another
Keywords: polygon fitting
Message-ID: <1989Sep19.223625.9965@paris.ics.uci.edu>
Date: 19 Sep 89 22:36:25 GMT
Sender: news@paris.ics.uci.edu (Network News)
Organization: UC Irvine Department of ICS
Lines: 22

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)