Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!mnetor!seismo!ll-xn!ames!xanth!kent From: kent@xanth.UUCP (Kent Paul Dolan) Newsgroups: comp.graphics Subject: Re: Point inside of polygon revisited... Message-ID: <1365@xanth.UUCP> Date: Mon, 22-Jun-87 02:49:37 EDT Article-I.D.: xanth.1365 Posted: Mon Jun 22 02:49:37 1987 Date-Received: Tue, 23-Jun-87 05:32:20 EDT References: <948@elrond.CalComp.COM> <260@brandx.rutgers.edu> Reply-To: kent@xanth.UUCP (Kent Paul Dolan) Organization: Old Dominion University, Norfolk Va. Lines: 132 Keywords: ray tracing, graphics, polygon intersection Summary: FLAME! Also the solution to the problem. In article <260@brandx.rutgers.edu> webber@brandx.rutgers.edu (Webber) writes: ]In article <948@elrond.CalComp.COM>, amamaral@elrond.CalComp.COM (Alan Amaral) writes: ]] ]] A while ago someone asked for a method for determining whether or not ]] a point was inside or outside of a polygon. I have the replies, and ]] am in the process of implementing just such a function, but have come ]] up against what I view as a significant problem. ... ] ]A rather interesting article was written on the problem of this ]method: ] A. R. Forrest, ``Computational geometry in practice,'' appeared in: ] R. A. Earnshaw (ed.), Fundamental Algorithms for Computer ] Graphics, NATO ASI Seires Vol. F17, Springer-Verlag, 1985, 707-724. ] ] ]] HELP! ] ]Said author's conclusions were: ] ] Simply by examining an apparently trivial operation which must ] have been implemented thousands of times in practice, we have ] shown that such operations are by no means trivial. It is ] doubtful indeed whether any completely sucessful implementations ] exist or indeed can ever exist. We tend to take for granted in ] many algorithms the ability to implement these primitives successfully ] and we must realise that we do so at our peril. Implementation ] requires careful attention to various geometric cass which must ] be correctly identified and to all arithmetic operations involved. ] The precision to which these operations must be carried out is ] considerably higher than many realise. ] ]Enjoy. ] ]------ BOB (webber@aramis.rutgers.edu ; rutgers!aramis.rutgers.edu!webber) [This is not a flame at Bob Webber, who is probably the salt of the earth, but at the author he quotes, who seems modestly retarded.] Oh, come on: "Anything I don't know how to do must be extremely difficult, and probably requires magic to accomplish? And besides that, it probably isn't even possible, so why bother to try?" Really! The problem is trivial, and so is the solution; I did this one ten years ago, it took five minutes thought after I saw that the problem existed, and there are probably thousands (well, dozens) of other people who did it right, too, thought nothing about it, and went on about their jobs. Unlike Fermet, I have _lots_ of room on the page, ;-) so here goes: Reprise: a commonly recommended method for determining whether a point is inside a polygon is to draw a ray (say to the horizontal to the left) to infinity, then count intersections with the polygon boundary. If the count is even, the point is exterior to the polygon, if the count is odd, the point is interior to the polygon. If the point lies on the boundary, you use some default (I chose inside as my default). A problem arises when the ray penetrates a vertex of the boundary where it should be counted as one intersection, because the naive approach will find one intersection with each of the two lines that make up the vertex, and count twice. The reason for the problem is that the point of intersection is the end of two lines. The solution is to make it the end of only one line. You do this by making each line have only one end, in an appropriate way. In one dimension, in math, this is called an open ended interval. I don't know if it has a name in two dimensions. What I did: I put in a check for being on the boundary that flagged the point as (default = ) interior if it was on the boundary, and exited the count loop early. For this check, the lines were double ended. I ignored all horizontal lines (in general, lines parallel to the ray) when counting intersections. For all non-horizontal lines, I made the upper end open, and the lower end closed. Now, up pointing vertices count zero intersections, down pointing vertices count two intersections, and sideways pointing vertices count 1 intersection. This treats all the anticipated weird cases right; if your count says you were inside the polygon (think of counting "in from infinity", rather than "out from the point in question", the result's the same), crossing: / at the vertex counts once, and you're now outside; \ crossing: /\ at the vertex counts zero, and you're still inside; crossing: \/ at the vertex counts twice, and you're still outside; crossing: __/ at the vertices counts once; and you're now outside / crossing: __ / \ at the vertices counts zero; and you're still inside; crossing: \__/ at the vertices counts two times; and you're still inside; etc. It galls me a lot to see someone make such a fuss over problems _he_ doesn't know how to solve. A moments thought would have sufficed to realize that _lots_ of packages exist that do pixel fills of characters described by their boundaries and magnified to fit the font size, and that therefore someone, somewhere must have solved this problem correctly. That happened to be the application I "discovered" the above trick while doing. It has since filled millions of characters, at all orientatins, without a bobble. Have a nice day anyway, I'll be better tomorrow. ;-) Maybe. :-( Kent. -- Kent Paul Dolan, LCDR, NOAA, Retired; ODU MSCS grad student // Yet UUCP : kent@xanth.UUCP or ...{sun,harvard}!xanth!kent // Another CSNET : kent@odu.csnet ARPA : kent@xanth.cs.odu.edu \\ // Happy USPost: P.O. Box 1559, Norfolk, Virginia 23501-1559 \// Amigan! Voice : (804) 587-7760 -=][> Last one to Ceres is a rotten egg! -=][>