Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!lll-crg!lll-lcc!pyramid!decwrl!magic!stolfi
From: stolfi@magic.DEC.COM (Jorge Stolfi)
Newsgroups: net.graphics
Subject: Re: Intersecting lines
Message-ID: <1170@magic.DEC.COM>
Date: Wed, 24-Sep-86 11:37:54 EDT
Article-I.D.: magic.1170
Posted: Wed Sep 24 11:37:54 1986
Date-Received: Wed, 24-Sep-86 22:17:14 EDT
References: <445@hp-sdd.UUCP>
Reply-To: stolfi@magic.UUCP (Jorge Stolfi)
Followup-To: net.graphics
Distribution: net
Organization: DEC Systems Research Center, Palo Alto
Lines: 66
Keywords: detecting intersections, segment intersections, Bentley, Ottman
Summary: An algorithm by Bentley and Ottman does it in O((n+k) log n) time.
X-Edited: last by stolfi on Wed Sep 24 08:37:19 1986 PDT


Nick Flor wrote:
>   
>   Does anyone out there have a good algorithm for determining if
>   a polygon line segment intersects another line segment in the
>   same polygon?  (Besides the O(n^2) one where you calculate the
>   intersection of the line segment with each segment in the
>   polygon) 

The standard algorithm for this sort of things is described in

%A {Jon Louis Bentley and Thomas Ottman}
%T {Algorithms for reporting and counting geometric intersections.}
%P {{a.} Tech. Rep. CMU-CS-78-135, Carnegie-Mellon Univ. (Aug. 1978). }
%P {{b.} IEEE Trans. on Computers Vol C-28 No. 9 (Sep. 1979), 643--647.}

They consider the following problem: given n line segments in the 
plane, find and report all intersecting pairs.
Their algorithm sweeps the plane with a vertical line, keeping track
of the `active list' of segments that intersect the line (and their ordering).

The algorithm maintains also a sorted `event queue' containing the
x-positions ahead of the sweeping line where something intersting is
going to happen.  An interesting event consists of the sweeping line
hitting either a segment's left endpoint, a right endpoint, or an
intersection between two CONSECUTIVE segments of the current active
list.  At that moment, either a new segment will be inserted in the active
list, or an old segment will be deleted, or two consecutive segments
will exchange their positions.  

Initially, the event queue contains only the sorted x-coordinates of
all segment endpoints; the active list is empty, and the sweep line is
at x = minus infinity.  As the sweep proceeds, the algorithm may
discover some intersections ahead of the current sweep line, which also
get inserted in the event queue.  The main loop is then: remove the
next event from the queue, advance the sweep line up to that x-position,
update the active list, check if the new pairs of adjacent segments
intersect ahead of the sweep line, add any such intersections to the
event queue, and repeat.  

With the proper data structures, each iteration can be performed in
O(log n) time. The total time is then O((n + k) log n), where k
is the totalnumber of intersections.

If you only need to know ONE intersection, there is a much simpler
algorithm that does it in O(n log n) time:

%A {Michael Ian Shamos and and Dan Hoey}
%T {Geometric intersection problems.}
%P {Proc. 17th IEEE FOCS --- Annual Symposium on
   Foundations of Computer Science (October 1976), 208--215.}

Hope this will help,

  Jorge Stolfi
  
V V V V V V V V V V V V V V V V V V V V V V V V V V V V V V V V V V V V 

BTW: Bob Wallis, are you there? I got a message from you, but
the Return-Path seems to be screwed up: pyramid!weitek!somewhere!wallis.
Weitek said somewhere is nowhere to be found...

^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ 

ARPA: stolfi@src.dec.com
UUCP: ..{..decvax,ucbvax,allegra}!decwrl!stolfi
DISCLAIMER: My employer probably will not like this disclaimer.