mwm@eris.berkeley.edu (Mike (Don't have strength to leave) Meyer) (10/20/86)
In article <8900031@osiris> kaden@osiris.CSO.UIUC.EDU writes: > > Can we generalise to determine whether (p1,p2) is > inside a polygon? Use the VECTOR approach, ONLY, as > it is clearly the most superior, elegant and non- > paleozoic approach to the problem. I will not even > scan any other precambrian attempts. > > > Thankyou. I'm not sure what you mean by the "VECTOR" approach, but my solution to the triangle problem (which I MAILED to the asker) generalizes quite nicely to an arbitrary polygon. It's also generally faster than any of the solutions I've seen posted. The heart of the solution is a theorom which states that any ray from a point crosses a closed curve an odd number of times iff the point is inside the curve. To use this, we chose a computationally "nice" ray, the one in the positive X direction from the point. The heart of the algorithm is the routine crosses, below. /* * Just to make things easy */ typedef struct { float x, y ; } point ; /* * Crosses determines if a ray in the positve x direction from p crosses * the line from v1 to v2. Start by running lots of tests to avoid * interpolation. */ crosses(p, v1, v2) point p, v1, v2; { if (p . y <= v1 . y && p . y < v2 . y) /* to far in -y direction */ return 0 ; if (p . y >= v1 . y && p . y > v2 . y) /* to far in +y direction */ return 0 ; if (p . x >= v1 . x && p . x > v2 . x) /* to far in +x direction */ return 0 ; if (p . x <= v1 . x && p . x < v2 . x) /* Hit */ return 1 ; /* * We now have p in the box defined by [v1, v2). This means * that 1) the box isn't a line, so v1 . y != v2 . y; and * 2) we have to interpolate. To bad. */ if ((p . y - v1 . y) * (v1 . x - v2 . x) / (v1 . y - v2 . y) > 0) return 1 ; return 0 ; } Now, let's define an N-gon by an array of points v[1] through v[N] which are the vertices of the N-gon as you follow the boundary (clockwise, counterclockwise, who cares?). Define v[0] equal to v[N] to make my life easier. The the following code will test if p is inside of v. inside(p, v, n) point p, *v; unsigned n; { register unsigned i, crossings = 0; for (i = 0; i < n; i++) crossings += crosses(p, v[i], v[i + 1]) ; return crossings & 1 ; } which returns true if crossings is odd, indicating that p is inside of v. Just to let you exercise a little, I'll point out that there's a bug in the above code. There are lots of ways to fix it, and I still haven't decided on the best. I'd like to see other peoples fixes before posting anything. Oh, yeah - the triangle version of inside is particularly elegant, being: inside(p, v1, v2, v3) point p, v1, v2, v3; { return crosses(p, v1, v2) ^ crosses(p, v2, v3) ^ crosses(p, v3, v1) ; } Of course, by adding some assumptions about the n-gon (triangle), you can elimate the bug, and allow some nice speed improvements. <mike
kaden@osiris.CSO.UIUC.EDU (10/24/86)
# Gnyuck, gnyuck, gnyuck ... hey Moe! Eh, shaaaddaap! Count Vector on Sesame Street says: I love watching the ray crossing the curve and creating either an odd or even number of intersection points that I may count! Very splendid! Very splendid! HA! HA! HA! HA! HA! HA! HA! HA! HA! HA! HA! AH! HA! HA!
kevins@dartvax.UUCP (Kevin M. Schofield) (10/26/86)
In article <8900037@osiris> kaden@osiris.CSO.UIUC.EDU writes: > Count Vector on Sesame Street says: I love watching > the ray crossing the curve and creating either an > odd or even number of intersection points that I > may count! Very splendid! Very splendid! HA! HA! > HA! HA! HA! HA! HA! HA! HA! HA! HA! AH! HA! HA! Close, but not quite. You get a nasty exception to the rule when your ray hits a vertex of the polygon. -Kevin -- ------------------------------------------------------------------------------- "There may be no heaven, but somewhere there is a San Francisco." Kevin M. Schofield '88 email: {decvax,ihnp4} !dartvax!kevins kevins@dartmouth.EDU U.S. Mail: College: H.B. 2908, Dartmouth College, Hanover, NH 03755 Real World: 1851 Vallejo Street, St.Helena, CA 94574 --------------------------------------------------------------------------------
levy@ttrdc.UUCP (Daniel R. Levy) (10/31/86)
In article <5299@dartvax.UUCP>, kevins@dartvax.UUCP (Kevin M. Schofield) writes: >In article <8900037@osiris> kaden@osiris.CSO.UIUC.EDU writes: >> Count Vector on Sesame Street says: I love watching >> the ray crossing the curve and creating either an >> odd or even number of intersection points that I >> may count! Very splendid! Very splendid! HA! HA! >> HA! HA! HA! HA! HA! HA! HA! HA! HA! AH! HA! HA! > >Close, but not quite. You get a nasty exception to the rule when your >ray hits a vertex of the polygon. So what? Perturb the ray a little to get it off of the vertex and try again. (One thing about this kind of solution which seems a bit clumsy to me is that one needs to check every segment of the polygon to see if it does or does not intersect the ray.) -- ------------------------------- Disclaimer: The views contained herein are | dan levy | yvel nad | my own and are not at all those of my em- | an engihacker @ | ployer or the administrator of any computer | at&t computer systems division | upon which I may hack. | skokie, illinois | -------------------------------- Path: ..!{akgua,homxb,ihnp4,ltuxa,mvuxa, go for it! allegra,ulysses,vax135}!ttrdc!levy
pearce@calgary.UUCP (11/01/86)
In article <1284@ttrdc.UUCP>, levy@ttrdc.UUCP (Daniel R. Levy) writes: >>> Count Vector on Sesame Street says: I love watching >>> the ray crossing the curve and creating either an >>> odd or even number of intersection points that I >>> may count! Very splendid! Very splendid! HA! HA! >>> HA! HA! HA! HA! HA! HA! HA! HA! HA! AH! HA! HA! >> >>Close, but not quite. You get a nasty exception to the rule when your >>ray hits a vertex of the polygon. > >So what? Perturb the ray a little to get it off of the vertex and try again. > >(One thing about this kind of solution which seems a bit clumsy to me is >that one needs to check every segment of the polygon to see if it does or >does not intersect the ray.) I use this type of check to determine if a ray has struck the inside of a polygon - a vetex counts as .5 of an edge, and simple extent checks can eliminate the need to intersect *every* segement, most will just need min/max comparisions. This is, in general, much faster than performing a cross product with every edge, and this method works for concave polygons as well. (or has this already been brought up?) It does take more code to handle the many conditions though :-( Andrew Pearce [The Now Feeling] UUCP : pearce@calgary.UUCP USENET: ...{ihnp4,ubc-vision}!alberta!calgary!pearce
johnk@megaron.UUCP (11/03/86)
> In article <5299@dartvax.UUCP>, kevins@dartvax.UUCP (Kevin M. Schofield) writes: > >In article <8900037@osiris> kaden@osiris.CSO.UIUC.EDU writes: > >> Count Vector on Sesame Street says: I love watching > >> the ray crossing the curve and creating either an > >> odd or even number of intersection points that I > >> may count! Very splendid! Very splendid! HA! HA! > > > >Close, but not quite. You get a nasty exception to the rule when your > >ray hits a vertex of the polygon. > > So what? Perturb the ray a little to get it off of the vertex and try again. This method of counting intersections is based, I believe, on the Jordan Curve Theorem. It *doesn't* break down for a ray intersecting a vertex. Your intersection algorithm, upon encountering an intersecting vertex, must distinguish whether or not the slope of the contour changes sign at the vertex. If the sign indeed changes, count the intersection twice or not at all, depending on whether you think the glass is half full, or half empty; otherwise, count the intersection once. This points out the difficulties (which are rarely appreciated) in actually implementing an algorithm from computational geometry. Often the algorithm does not address certain critical boundary cases, such as vertical lines, overlapping line segments, etc. The paper in which the algorithm is described often deals with all these cases at once with something like ``perturb the point set through a small rotation epsilon ....'' -- John Kececioglu / arizona!johnk "Chess, like love, like music, has the power to make men happy." -- S. Tarrasch