Drawing Nice Projections of Objects in Space

Given a polygonal object (simple polygon, geometric graph, wire-frame, skeleton or more generally a set of line segments) in three-dimensional Euclidean space, we consider the problem of computing a variety of “nice” parallel (orthographic) projections of the object. We show that given a general polygonal object consisting ofline segments in space, deciding whether it admits aprojection can be done in(log+) time and(+) space, whereis the number of edge intersections of forbidden quadrilaterals (i.e., a set of directions that admits a crossing) and varies from zero to(). This implies for example that, given a simple polygon in 3-space, we can determine if there exists a plane on which the projection is a simple polygon, within the same complexity. Furthermore, if such a projection does not exist, aprojection can be found in() time and space. We show that an object always admits a regular projection (of interest to knot theory) and that such a projection can be obtained in() time and space or in() time and linear space. A description of the set of all directions which yield regular projections can be computed in(log+) time, whereis the number of intersections of a set of quadratic arcs on the direction sphere and varies from() to(). Finally, when the objects are polygons and trees in space, we considerprojections, i.e., projections such that every path from the root of the tree to every leaf is monotonic in a common direction on the projection plane. We solve a variety of such problems. For example, given a polygonal chain, we can determine in() time ifis monotonic on the projection plane, and in(log) time we can findthe viewing directions with respect to whichis monotonic. In addition, in() time, we can determine all directions with respect to which a given tree or simple polygon is monotonic.