Re: Intersecting lines

Article View: net.graphics

Article #1465

#1465

From: Steve Miller
Date: Wed, 24 Sep 1986 03:09

13 lines
1222 bytes

> 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

Technical Details

Message-ID: <534@bambi.UUCP>

Path: arc1-ca.pugleaf.net!utzoo!mnetor!seismo!caip!princeton!allegra!ulysses!bellcore!petrus!magic!science!bambi!steve

References: <445@hp-sdd.UUCP>

Show Full Headers

Complete Article Headers

Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: arc1-ca.pugleaf.net!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

Reply to Parent Message