staff@cadlab.sublink.ORG (Alex Martelli) (01/04/91)
gjschmidt@crocus.uwaterloo.ca (Crazy 2B CS student) writes: ... >I need an algorithm that will take a predetermined series of (x,y) >coordinates defining an area (call it A), and another (x,y) coordinate >(call it P), and figure out whether or not P is contained within, or >lines on one of the edges of, A. Preparata and Shamos, COMPUTATIONAL GEOMETRY - An Introduction, Springer Verlag, 1985, ISBN 0-387-96131-3, great little introductory text. Use comp.graphics for discussions related to computational geometry. Sample C-like pseudocode for is-point-P-inside-polygon-{edge[i],i=1..N}: for(L=0,i=1;i<=N;i++) if( ! horizontal( edge[i] ) ) if( a horizontal semiline to the left of P insersects edge[i] at any point except the lower vertex ) L++ ; at the end of the loop, point P is inside the polygon defined by the set of edges if and only if L is odd. The test for horizontal edges is of course simply that the Y coords of the edge's two vertices be different; that for line-intersection is that Yedge[lower] < Ypoint <= Yedge[upper], and that the intersection be to the LEFT of P should be optimized to only actually do any *computation* if Xedge[leftmost] <= Xpoint <= Xedge[rightmost]. Many optimizations are available for common special-cases; check the book! Please note followup-to pointing to comp.graphics, if any further discussion is needed. -- Alex Martelli - CAD.LAB s.p.a., v. Stalingrado 53, Bologna, Italia Email: (work:) staff@cadlab.sublink.org, (home:) alex@am.sublink.org Phone: (work:) ++39 (51) 371099, (home:) ++39 (51) 250434; Fax: ++39 (51) 366964 (work only), Fidonet: 332/401.3 (home only).