ncsmith@ndsuvax.UUCP (Timothy Lyle Smith) (09/28/89)
I need to find a formula/algorithm to determine if a line intersects a polygon. I would perfer a method that would do this in as litte time as possible. I need this for use in a forward raytracing program. -- Tim Smith North Dakota State University, Fargo, ND 58105 UUCP: ...!uunet!ndsuvax!ncsmith | 90% of the people on this planet BITNET: ncsmith@ndsuvax.bitnet | are crazy and the rest of us are INTERNET: ncsmith@plains.NoDak.edu | in grave danger of contamination
deb@svax.cs.cornell.edu (David Baraff) (09/29/89)
In article <2972@ndsuvax.UUCP> ncsmith@ndsuvax.UUCP (Timothy Lyle Smith) writes: > > I need to find a formula/algorithm to determine if a line intersects > a polygon. I would perfer a method that would do this in as litte > time as possible. I need this for use in a forward raytracing > program. I think that this is a very difficult problem. To start with, lines and polygons are semi-algebraic sets which both contain uncountable number of points. Here are a few off-the-cuff ideas. First, we need to check if the line and the polygon are seperated. Now, the Jordan curve seperation theoreom says that the polygon divides the plane into exactly two open (and thus non-compact) regions. Thus, the line lies completely inside the polygon, the line lies completely outside the polygon, or posssibly (but this will rarely happen) the line intersects the polyon. Now, the phrasing of this question says "if a line intersects a polygon", so this is a decision problem. One possibility (the decision model approach) is to reduce the question to some other (well known) problem Q, and then try to solve Q. An answer to Q gives an answer to the original decision problem. In recent years, many geometric problems have been successfully modeled in a new language called PostScript. (See "PostScript Language", by Adobe Systems Incorporated, ISBN # 0-201-10179-3, co. 1985). So, given a line L and a polygon P, we can write a PostScript program that draws the line L and the polygon P, and then "outputs" the answer. By "output", we mean the program executes a command called "showpage", which actually prints a page of paper containing the line and the polygon. A quick examination of the paper provides an answer to the reduced problem Q, and thus the original problem. There are two small problems with this approach. (1) There is an infinite number of ways to encode L and P into the reduced problem Q. So, we will be forced to invoke the Axiom of Choice (or equivalently, Zorn's Lemma). But the use of the Axiom of Choice is not regarded in a very serious light these days. (2) More importantly, the question arises as to whether or not the PostScript program Q will actually output a piece of paper; or in other words, will it halt? Now, PostScript is expressive enough to encode everything that a Turing Machine might do; thus the halting problem (for PostScript) is undecidable. It is quite possible that the original problem will turn out to be undecidable. I won't even begin to go into other difficulties, such as aliasing, finite precision and running out of ink, paper or both. A couple of references might be: 1. Principia Mathematica. Newton, I. Cambridge University Press, Cambridge, England. (Sorry, I don't have an ISBN# for this). 2. An Introduction to Automata Theory, Languages, and Computation. Hopcroft, J and Ulman, J. 3. The C Programming Language. Kernighan, B and Ritchie, D. 4. A Tale of Two Cities. Dickens, C.
tuna@athena.mit.edu (Kirk 'UhOh' Johnson) (09/29/89)
In article <32610@cornell.UUCP> deb@charisma.graphics.cornell.edu writes: % In article <2972@ndsuvax.UUCP> ncsmith@ndsuvax.UUCP writes: % > % > I need to find a formula/algorithm to determine if a line intersects % > a polygon. I would perfer a method that would do this in as litte % > time as possible. I need this for use in a forward raytracing % > program. % % I think that this is a very difficult problem. To start with, % lines and polygons are semi-algebraic sets which both contain % uncountable number of points. Here are a few off-the-cuff % ideas. % % [ .... egregious volumes of hairy sounding stuff deleted .... ] look in any respectable introductory graphics book (foley and van dam, newman and sproull, etc.) and you'll see that this is a solved (many times over) problem. it is definitely _FAR_ from undecidable; it's actually fairly simple to solve. if after you've found such a book and read what it has to say you find yourself still completely confused, then try asking the net for guidance. kirk
td@alice.UUCP (Tom Duff) (09/29/89)
>> >> I need to find a formula/algorithm to determine if a line intersects >> a polygon. I would perfer a method that would do this in as litte >> time as possible. I need this for use in a forward raytracing >> program. >I think that this is a very difficult problem. >(Suggests postscript, mentions turing-completeness problem, etc.) The situation is not nearly as bleak as Baraff suggests (he should know better, he's hung around The Labs for long enough). By the well known Dobbin-Dullman reduction (see J. Dullman & D. Dobbin, J. Comp. Obfusc. 37,ii: pp. 33-947, lemma 17(a)) line-polygon intersection can be reduced to Hamiltonian Circuit, without(!) the use of Grobner bases, so LPI (to coin an acronym) is probably only NP-complete. Besides, Turing-completeness will no longer be a problem once our Cray-3 is delivered, since it will be able to complete an infinite loop in 4 milliseconds (with scatter-gather.)
deb@svax.cs.cornell.edu (David Baraff) (09/29/89)
In article <9983@alice.UUCP> td@alice.UUCP (Tom Duff) writes: >>> >>> I need to find a formula/algorithm to determine if a line intersects >>> a polygon. I would perfer a method that would do this in as litte >>> time as possible. I need this for use in a forward raytracing >>> program. > >>I think that this is a very difficult problem. >>(Suggests postscript, mentions turing-completeness problem, etc.) > >The situation is not nearly as bleak as Baraff suggests (he should know >better, he's hung around The Labs for long enough). By the well known >Dobbin-Dullman reduction line-polygon intersection can be >reduced to Hamiltonian Circuit, without(!) the use of Grobner bases, Well, sure its no worse than NP-complete, but that's ONLY if you restrict yourself to the case where the line satisfies a Lipschitz condition on its second derivative. (I think there's an '89 SIGGRAPH paper from Caltech that deals with this). -David
koren@hpfelg.HP.COM (Steve Koren) (09/30/89)
> > > > I need to find a formula/algorithm to determine if a line intersects > > a polygon. I would perfer a method that would do this in as litte > > time as possible. I need this for use in a forward raytracing > > program. > I think that this is a very difficult problem. To start with, > lines and polygons are semi-algebraic sets which both contain If you are writing this for a ray tracer, I assume you really mean "line" or "half-line" and not "line-segment". In that case, can't you just check the intersection of the line and each of the edges of the polygon? If it hits any edge, it passes through the polygon. This is sort of similar to an algorithm that determines if a point is inside a polygon. You draw a line from the point to infinity, and count the number of edges of the polygon the line crosses. If it crosses an even number, you're outside. If it crosses an odd number, you're inside. This even takes care of polygons with "holes" in them. There's some code that does basically this in QRT, you can pull it out and use it if you wish. Its in a file called "pattern.c", if you have the QRT source. Its a little hacked out, but its only a few lines. Hope this helps. - steve (koren@hpfela.HP.COM) PS - oh by the way, there's a fairly simply extention to this if you want to use line-segments instead of lines or half-lines. Proceed as above: if you hit a polygon-side you hit the polygon. If you dont hit a side, see if both points are inside or outside the polygon (easy to do; see the code I pointed out above). That will tell you if the line is competely inside or outside the polygon. If one point is inside and one is outside but you didn't find an interection with the polygon side, somethings messed up in the code. PPS - if the line doesn't lie in the same plane as the polygon, the problem is even simpler. Just find the intersection point of the line and the plain of the polygon. If this point is inside the polygon (see the test above), your line hit the polygon somewhere.
brown@proline.cs.unc.edu (Randy Brown) (10/01/89)
In article <14759@bloom.MIT.EDU> tuna@athena.mit.edu (Kirk Johnson) writes: * In article <32610@cornell.UUCP> deb@charisma.graphics.cornell.edu writes: * % In article <2972@ndsuvax.UUCP> ncsmith@ndsuvax.UUCP writes: * % > * % > I need to find a formula/algorithm to determine if a line intersects * % > a polygon. I would perfer a method that would do this in as litte * % > time as possible. * % * % I think that this is a very difficult problem. To start with, * % lines and polygons are semi-algebraic sets which both contain * % uncountable number of points. Here are a few off-the-cuff ideas. * % [ .... egregious volumes of hairy sounding stuff deleted .... ] ---> (but funny) <--- -->But an IMPORTANT inclusion, which was the "Tale of Two Cities" reference.<-- *it is definitely _FAR_ from undecidable; it's actually fairly simple to solve. *if after you've found such a book and read what it has to say you find *yourself still completely confused, then try asking the net for guidance. *kirk I'm sorry, but I couldn't find the information about polygons in the referenced book, "A Tale of Two Cities", by Dickens. Do the vertices have to be ordered in clockwise or counterclockwise order, or does it matter? Dickens was quiet on the subject, and Newton has been dead even longer. But the ISBN for Principia Mathematica is #1066-ITS-A-JOKE. ---- brown@cs.unc.edu or uunet!mcnc!unc!brown "No-one gets a lifetime rehearsal, as specks of dust, we're universal."
ksbooth@watcgl.waterloo.edu (Kelly Booth) (10/02/89)
In article <14759@bloom-beacon.MIT.EDU> tuna@athena.mit.edu (Kirk 'UhOh' Johnson) writes: > >look in any respectable introductory graphics book (foley and van dam, >newman and sproull, etc.) and you'll see that this is a solved (many >times over) problem. > >it is definitely _FAR_ from undecidable; it's actually fairly simple >to solve. > >if after you've found such a book and read what it has to say you find >yourself still completely confused, then try asking the net for >guidance. > >kirk I think this is what the original posting was trying to say. But apparently his :) key was broken when he posted.
mitchell@cbmvax.UUCP (Fred Mitchell - QA) (10/03/89)
A simpler way of thinking about it is to: 1) compute the plane the polygon lies in 2) calculate the point where line intersects plane 3) determine if point lies inside or outside of polygon. A possible way of determining 3) would be to do a bounding box around polygon and if point lies outside bounding box, you know that its outside. If in, you've more checking to do. Since I have done this in the Ray-Trace package I'm currently working on, drop me E-mail if you want more details.