re point within a polygon scrowe hemel bull co uk simon crowe writes i am looking for an algorithm to determine if a given point is bound by a polygon does anyone have any such code or a reference to book containing information on the subject well it s been a while since this was discussed so i take the liberty of reprinting without permission so sue me eric haines reprint of the very interesting discussion of this topic jonas o o x snip snip x o o give a man a fish and he ll eat one day give a man a fishing rod and he ll laze around fishing and never do anything with that in mind i reprint without permission so sue me relevant information posted some years ago on this very problem note the early use of postscript technology predating many of this year s papers listed in the april st siggraph program announcement posted here a few days ago eric intersection between a line and a polygon undecidable by dave baraff tom duff from deb charisma graphics cornell edu newsgroups comp graphics keywords p np jordan curve separation ursyhon metrization theorem organization program of computer graphics in article ncsmith ndsuvax uucp timothy lyle smith writes i need to find a formula algorithm to determine if a line intersects a polygon i would prefer a method that would do this in as little 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 separated now the jordan curve separation theorem 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 possibly 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 co 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 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 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 principia mathematica newton i cambridge university press cambridge england sorry i don t have an isbn for this an introduction to automata theory languages and computation hopcroft j and ulman j the c programming language kernighan b and ritchie d a tale of two cities dickens c from td alice uucp tom duff summary overkill organization at t bell laboratories murray hill nj 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 ii pp lemma 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 is delivered since it will be able to complete an infinite loop in milliseconds with scatter gather from deb svax cs cornell edu david baraff 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 siggraph paper from caltech that deals with this j o n a s y n g v e s s o n email jonas y isy liu se dept of electrical engineering voice university of linkoping sweden fax
