Drawing nice projections of objects in space

Given a polygonal object (simple polygon, geometric graph, wire-frame, skel eton or more generally a set of line segments) in three-dimensional Euclide an space, we consider the problem of computing a variety of "nice" parallel (orthographic) projections of the object. We show that given a general pol ygonal object consisting of n line segments in space, deciding whether it a dmits a crossing-free projection can be done in O(n(2) log n + k) time and O(n(2) + k) space, where X: is the number of edge intersections of forbidde n quadrilaterals (i,e., a set of directions that admits a crossing) and var ies from zero to O(n(4)). This implies for example that, given a simple pol ygon in 3-space, we can determine if there exists a plane on which the proj ection is a simple polygon, within the same complexity. Furthermore, if suc h a projection does not exist, a minimum-crossing projection can be found i n O(n(4)) time and space, We show that an object always admits a regular pr ojection (of interest to knot theory) and that such a projection can be obt ained in O(n(2)) time and space or in O(n(4)) time and linear space, A desc ription of the set of all directions which yield regular projections can be computed in O(n(3) log n + k) time, where k is the number of intersections of a set of quadratic arcs on the direction sphere and varies from O(n(3)) to O(n(6)). Finally, when the objects are polygons and trees in space, we consider monotonic projections, i.e., projections such that every path from the root of the tree to every leaf is monotonic in a common direction on t he projection plane. We solve a variety of such problems. For example, give n a polygonal chain P, we can determine in O(n) time if P is monotonic on t he projection plane, and in O(n log n) time we can find all the viewing dir ections with respect to which P is monotonic. In addition, in O(n(2)) time, we can determine all directions with respect to which a given tree or simp le polygon is monotonic. (C) 1999 Academic Press.