Here's another way to skin the cat.
A Winding Number and Point-in-Polygon Algoritm
by David G. Alciatore and Rick Miranda
http://www.engr.colostate.edu/~dga/dga/papers/point_in_polygon.pdf This is again the winding number algorithm.
But instead of doing the onleft cross product
test, we translate the point of the polyline
to point p as origin of the coordinate system.
We then proceed to count how many times
the y coordinates cross the positive x axis.
One interesting note about the winding number
algorithm is that the sign of the wn also gives
you the direction the polyline is drawn. Negative
wn is ccw and vice-versa.
;; ;
;; inside_p by ymg ;
;; ;
;; A Winding umber and Point-in-Polygon Algoritm ;
;; by David G. Alciatore and Rick Miranda ;
;; http://www.engr.colostate.edu/~dga/dga/papers/point_in_polygon.pdf ;
;; ;
;; Here instead of onleft cross product test, we translate the polyline ;
;; to the point. We then count the crossing of the y coordinates above ;
;; zero. ;
;; ;
;; (Under Test) ;
;; ;
)
((< (* y1 y2
) 0) (if (> (+ x1
(* y1
(/ (- x2 x1
) (- y1 y2
)))) 0) ))
)
)
)
ymg
