# 08.05.07

## Exercise 8.12

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).

raysCross :: Ray -> Ray -> Bool raysCross (a,b) (x,y) = let h = isLeftOf x (a,b) && isRightOf y (a,b) i = isLeftOf y (a,b) && isRightOf x (a,b) j = isLeftOf a (x,y) && isRightOf b (x,y) k = isLeftOf b (x,y) && isRightOf a (x,y) in (h || i) && (j || k) countCrossings :: Ray -> [Ray] -> Int countCrossings r rs = foldl (+) 0 (map (\x -> if raysCross r x then 1 else 0) rs) guaranteedOutside :: [Vertex] -> Vertex guaranteedOutside vs = (foldl maxop 0 xs + 1, foldl maxop 0 ys + 1) where (xs, ys) = unzip vs maxop a b = if a > b then a else b containsS' :: Shape -> Coordinate -> Bool (Polygon ps) `containsS'` p = let poutside = guaranteedOutside ps in (countCrossings (p,poutside) (zip ps (tail ps ++ [head ps]))) `mod` 2 == 1 |

See Exercise 8.4 for definitions of `isLeftOf` and `isRightOf`. I am also left feeling that there must be a more elegant way to count the number of list elements that fulfil a predicate (which is what `countCrossings` is really doing).

fero said,

July 24, 2008 at 12:11 am

Yes, there is a more elegant way to count the number of list elements that fulfil a predicate. I used:

crossings = length (filter (raysCross ray) sides)

Julian said,

April 14, 2010 at 12:31 am

There’s a more elegant method than maxop, which is to use the Standard Prelude maximum function.

Unfortunately, however, the method shown does not work in this case:

gives a result of False, even though the point (0,0) clearly lies inside the square.

The reason is that the point outside that is chosen is (2,2), and the ray (0,0) to (2,2) passes through the vertex (1,1), and so lies on two edges.

This problem is therefore far subtler than it first appears.

One approach is to use the given idea but to take account of the fixed ray (from chosen point to outside point) passing through vertices, by having each one counting for 0.5. However, this will also fail if the ray just touches a vertex (if the shape is concave). A fix for this is to use signed crossings, taking account of the direction in which the rays cross. But this is getting fairly awkward and difficult.

I’m currently working on an alternative approach which uses winding numbers – we’ll see how it works out ….

Julian

Julian said,

April 14, 2010 at 4:04 am

Here goes ….

We include a little test program at the end.