naras@stat.fsu.edu (B. Narasimhan) (08/15/90)
Consider two line segments in R3 determined by points (x(1),y(1),z(1)) and (x(2),y(2),z(2)), and (x(3),y(3),z(3)) and (x(4),y(4),z(4)) respectively. I want to project these line segments on the XY plane in such a way that I depict which segment crosses over and which one goes under. This I can do in a straightforward way by computing the intersection point of the projected segments (if there is one), then projecting this point back to the original line segments and checking the z-coordinate. Now suppose I have a sequence of points (x(1),y(1),z(1))....(x(n),y(n),z(n)) such that a line segment connects (x(i),y(i),z(i)) and (x(i+1),y(i+1),z(i+1)). The last point is connected to (x(1),y(1),z(1)). If I use the above approach, I would have an O(n^2) algorithm. Is there an efficient algorithm for projecting the closed figure so that I depict the over/under aspect of the crossings? Note that I need to know the identity of each of the segments going under or above. References and suggestions welcome. Thanks in advance. -- ---------------------------------------------------------------------- B. Narasimhan Supercomputer Computations Research Institute & naras@stat.fsu.edu Dept. of Statistics, FSU, Tallahassee, FL 32306. ----------------------------------------------------------------------
merrill@bucasb.bu.edu (John Merrill) (08/15/90)
In article <839@stat.fsu.edu> naras@stat.fsu.edu (B. Narasimhan) writes: > Consider two line segments in R3 determined by points > (x(1),y(1),z(1)) and (x(2),y(2),z(2)), and (x(3),y(3),z(3)) and > (x(4),y(4),z(4)) respectively. I want to project these line > segments on the XY plane in such a way that I depict which segment > crosses over and which one goes under. This I can do in a > straightforward way by computing the intersection point of the > projected segments (if there is one), then projecting this point > back to the original line segments and checking the z-coordinate. > Now suppose I have a sequence of points > (x(1),y(1),z(1))....(x(n),y(n),z(n)) such that a line segment > connects (x(i),y(i),z(i)) and (x(i+1),y(i+1),z(i+1)). The last > point is connected to (x(1),y(1),z(1)). > If I use the above approach, I would have an O(n^2) algorithm. The poster asks: is there a more efficient algorithm? The answer is no. It suffices to observe that there exists a configuration of endpoints such that the total number of occlusions is O(n^2). This proves that the problem is O(n^2)-SPACE, and hence has no solution which is better than O(n^2)-TIME. One such configuration of points is constructed by fixing a k > 0, and taking (x_{2i}, y_{2i}, z_{2i}) = (cos(pi * i / k), sin(pi * i / k), (2 * i) / k) and (x_{2i + 1}, y_{2i + 1}, z_{2i + 1}) = (cos(pi * (k + i) / k), sin(pi * (k + i) / k), (2 * i + 1) / k) It is left as a trivial exercise for the reader to prove than there are O(n^2) occlusions between elements of this polygon when it is viewed from (0, 0, +\infty). -- John Merrill / merrill@bucasb.bu.edu / harvard!bu.edu!bucasb!merrill
jroth@allvax.dec.com (Jim Roth) (08/15/90)
In article <839@stat.fsu.edu>, naras@stat.fsu.edu (B. Narasimhan) writes... >Consider two line segments in R3 determined by points (x(1),y(1),z(1)) and >(x(2),y(2),z(2)), and (x(3),y(3),z(3)) and (x(4),y(4),z(4)) respectively. >I want to project these line segments on >the XY plane in such a way that I depict which segment crosses over and >which one goes under. This I can do in a straightforward way by computing >the intersection point of the projected segments (if there is one), then >projecting this point back to the original line segments and checking the >z-coordinate. >Now suppose I have a sequence of points (x(1),y(1),z(1))....(x(n),y(n),z(n)) >such that a line segment connects (x(i),y(i),z(i)) and (x(i+1),y(i+1),z(i+1)). >The last point is connected to (x(1),y(1),z(1)). >If I use the above approach, I would have an O(n^2) algorithm. >Is there an efficient algorithm for projecting the closed figure so that >I depict the over/under aspect of the crossings? Note that I need to know >the identity of each of the segments going under or above. Yes - such algorithms are in the so-called field of "computational geometry". There are monographs on the subject, such as "Introduction to Computational Geometry" by Preperata & Shamos, or "Algorithms in Computational Geometry" by Edelsbrunner (both Springer Verlag.) For your problem a good approach would be a plane sweep algorithm. Basically, you sort the Y coordinates (say) and sweep a line thru the Y coordinates, maintaining an active line list of lines crossing the sweep line as you go along. At each vertex new intersections will be tested beteween lines adjacent in the active edge list and those incident on the next vertex; these intersections will be added to the queue of events to be handled. Time is O((n+s)log(n)), n = number of vertices, s = number of intersections. See in particular the paper "Plane sweep algorithms for intersecting geometric figures" J. Nievergelt & F. Preperata Communications of the ACM 25 #10, Oct 1982, pp 739-747 I've used such algorithms and they are quite fast. - Jim