There are a couple of ways to do this (the basic problem being how to deal with concave polygons). One way is to convert the polygon to a convex hull and a list of triangles representing subtractions from the convex hull, then check containment within the hull and non-containment within the triangles. However, I present a simpler way: pick a point guaranteed not to be in the polygon, form the ray between that and the point in question, and count the number of times that ray crosses the polygon sides. If it’s even, the point is outside the polygon. This method also works for self-crossing polygons (provided that one considers any internal spaces formed as outside the polygon: consider a pentagram for example).<\/p>\n
raysCross :: Ray -> Ray -> Bool\r\nraysCross (a,b) (x,y) = let h = isLeftOf x (a,b) && isRightOf y (a,b)\r\n i = isLeftOf y (a,b) && isRightOf x (a,b)\r\n j = isLeftOf a (x,y) && isRightOf b (x,y)\r\n k = isLeftOf b (x,y) && isRightOf a (x,y)\r\n in (h || i) && (j || k)\r\n\r\ncountCrossings :: Ray -> [Ray] -> Int\r\ncountCrossings r rs = foldl (+) 0\r\n (map (\\x -> if raysCross r x then 1 else 0) rs)\r\n\r\nguaranteedOutside :: [Vertex] -> Vertex\r\nguaranteedOutside vs\r\n = (foldl maxop 0 xs + 1, foldl maxop 0 ys + 1)\r\n where (xs, ys) = unzip vs\r\n maxop a b = if a > b then a else b\r\n\r\ncontainsS' :: Shape -> Coordinate -> Bool\r\n(Polygon ps) `containsS'` p\r\n = let poutside = guaranteedOutside ps\r\n in (countCrossings (p,poutside)\r\n (zip ps (tail ps ++ [head ps]))) `mod` 2 == 1<\/pre>\n