Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!caip!princeton!allegra!ulysses!bellcore!petrus!magic!science!bambi!steve
From: steve@bambi.UUCP (Steve Miller)
Newsgroups: net.graphics
Subject: Re: Intersecting lines
Message-ID: <534@bambi.UUCP>
Date: Tue, 23-Sep-86 23:09:50 EDT
Article-I.D.: bambi.534
Posted: Tue Sep 23 23:09:50 1986
Date-Received: Thu, 25-Sep-86 03:45:23 EDT
References: <445@hp-sdd.UUCP>
Distribution: net
Organization: The Fantasy Factory
Lines: 13

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

Well... you don't have to compute the actual intersection to determine
whether or not two lines intersect, but the order of the problem
remains the same.  However, never overlook the virtue of comparison
to some simple bounding region, such as a box or circle.  Also, I have
done some work, with ambiguous results, with bounding rectangles applied
to parts of polygons.  Anyone else?

	Steve Miller ihnp4!bellcore!bambi!steve