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