Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!cbatt!ihnp4!qantel!lll-lcc!lll-crg!seismo!umcp-cs!aplcen!osiris!phil
From: phil@osiris.UUCP (Philip Kos)
Newsgroups: net.graphics
Subject: Re: Intersecting lines
Message-ID: <889@osiris.UUCP>
Date: Fri, 26-Sep-86 08:46:45 EDT
Article-I.D.: osiris.889
Posted: Fri Sep 26 08:46:45 1986
Date-Received: Tue, 30-Sep-86 05:48:07 EDT
References: <445@hp-sdd.UUCP> <534@bambi.UUCP>
Distribution: net
Organization: Johns Hopkins Hospital
Lines: 24
Summary: similar, but probably not useful

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

I had to do something similar as part of a CAD filtering program I
wrote in grad school, but I was only dealing with closed, non-
degenerate rectangles with sides oriented parallel to the X-Y axes.
There was an algorithm in Knuth I was going to use but I decided to
take advantage of the the parallel rectangles constriction to use a
faster one.  The resulting filter was pretty quick, even for images of
around 1000 rectangles.

The Knuth algorithm would work for you but it would still be O(n^2)...


Phil Kos			  ...!decvax!decuac
The Johns Hopkins Hospital                         > !aplcen!osiris!phil
Baltimore, MD			...!allegra!umcp-cs

"And if a man among you
Got no sin upon his hand,
Let him cast a stone at me
For playing in the band." - Robert Hunter