Xref: utzoo sci.math:12015 comp.graphics:12843
Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!uakari.primate.wisc.edu!uflorida!stat!naras
From: naras@stat.fsu.edu (B. Narasimhan)
Newsgroups: sci.math,comp.graphics
Subject: Projection question.
Message-ID: <839@stat.fsu.edu>
Date: 14 Aug 90 17:47:35 GMT
Reply-To: naras@stat.fsu.edu (B. Narasimhan)
Organization: Dept. of Statistics, Florida State Univ.
Lines: 27

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. 
----------------------------------------------------------------------