evp@lewey.AIT.COM (Ed Post) (06/18/87)
in article <1881@zeus.TEK.COM>, bobr@zeus.TEK.COM (Robert Reed) says: > > 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. This is getting more and more complex. There's a very simple solution to the "crossing a vertex" problem, and I'd thought that everyone knew about it. To recap: you have a point and a polygon. You want to know whether the point is inside the polygon according to the "line crossing parity" definition of "inside". The algorithm is as follows: I. Let P be the point to test; initialize inside to FALSE. II. for each line L in the polygon: a. let maxy be the larger of the two Y coordinates, and miny be the smaller. b. if maxy == miny: 1. if P.x is between the min and max X of L, the point is ON the polygon. Terminate algorithm. 2. otherwise, continue to next line. c. if P.y >= maxy or P.y < miny, continue to next line. d. Let Ix be the intersection of L and the line y = P.y . e. If Ix == P.y, the point is ON the polygon. Terminate algorithm. f. If Ix is less than P.y, inside = !inside. III. If inside is TRUE, the point is INSIDE the polygon, otherwise it is OUTSIDE. The newsgroup discussions center on the special case when the Y coordinate of P exactly equals the Y coordinate of a line. In fact, it must equal the endpoint of an even number of lines since each endpoint of a closed polygon is shared by two lines. Examples of this case are: / / ------------------------o----------.P (example 1) \ \ \ \ ------------------------o========o-------.P (example 2) | | -----------------------o-----------.P (example 3) / \ / \ \ / \ / -----------------------o-------------.P (example 4) The question: how to separate these cases into ones with even and odd crossing numbers? The answer: treat each line segment as half-open on the TOP. Define an intersection between a line and the ray to be valid only if it does not pass through the top point of the line. If the test in step II.c were written as: "P.y > maxy or P.y < miny", examples 1 and 2 would produce the wrong number of intersections with the horizontal ray. But since II.c treats each edge as half-open at the top, these two examples record an intersection only for the top line and not the bottom. II.c records zero intersections for example 3, and two intersections for example 4. If being exactly ON the polygon is not important to know, steps II.b and II.e may be eliminated. The only side effect of this deletion is to make points exactly on one side of the polygon INSIDE, and points on the opposite side OUTSIDE. -Ed -- Ed Post -- hplabs!lewey!evp (408)252-8713 American Information Technology; Cupertino, CA 95014