##
Surface Reconstruction between Simple Polygons via Angle Criteria

###
Emo Welzl, Barbara Wolfers
Institut für Informatik
Freie Universität Berlin
email: emo@inf.fu-berlin.de
Report B 94-11
April 94

Get the report here or by anonymous ftp:
Server: fubinf.inf.fu-berlin.de
File: pub/reports/tr-b-94-11.ps.gz

We consider the problem of connecting two simple polygons
$P$ and $Q$ in parallel planes by a polyhedral surface.
The goal is to find an optimality criterion which
naturally satisfies the following conditions: (i) if
$P$ and $Q$ are convex, then the optimal surface is the convex hull
of $P$ and $Q$ (without facets $P$ and $Q$), and
(ii) if $P$ can be obtained from $Q$ by scaling
with a center $c$, then the optimal surface is the
portion of the cone defined by $P$ and apex $c$ between
the two planes.
We provide a criterion (based on the sequences of angles of the edges
of $P$ and $Q$), which satisfies these conditions,
and for which the optimal surface can be efficiently computed.
Moreover, we supply a condition, so-called {\em angle consistency},
which proved very helpful in preventing self intersections
(for our and other criteria). The methods have been
implemented and gave improved results in a number of examples.