Article View: net.graphics
Article #1470Re: Intersecting lines
From: Philip Kos
Date: Fri, 26 Sep 1986 12:46
Date: Fri, 26 Sep 1986 12:46
24 lines
1629 bytes
1629 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) 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
Technical Details
Message-ID:
<889@osiris.UUCP>Path:
arc1-ca.pugleaf.net!utzoo!watmath!clyde!cbatt!ihnp4!qantel!lll-lcc!lll-crg!seismo!umcp-cs!aplcen!osiris!philReferences:
<445@hp-sdd.UUCP> <534@bambi.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!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