Reconstructing Convex Polygons and Polyhedra from Edge and Face Counts in Orthogonal Projections
We study the problem of constructing convex polygons and convex polyhedra given the number of visible edges and visible faces from some orthogonal projections. In 2D, we find necessary and sufficient conditions for the existence of a feasible polygon of s
- PDF / 715,171 Bytes
- 12 Pages / 430 x 660 pts Page_size
- 32 Downloads / 199 Views
School of Computer Science, University of Waterloo, Waterloo, Ontario, Canada N2M 3G1 {biedl,alopez-o}@uwaterloo.ca 2 Department of Computer Science and Engineering Bangladesh University of Engineering and Technology, Dhaka-1000, Bangladesh [email protected]
Abstract. We study the problem of constructing convex polygons and convex polyhedra given the number of visible edges and visible faces from some orthogonal projections. In 2D, we find necessary and sufficient conditions for the existence of a feasible polygon of size N and give an algorithm to construct one, if it exists. When N is not known, we give an algorithm to find the maximum and minimum size of a feasible polygon. In 3D, when the directions span a single plane we show that a feasible polyhedron can be constructed from a feasible polygon. We also give an algorithm to construct a feasible polyhedron when the directions are covered by two planes. Finally, we show that the problem becomes NP-complete for three or more planes.
1 Introduction Reconstructing polyhedra from projection information is an important field of research due to its applications in geometric modeling, computer vision, geometric tomography, and computer graphics. The nature of reconstruction problems and the techniques to solve them depend upon the types of information given, such as line drawings, silhouettes, and area/volume/shape of shadows, among others. The computational geometry community has studied the problem of reconstructing convex polyhedra from triangulations of the shadow boundary. Marlin and Toussaint [15] gave an O(n2 ) algorithm for deciding whether such a polyhedron exists and constructing a polyhedron where possible. In another variation of this problem, where the triangulations are isomorphic to two opposite projections from the z-axis, Bereg [2] showed that the polyhedron can always be reconstructed. See [6] for a collection of similar problems on reconstruction of polyhedra. Reconstructing polyhedra has also been studied from the point of view of applications, and various types of projection information have been considered. Among them line drawings [13,14,17,18,19,20,23,24] are possibly the most common. Line drawings may be obtained from images, from geometric drawings from the designers [20, Chapter 1], or may be freehand drawings [12,22]. The reconstruction algorithms differ for a single and multiple drawings. For multiple drawings there are two common V. Arvind and S. Prasad (Eds.): FSTTCS 2007, LNCS 4855, pp. 400–411, 2007. c Springer-Verlag Berlin Heidelberg 2007
Reconstructing Convex Polygons and Polyhedra from Edge and Face Counts
401
approaches based on the representation of the polyhedra to be reconstructed: constructive solid geometry and boundary representation. Both approaches are used in engineering and product design such as designing complex mechanical parts and in CAD [10,23]. It is more difficult to construct a polyhedron from a single drawing [20,23]. Reconstruction from the area and shape of projections has been considered in geom
Data Loading...
