Xref: utzoo sci.math:12030 comp.graphics:12865
Path: utzoo!attcan!uunet!wuarchive!zaphod.mps.ohio-state.edu!sdd.hp.com!decwrl!bacchus.pa.dec.com!shlump.nac.dec.com!ryn.esg.dec.com!allvax!jroth
From: jroth@allvax.dec.com (Jim Roth)
Newsgroups: sci.math,comp.graphics
Subject: Re: Projection question.
Summary: Use a plane sweep algorithm
Message-ID: <2514@ryn.esg.dec.com>
Date: 14 Aug 90 22:35:41 GMT
Sender: guest@ryn.esg.dec.com
Followup-To: sci.math
Organization: Digital Equipment Corporation
Lines: 45


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