Abstract:
Computing nice projections of objects in 2D and 3D is a well studied
problem in computational geometry. By nice projections we mean optimal
projections having some special geometric property. Aside from theoretical
interest, its application reaches in the domain of computer graphics, computer
vision, object recognition, 3D graph drawing, visualization, robotics,
knot theory etc. Considerable amount of research work has been done based
on different criteria of niceness. For 3D objects some common criteria of
niceness include maximizing (minimizing) the area of projection, minimizing
the number of crossing in the projection of 3D lines, minimum overlapping
among line segments and vertices, monotonicity of polygonal chains and generating
silhouettes which meet some predefined criteria.
However, computing orthogonal projections of a set of line segments in
2D and 3D with the following optimality criteria have not been considered
so far: (i) sum of the projected length of the line segments in 2D is the
minimum and maximum, (ii) sum of the projected area of the triangles in
3D is the minimum and maximum, (iii) sum of the projected length of the line
segments in 3D is maximum and minimum. (iv) maximizing (minimizing)
the minimum (maximum) ratio between actual length and projected length
of line segments in 2D. This thesis addresses these four problems and gives
separate algorithms for each..
The underlying concept for Problem(i) and (ii) are similar. Here the idea
of McKenna-Seidls algorithm is used by extending the concept of view from
convex polyhedra to 2D and 3D scene. We have developed an O(n log n)
algorithm for finding an optimal direction in Problem(i) and an O(n2) algorithm
for that in Problem(ii). For problem (iii) we give several approximation
algorithms. Experimental result shows that our algorithm is within constant
factor of the optimum solution. In addition to our main objective on this
problem, the above algorithm can be used in a novel application, which is
to find the maximum (minimum) perimeter of a convex polyhedron in an
orthogonal projection and for which no solution is known. The running time
of this algorithm is O(n2). For Problem (iv), we developed an O(nlogn)
algorithm to find an optimal solution.
