amamaral@elrond.CalComp.COM (Alan Amaral) (06/15/87)
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.
To recap, the theorum put forth was that given a bounded area on a plane
and a point on the plane, one could determine whether the point was inside
the area, or outside the area by determining how many edges an arbitrary
ray starting at the given point crossed. (and a partridge in a pear tree...)
If the ray crossed an even number of edges, then the point is outside of the
area, and it's inside if the number of crossings is odd.
This all works well and good, EXCEPT for one particular case. What if the
ray happens to cross 2 edges at exactly the same point (i.e. at a corner)?
Take the two following cases:
+
/|
1 / |
/ |
/ |
<-------+--x | 3
\ |
\ |
2 \ |
\|
+
Intersection point (x) is inside of the bounded area, but there are 2 crossings.
You could count only 1 crossing at a corner (i.e. crossing is only valid if edge
T value is 0 < T <= 1) but that fails in the next case:
<-----+--------x
|\
| \
1| \2
| \
+----+
3
Has anyone solved this particular problem, or do you just ignore it?
I have tried all sorts of schemes to work around this particular problem,
but have always been able to come up with some kind of pathological case
where a concave polygon will fail.
HELP!
--
uucp: ...decvax!elrond!amamaral I would rather be a
phone: (603) 885-8075 fool than a king...
us mail: Calcomp/Sanders DPD (PTP2-2D01)
Hudson NH 03051-0908amamaral@elrond.UUCP (06/15/87)
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. > I forgot to say in that last message that I am working in 3 space, so the concepts of local minima and maxima are not as straight forward as in 2 space. (are they?) I have been working on this particular problem on and off for a while now, with no luck. Thanks for any help... -- uucp: ...decvax!elrond!amamaral I would rather be a phone: (603) 885-8075 fool than a king... us mail: Calcomp/Sanders DPD (PTP2-2D01) Hudson NH 03051-0908
webber@brandx.rutgers.edu.UUCP (06/16/87)
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)
sdh@thumper.UUCP (06/16/87)
In article <948@elrond.CalComp.COM>, amamaral@elrond.UUCP writes: > To recap, the theorum put forth was that given a bounded area on a plane > and a point on the plane, one could determine whether the point was inside > the area, or outside the area by determining how many edges an arbitrary > ray starting at the given point crossed. (and a partridge in a pear tree...) > If the ray crossed an even number of edges, then the point is outside of the > area, and it's inside if the number of crossings is odd. > > This all works well and good, EXCEPT for one particular case. What if the > ray happens to cross 2 edges at exactly the same point (i.e. at a corner)? Here's a way around your problem: pick a ray that doesn't cause the problem you described. You said the ray is arbitrary, so use that fact to your advantage. The most effective way to do this is to make sure that every point on the polygonis not on the ray. The problem with this is that you have to check every point. Too slow. A somewhat better (but still fallable) way than arbitrarily picking a ray, is to use a vector that is defined by the given point and the midpoint of a particular edge. The only reasone for this is that it will be fast, and only less fallable in the sense that you know it will definitely cross ONE edge without intersecting a point. Any other suggestions? Steve Hawley
shebs@utah-cs.UUCP (Stanley Shebs) (06/16/87)
In article <948@elrond.CalComp.COM> amamaral@elrond.CalComp.COM (Alan Amaral) writes: >To recap, the theorum put forth was that given a bounded area on a plane >and a point on the plane, one could determine whether the point was inside >the area, or outside the area by determining how many edges an arbitrary >ray starting at the given point crossed. (and a partridge in a pear tree...) >If the ray crossed an even number of edges, then the point is outside of the >area, and it's inside if the number of crossings is odd. > >This all works well and good, EXCEPT for one particular case. What if the >ray happens to cross 2 edges at exactly the same point (i.e. at a corner)? I ran into this problem a few years ago while working at Boeing. It's not particularly important which ray you pick, so if the line did hit right on an endpoint, I just perturbed the ray a little bit and tried again. This takes care of every possible crossing through a vertex - no special cases. Termination can be guaranteed by making the perturbations sufficiently small that it would take more of them than there are vertices in the polygon to march all the way around the point. An easy way to do this is just to increment the y component of the end of the ray while leaving x fixed - the rays get more and more vertical, but each will be different... Performance is not bad, because with floating point computation, the chances of having to do a perturbation are 1/bits-in-a-float or thereabouts. Also works in 3D, assuming perturbation lies in the plane of the polygon, and could be extended to polyhedra. Not really workable with integer computation though. Alas, after I had put the algorithm together (was actually for computing intersections of squares with polygons), proved correctness, and demonstrated an implementation, it was discarded because it was "too general" (the polygons supposedly had only vertical and horizontal edges). Now you know why I have a low opinion of military contractors and the DoD... stan shebs shebs@cs.utah.edu
cbn@wiley.UUCP (06/16/87)
The problem you describe in three dimensions has a very similar counterpart in two dimensions, if I understand your problem correctly. A popular algorithm for scan converting polygons in 2D performs a similar "intersection counting" function. First, the algorithm attempts generates a list of the points at which the edges of a given polygon intersect with the scan lines of the raster device. This is similar to your calculation of ray intersections with the object planes. Once the list of intersections is generated, they are sorted by scan line and the points on a given scan line are "paired up". The pairing is similar to your "odd-even" test, in that the space between any two pairs should be inside the polygon (on that scan line) and can be displayed with that polygon's color. The problem occurs when a scan line EXACTLY intersects a vertex of the polygon. (Sound familiar?) Depending upon the type of vertex, you either count it as a single or double intersection. Your first example (if considered a 2D polygon in the xy plane) would count as a single intersection, while your second example would count as two intersections. In the latter case, the resulting two intersections would pair up and either be displayed as a point, or as nothing at all. The way you determine what type of vertex you're dealing with, is to examine the slope of the edges that make up the vertex. In the 2D case, if the y values of the edges are BOTH LARGER than at the vertex in question, the point is a local "minimum". Conversely, if the y values of the edges are BOTH SMALLER than at the vertex in question, the point is a local "maximum". If the vertex is a local maximum or minimum, count the point as TWO intersections, otherwise count it as one. Now, there must be a similar mechanism in the 3D world. Look at the equations of the planes that intersect at the edge in question and see if the produce an edge that is a local maximum or minimum. Your first exanmple should not satisfy the test and should be counted as a single intersection, instead of two. The second case is definitely a maximum ( with respect to the vertical axis in your drawing) and should be counted as two intersection (or possibly no intersections, depending upon your need.) Most good graphics texts discuss scan conversion. Maybe referring to them will be of help. I can recommend "Procedural Elements of Computer Graphics" by David F. Rogers (McGraw-Hill) as a good, all-around treatment of the subject. I've implemented several scan conversion algorithms and this one works well. I haven't yet done any ray-tracing, so this is postulation of a known solution to what seems to be a very similar problem. Good Luck. Chris B. Newton TRW, Redondo Beach, Ca. cbn@wiley
bobr@zeus.UUCP (06/16/87)
In 2-space, the problem is still trivial. Given an interior point, the infinite ray from this interior point over which crossings are counted, and a starting vertex on the polygon, do the following: Create a state variable which indicates whether the last non-collinear vertex was above or below the line containing the ray. Initialize this with a value appropriate for the initial polygonal point. Walk the polygon, examining each vertex in sequence. If the vertex lies on the "other" side of the line, update the state variable and determine the crossing point. If it lies on the ray, increment the crossing count. If a vertex lies on the line, no crossing has occurred. If the next vertex is on the same side, no crossing has occurred. If one or more vertices lie on the line, no crossing calculations are performed. In your examples, case 1 counts as a single crossing. Beginning at the upper vertex of edge 1, the state variable ABOVE is set TRUE. The next vertex lies on the line, so move onto the next. The next vertex is below the line, so compute the intersection of edge 2, which lies on the ray. Bump the crossing count. ABOVE is now FALSE. The next vertex (which completes the loop of the polygon) is once again above the line. Update ABOVE and compute the intersection. The intersection is NOT on the ray, so at the conclusion of the algorithm, the crossing count is 1, indicating the point is inside the polygon. Consider case 2. This is a little tricky because the upper vertex of edge 1 lies on the line. The simplest solution is to therefore reject it as the intial vertex for the test and move on to the lower vertex of edge 1. Starting here ABOVE is FALSE. Going to the next vertex (right end of edge 3), this is also below, so no crossing test is done. Moving on to the next, it lies on the line, so no crossing test is done. Moving on to the next, which is the final vertex, it also lies below, so no crossing test is done. At the conclusion of the algorithm, the crossing count is 0, which is even, indicating that the point lies in the exterior of the polygon. -- Robert Reed, Tektronix CAE Systems Division, bobr@zeus.TEK
upl@puff.WISC.EDU (Future Unix Gurus) (06/17/87)
In article <4644@utah-cs.UUCP$ shebs@utah-cs.UUCP (Stanley Shebs) writes: $In article <948@elrond.CalComp.COM$ amamaral@elrond.CalComp.COM (Alan Amaral) writes: $ $$To recap, the theorum put forth was that given a bounded area on a plane $$and a point on the plane, one could determine whether the point was inside $$the area, or outside the area by determining how many edges an arbitrary $$ray starting at the given point crossed. (and a partridge in a pear tree...) $$If the ray crossed an even number of edges, then the point is outside of the $$area, and it's inside if the number of crossings is odd. $$ $$This all works well and good, EXCEPT for one particular case. What if the $$ray happens to cross 2 edges at exactly the same point (i.e. at a corner)? $ A solution that I always liked for its simplicity is to double the resolution horizontally and place your verticies on even lines and your scanned points on odd ones, or vice versa. Note that this is directly analogous to defining your verticies as being in the middle of a pixel location, rather than at its boundry. Jeff Kesselman upl@puff (temporarily, until I accept a job offer and move!)
upl@puff.WISC.EDU (Future Unix Gurus) (06/17/87)
Whoops! I ment double the resolution vertically, obviosuly, in my last message. Jeff Kesselman
sohan+@andrew.cmu.edu.UUCP (06/17/87)
A very non-rigorous outline of a method I am using for a particular application is: Given Polygon p[1..n], point being checked P Take a known external point E; compute the cross-product of (P->pi) and (P->E) for i in [1..n]. Whenever cross-products change sign (crosses 0 - break ties consistently), check if pi-1->pi cuts P->E. If the number of such intersections is even, then external else internal. This is pretty painless and correct (I think :-)) for all kinds of polygons. Hope this helps Sohan
garrity@garrity.UUCP (06/17/87)
> Has anyone solved this particular problem, or do you just ignore it? > I have tried all sorts of schemes to work around this particular problem, > but have always been able to come up with some kind of pathological case > where a concave polygon will fail. Yes, we encountered it. Someone here came up with a solution which works quite well. When the ray intersects a vertex of the line (i.e. the parameter of the intersection is 0 or 1), then "tweak" the ray to one side. This means that you offset the ray by a "small" amount to one side. You must be consistent about which side you tweak to. You then recompute the intersection. This seems to work in all cases. In fact, since our implementation worked with things other than lines (arcs, B-splines, etc.) I happen to know that it works in the nasty case where the ray goes through the start-end vertex of a circle. Hope this helps. -- -MPG- -- Mike Garrity -- -- -- snail: Applicon, a division of Schlumberger Systems, Inc. -- 829 Middlesex Tpk. -- P.O. box 7004 -- Billerica MA, 01821 -- -- uucp: {allegra|decvax|mit-eddie|utzoo}!linus!raybed2!applicon!garrity -- {amd|bbncca|cbosgd|wjh12|ihnp4|yale}!ima!applicon!garrity
beatyr@pur-ee.UUCP (Robert Beaty) (06/17/87)
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. > >To recap, ... > ...determining how many edges an arbitrary >ray starting at the given point crossed. >If the ray crossed an even number of edges, then the point is outside of the >area, and it's inside if the number of crossings is odd. > Boy I hope this isn't too silly, but why not do the obvious? Look in all four (or six in 3 space) unit vectors, and their negatives. i.e.: ^ | <-- x --> | v Then do something simple like taking the minima, or the greatest frequency, either odd or even. If it should work for any single ray then it should work for any conbination of rays. If you still can't get a 3/4 ths majority then rotate the four rays (or six rays) some angle theta ( or (theta,phi) ) and try again. Seems to me this should get you a simple result for all but the most odd-ball cases. (in those cases rotate by another theta and try again) Oh well.. this seemed so obvious to me it might be wrong. Bob ---------- ... ihnp4!pur-ee!beatyr <- usenet ... beatyr@ed.ecn.purdue.edu <- arpa-net ... beatyr@pur-ee.UUCP <- UUCP ----------
shebs@utah-cs.UUCP (Stanley Shebs) (06/17/87)
In article <790@thumper.UUCP> sdh@thumper.UUCP writes: >[...] >The most effective way to do this is to make sure that every point on the >polygonis not on the ray. The problem with this is that you have to check >every point. Too slow. Huh? You have to check intersections with every edge anyway, looking at the endpoints specifically comes almost for free. >[...] use a vector that is defined by the given point and the midpoint >of a particular edge. The only reasone for this is that it will be fast, >and only less fallable in the sense that you know it will definitely cross >ONE edge without intersecting a point. This seems like a useless piece of information - you still have to check every edge of the polygon, and you still have to do *something* if a vertex is right on the ray. It's easy enough to construct polygons and points with a ray going to a midpoint on an edge, with nearly half the vertices on the ray also. If all this is for ray tracing, then to get speed you want to avoid the full-blown polygon interior calculation as much as possible. Use bounding boxes at least, cut arbitrary polygons into convex ones, use coherence. A little preprocessing goes a long way... >Steve Hawley stan shebs
joer@nscpdc.NSC.COM (G. Wiz) (06/17/87)
In my solution of the problem, I am able to generate rays in multiple angles, It works like this. When the ray traverses a vertice of the polygon, the ray is marked as invalid and a new ray is generated. This is accomplished recursively. This continues until a ray is generated that does not traverse any vertice. Not elegant, but it works. -- /****************************************************************************** $ $ $ G. Wiz My opinions are mine! $ $ The Graphics Wizard $ $ National Semiconductor Corp. You are entitled to them! $ $ ICM Product Support $ $ 1-800-222-2433 $ $ $ ******************************************************************************/
bobr@zeus.UUCP (06/17/87)
Steve Hawley writes:
A somewhat better (but still fallable) way than arbitrarily picking a
ray, is to use a vector that is defined by the given point and the
midpoint of a particular edge. The only reason for this is that it
will be fast, and only less fallable in the sense that you know it will
definitely cross ONE edge without intersecting a point.
There is no guarantee that a ray which intersects the midpoint of some edge
will not also hit a vertex, even if the polygon is convex. Also, there is a
slight disadvantage in using an arbitrarily sloped ray, on the order of two
extra subtractions per intersection test.
--
Robert Reed, Tektronix CAE Systems Division, bobr@zeus.TEKmike@wsucshp.UUCP (Mike Kibler - CSB2056) (06/18/87)
Another approach is one that I used in a a polygon clipper.
It is derived from Sutherland and Hodgman's polygon
clipping algorithm described in Foley and Van Dam, Fundamentals
of Interactive Computer Graphics, July 1984. pp 450-455.
An application which could work for you, although expensive is:
It assumes the vertices are ordered in a clockwise manner.
At least three vertices in polygon.
Right handed coordinate system
still_in = true
v1 = Ist vertex in polygon.
v2 = 2nd vertex in polygon.
v3 = 3rd vertex in polygon.
polygon_outer_normal = cross_product(v3-v2,v1-v2)
more_vertices = num_vertices_in_polygon
While (more_vertices and still-in) do
more_vertices--
v2=next vertex in polygon
if (same_direction(cross product(v2-v1,point-v1),
polygon_outer_normal)) still-in = false
else
v1 = v2
end while
Of course all the normal cross product boundary checking must
be done.
---- Mike ( Those who can do, do, those who can't simulate! )
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Michael K. Kibler CSNET: mike%cs1.wsu.edu@RELAY.CS.NET
Computer Science Dept. UUCP: ..!ucbvax!ucdavis!egg-id!ui3!wsucshp!mike
Washington State Univ. BITNET: kibler@wsuvm1.BITNET
Pullman, WA. 99164-1210 PHONE: 509-335-2723 or 509-335-6636kenm@sci.UUCP (Ken McElvain) (06/19/87)
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. > > To recap, the theorum put forth was that given a bounded area on a plane > and a point on the plane, one could determine whether the point was inside > the area, or outside the area by determining how many edges an arbitrary > ray starting at the given point crossed. (and a partridge in a pear tree...) > If the ray crossed an even number of edges, then the point is outside of the > area, and it's inside if the number of crossings is odd. > > This all works well and good, EXCEPT for one particular case. What if the > ray happens to cross 2 edges at exactly the same point (i.e. at a corner)? > > Has anyone solved this particular problem, or do you just ignore it? > I have tried all sorts of schemes to work around this particular problem, > but have always been able to come up with some kind of pathological case > where a concave polygon will fail. > > HELP! Winding numbers work a bit better. Here is my version of a point in poly routine using a quadrant granularity winding number. The basic idea is to total the angle changes for a wiper arm with its origin at the point and whos end follows the polygon points. If the angle change is 0 then you are outside, otherwise you are in some sense inside. typedef struct point_ { float x,y; } point; pointinpoly(pt,cnt,polypts) point pt; /* point to check */ int cnt; /* number of points in poly */ point *polypts; /* array of points, */ /* last edge from polypts[cnt-1] to polypts[0] */ { int oldquad,newquad; point thispt,lastpt; float a,b; int wind; /* current winding number */ wind = 0; lastpt = polypts[cnt-1]; oldquad = whichquad(lastpt,pt); for(i=0;i<cnt;i++) { /* for each point in the polygon */ thispt = polypts[i]; newquad = whichquad(thispt,pt); if(oldquad!=newquad) { /* adjust wind */ /* * use mod 4 comparsions to see if we have * advanced or backed up one quadrant */ if(((oldquad+1)&3)==newquad) wind++; else if((((newquad+1)&3)==oldquad) wind--; else { /* * upper left to lower right, or * upper right to lower left. Determine * direction of winding by intersection * with x==0. */ a = lastpt.y - thispt.y; a *= (pt.x - lastpt.x); b = lastpt.x - thispt.x; a += lastpt.y * b; b *= pt.y; if(a > b) wind += 2; else wind -= 2; } } lastpt = thispt; } return(wind); /* non zero means point in poly */ } /* * Figure out which quadrent pt is in with respect to orig */ whichquad(pt,orig) point pt; point orig; { if(pt.x < orig.x) { if(pt.y < orig.y) quad = 2; else quad = 1; } else { if(pt.y < orig.y) quad = 3; else quad = 0; } } I pulled this out of some other code and hopefully didn't break it in doing so. There is some ambiguity in this version as to whether a point lying on the polygon is inside or out. This can be fairly easily detected though, so you can do what you want in that case. I tried to mail this but it bounced, maybe others will be interested. Ken McElvain decwrl!sci!kenm
kent@xanth.UUCP (Kent Paul Dolan) (06/22/87)
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! -=][>
planting@colby.WISC.EDU ( W. Harry Plantinga) (06/23/87)
Concerning the point-in-polygon problem the following appeared: >] >]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. >] >]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. >] To which Kent Dolan (kent@xanth.UUCP) replied: >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 . . .; >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. > To which I say: On the contrary, the problem is not trivial to solve for every possible case. Your solution, for example, will very likely fail for some instances of the problem. One problem that Forrest was speaking of is the large number of special cases in geometrical problems. These you may have solved correctly (but your solution shows that Forrest is right, there are lots of special cases). The other problem that Forrest mentions is that of the precision to which the arithmetic is carried out, even assuming the locations of the points are known exactly. You didn't mention taking any special precautions to avoid problems arising from numerical imprecision in determining whether line segments intersect, whether points are equal, etc. If you didn't, then your algorithm will fail in certain bad cases, for example, for lines that are very nearly parallel. In that case, numerical problems will cause your algorithm to judge some line segments to intersect when in fact they don't, or some line segments not to intersect when they do. In that case your algorithm will not correctly determine whether the point is in the polygon. Forrest is right that "we tend to take for granted in many algorithms the ability to implement . . . primitives successfully." The wisdom of recognizing false assumptions here is made the more pungent by the vehemence with which others believe them to be true. Harry Plantinga University of Wisconsin CS Department planting@cs.wisc.edu {allegra,ihnp4,heurikon,seismo}!speedy!planting (608) 233-1386
mdoerr@uklirb.UUCP (06/25/87)
/***** uklirb:comp.graph / elrond!amamaral / 9:17 pm Jun 15, 1987*/ 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. > I forgot to say in that last message that I am working in 3 space, so the concepts of local minima and maxima are not as straight forward as in 2 space. (are they?) I have been working on this particular problem on and off for a while now, with no luck. Thanks for any help... -- uucp: ...decvax!elrond!amamaral I would rather be a phone: (603) 885-8075 fool than a king... us mail: Calcomp/Sanders DPD (PTP2-2D01) Hudson NH 03051-0908 /* ---------- */ While researching the literature for clipping algorithms (concave 2D-polys with holes against concave 2D-polys with holes) I found the following paper that might be of help to you: Yehuda E. Kalay: Determining the Spatial Containment of a Point in General Polyhedra, Computer Graphics and Image Processing, Vol. 19, pp. 303-334, 1982 He first introduces a 2D-point-inside-polygon-test that is suitable for concave polygons with holes. Then he extends that algorithm to 3D by reducing the 3D problem in two different ways to the 2D case. This isn't as straight forward as it may sound. His 2D test is similiar to the solution proposed by Ed Post (hplabs!lewey!evp) in this news group. Hope this helps ... BTW: Has anyone REALLY UNDERSTOOD how Weiler's polygon comparision algorithm works? (see K. Weiler: Polygon Comparison using a Graph Representation, SIGGRAPH-80 proceedings in Computer Graphics, Vol. 14, pp. 10-18, 1980) I've understood the overall concept, but those difficult details have confused me as much as a potion of confusion :-) Who could enlighten me? ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Michael "The Turtle" Doerr %% /-------\ %% CS Department (FB Informatik) % o o % University of Kaiserslautern -{ o o o }==O D-6750 Kaiserslautern (West Germany) % o o % uucp: ...!seismo!unido!uklirb!mdoerr %% \-------/ %%
stephen@obed.UUCP (06/30/87)
In article <3731@spool.WISC.EDU>, planting@colby.WISC.EDU ( W. Harry Plantinga) writes:
: The other problem that Forrest mentions is that of the precision to
: which the arithmetic is carried out, even assuming the locations of
: the points are known exactly. You didn't mention taking any special
: precautions to avoid problems arising from numerical imprecision in
: determining whether line segments intersect, whether points are equal,
: etc. If you didn't, then your algorithm will fail in certain bad
: cases, for example, for lines that are very nearly parallel. In that
: case, numerical problems will cause your algorithm to judge some line
: segments to intersect when in fact they don't, or some line segments
: not to intersect when they do. In that case your algorithm will not
: correctly determine whether the point is in the polygon.
:
: Forrest is right that "we tend to take for granted in many algorithms
: the ability to implement . . . primitives successfully." The wisdom
: of recognizing false assumptions here is made the more pungent by the
: vehemence with which others believe them to be true.
You are ASSUMING problems here: for example: There is little problem with
roundoff error if the 'arbitrary line' is parallel to the X axis. All that
needs to be checked in that case is the 'y' values of the endpoints.
An intersecting line with both Y values the same is parallel. a non-zero
difference means it is non-parallel. Any roundoff error will be offset
in succeeding line segments. This assumes, of course, that the endpoints
of two ajacent lines are at exactly the same point (ignoring non-closure).
If you feel that I am wrong here, please send me an actual counter-example.
Stephen Samuel
{seismo!mnetor,ihnp4,vax135,ubc-vision}!alberta!obed!stephenplanting@colby.WISC.EDU ( W. Harry Plantinga) (06/30/87)
In article <402@pembina.UUCP> obed!stephen@alberta.UUCP (Stephen Samuel) writes: >In article <3731@spool.WISC.EDU>, planting@colby.WISC.EDU (W. Harry Plantinga (me)) writes: > : The other problem that Forrest mentions is that of the precision to > : which the arithmetic is carried out. >You are ASSUMING problems here: for example: There is little problem with >roundoff error if the 'arbitrary line' is parallel to the X axis. All that >needs to be checked in that case is the 'y' values of the endpoints. > >If you feel that I am wrong here, please send me an actual counter-example. ^ / \ / \ ray <-----------------/* \ / \ <_________> Does the point lie inside or outside of the triangle? If it is very close to the edge of the triangle and if the angle of the edge is appropriate, the precision of computation needed to get the right answer can be surprisingly high. Harry Plantinga planting@colby.wisc.edu
amamaral@elrond.CalComp.COM (Alan Amaral) (07/02/87)
In article <3772@spool.WISC.EDU>, planting@colby.WISC.EDU ( W. Harry Plantinga) writes: > In article <402@pembina.UUCP> obed!stephen@alberta.UUCP (Stephen > Samuel) writes: > > >If you feel that I am wrong here, please send me an actual counter-example. > > ^ > / \ > / \ > ray <-----------------/* \ > / \ > <_________> > > Does the point lie inside or outside of the triangle? If it is very > close to the edge of the triangle and if the angle of the edge is > appropriate, the precision of computation needed to get the right > answer can be surprisingly high. ^^^^^ ^^^^^ Please define "RIGHT"... I'm sure this problem has been suitably solved a number of times with INTEGER math, no more, but then again I'm sure the applicable definitions of "RIGHT" differ... By the way, handwaving does not "an actual counter-example" make. Please be more specific, like supply real NUMBERS, not vague pictures. "Very close to the edge" and "appropriate angle" are hard to calculate... > Harry Plantinga &^@%$ postnews... -- uucp: ...decvax!elrond!amamaral I would rather be a phone: (603) 885-8075 fool than a king... us mail: Calcomp/Sanders DPD (PTP2-2D01) Hudson NH 03051-0908
webber@brandx.rutgers.edu (Webber) (07/03/87)
In article <1007@elrond.CalComp.COM>, amamaral@elrond.CalComp.COM (Alan Amaral) writes: > In article <3772@spool.WISC.EDU>, planting@colby.WISC.EDU ( W. Harry Plantinga) writes: > > Does the point lie inside or outside of the triangle? If it is very > > close to the edge of the triangle and if the angle of the edge is > > appropriate, the precision of computation needed to get the right > > answer can be surprisingly high. ^^^^^ > ^^^^^ > Please define "RIGHT"... I'm sure this problem has been suitably solved > a number of times with INTEGER math, no more, but then again I'm sure > the applicable definitions of "RIGHT" differ... RIGHT is always relative to the application. If you are attempting realistic modelling, then anything that results in a percievably different image from the intended, is WRONG. If you are doing some kind of geometric application, anything that violates the geometric properties you are assuming can mean WRONGness, e.g., you expect the answer from the intersection between x and y to be the same as between y and x (even though arithmetic on computers does not always commute) -- also, if x is isomorphic to z, then the intersection of x with y and the intersection of z with y should lead to the same answer. Many systems have deep bugs because these properties are assumed by the programmer although the implementation does not support them. INTEGER math is not magic unless you are on a machine that supports arithmetic on integers of arbitrary size in a reasonable way (perhaps a Connection machine?). Otherwise you run into problems with precision -- try and set up the rotation matrices for integer arithmetic and see what happens as you try and show that when you rotate an image full circle it comes back to the same location. Of course, all of this is probably solvable. When you solve it, please post the code :-) >> By the way, handwaving does not "an actual counter-example" make. Please >> be more specific, like supply real NUMBERS, not vague pictures. "Very >> close to the edge" and "appropriate angle" are hard to calculate... Exact counter-examples are often machine and code dependant. I would certainly say that the principles involved are not so opaque that the only way to demonstrate that there is a problem is to run an actual simulation. If a simulation is needed, perhaps it would be easier for you to supply a piece of code and the set of intersection properties you are interested in simulating and then one can address the question of does this really happen. There is alot not known about the tradeoffs involved here. ----- BOB (webber@aramis.rutgers.edu ; rutgers!aramis.rutgers.edu!webber)
dmark@marvin (David M. Mark) (07/09/87)
A useful reference on the effects of "digital geometry" and digital number representation on Point-in-Polygon and similar problems is: Franklin, W.R., 1984, "Cartographic errors symptomatic of underlying algebra problems." Proceedings, International Symposium on Spatial Data Handling, Zurich, Switzerland, vol. 1, pp. 190-208. Randolph Franklin is at Rensselaaer Polytechnic Institute, and is reachable via csnet/ARPAnet, but I do not have his username and node name. David M. Mark, Department of Geography, SUNY@Buffalo dmark@buffalo.csnet geodmm@ubvms.BITNET