tada@athena.mit.edu (Michael Zehr) (03/03/88)
In article <590@naucse.UUCP> rrr@naucse.UUCP (Bob Rose ) writes: >In article <3320@bloom-beacon.MIT.EDU>, tada@athena.mit.edu (Michael Zehr) writes: >> The method I use in some graphics programs requires a compare and an >> xor for each edge of the polygon, and 2 multiplies (total, not for each >> edge). >> michael j zehr > >Sounds interesting. Lets here about the algorithm, it does sound >rather specific though, like xor is not that common in (none bit mask) >graphic routines. > > -bob you got it... (in pseudo C:) edge[] is an array of edges an edge has two fields, end1 and end2, plus two precomputed values to speed up the actual check: slope and intercept slope = (end2.y - end1.y)/(end2.x - end1.x) intercept = end2.y - slope*end2.x an "end" has two fields, x and y (this isn't the same datastructure i'm using, so i'm paraphrasing for simplicity and readability) flag = FALSE; for(k=0;k<num_edges;k++) if ((x > edge[k].end1.x) ^ (x > edge[k].end2.x)) if(y < (temp = edge[k].intercept + edge[k].slope*x) flag ^= TRUE; else if (y==temp) /* point is on an edge so do whatever you want with it */; after it's checked each edge, flag == TRUE implies it's inside, flag == FALSE implies it's outside the polygon. the multiply only occurs when a vertical line extended from the point being tested intersects with the edge. it then computes the intersection point, and checks if the point is below the edge. if so, it counts as an intersection. the multiply is only executed when there is a possible intersection, which is zero, one or two times for a convex polygon. this works as-is for concave, but doesn't guarantee only two multiplies. depending on your compiler and specific machine, it may be marginally faster to keep track of the lowest and highest end of each edge, and put another if statement before the one that computes the actual intersection, but i haven't tried this to see then you'd have: if (y < edge[k].min_y) flag^= TRUE; else if (y <= edge[k].max_y) if (y < (temp= .... Also, if your polygon are usually short and fat then you'd want to change that to a horizontal line test instead of the current vertical line test. Also, if your polygons are guaranteed convex, you could count the number of times the x tested true, and after the second one you wouldn't have to look at any more edges. If there are special cases which aren't handled correctly, would someone please, please, PLEASE let me know. thanks. ------- michael j zehr "My opinions are my own ... as is my spelling."