In the hidden-line elimination problem, we would like to visualize a threedimensional scene, described by a collection
Question:
In the hidden-line elimination problem, we would like to visualize a threedimensional scene, described by a collection of polygons, from a particular viewing point, p, and in a particular direction. This problem is often solved by projecting the edges of the polygons in the scene onto a view plane perpendicular to the viewing direction. Then this set of segments is processed to remove the portions of edges that cannot be seen from p because they are occluded by a polygon in the scene. In order to identify visible and invisible portions of edges, it is helpful to know which pairs of line segments intersect one another. So, suppose you are given a set, S, of n line segments in the plane. Describe an algorithm to enumerate all k pairs of intersecting segments in S in O((n + k) log n) time. Use the plane-sweep technique, including segments intersections as events. Note that you cannot know these events in advance, but it is always possible to know the next event to process as you are sweeping.
Step by Step Answer:
Algorithm Design And Applications
ISBN: 9781118335918
1st Edition
Authors: Michael T. Goodrich, Roberto Tamassia