nick@hp-sdd.UUCP (Nick Flor) (09/23/86)
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) Thanks in advance. Nick -- Standard disclaimer: The above opinions are my own and do not necessarily reflect those of my employers. Nick V. Flor -- This is just another permutation of sh*t. ..hplabs!hp-sdd!nick "What's going down in this world, you got no idea. Believe me." The Comedian
steve@bambi.UUCP (Steve Miller) (09/24/86)
> 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
stolfi@magic.DEC.COM (Jorge Stolfi) (09/24/86)
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.
phil@osiris.UUCP (Philip Kos) (09/26/86)
> 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