The simplest way to allow vertices in clockwise or anticlockwise order is to define `isRightOf` analogously to `isLeftOf`, and combine them with a boolean expression.

isLeftOf :: Coordinate -> Ray -> Bool
(px,py) `isLeftOf` ((ax,ay), (bx,by))
= let (s,t) = (px-ax, py-ay)
(u,v) = (px-bx, py-by)
in s * v >= t * u
isRightOf :: Coordinate -> Ray -> Bool
(px,py) `isRightOf` ((ax,ay), (bx,by))
= let (s,t) = (px-ax, py-ay)
(u,v) = (px-bx, py-by)
in s * v <= t * u
(Polygon pts) `containsS` p
= let leftOfList = map isLeftOfp (zip pts (tail pts ++ [head pts]))
isLeftOfp p' = isLeftOf p p'
rightOfList = map isRightOfp (zip pts (tail pts ++ [head pts]))
isRightOfp p' = isRightOf p p'
in and leftOfList || and rightOfList |

isLeftOf :: Coordinate -> Ray -> Bool
(px,py) `isLeftOf` ((ax,ay), (bx,by))
= let (s,t) = (px-ax, py-ay)
(u,v) = (px-bx, py-by)
in s * v >= t * u
isRightOf :: Coordinate -> Ray -> Bool
(px,py) `isRightOf` ((ax,ay), (bx,by))
= let (s,t) = (px-ax, py-ay)
(u,v) = (px-bx, py-by)
in s * v <= t * u
(Polygon pts) `containsS` p
= let leftOfList = map isLeftOfp (zip pts (tail pts ++ [head pts]))
isLeftOfp p' = isLeftOf p p'
rightOfList = map isRightOfp (zip pts (tail pts ++ [head pts]))
isRightOfp p' = isRightOf p p'
in and leftOfList || and rightOfList

This entry was posted on Sunday, July 29th, 2007 at 11:49 pm and is filed under Uncategorized. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

[…] our updated definition of `containsS` for polygons from Exercise 8.4. To prove the second fact is […]

[…] Exercise 8.4 for definitions of isLeftOf and […]

Seems this also works:

(Polygon pts) `containsS` p

= let leftOfList = map (isLeftOf p)

(zip pts (tail pts ++ [head pts]))

in and leftOfList || not (or leftOfList)

Can anyone advise me how to forbid this control

to eat leading left spaces?

>(Polygon pts) `containsS` p

> = let leftOfList = map (isLeftOf p) (zip pts (tail pts ++ [head pts]))

> in and leftOfList || not (or leftOfList)

Sorry,

I noticed that my previous solution does not work

if some points are on sides.

This one seems to work also for sides

>(px,py) `isLeftOf` ((ax,ay),(bx,by))

> = let (s,t) = (px-ax, py-ay)

> (u,v) = (px-bx, py-by)

> in s*v – t*u

>(Polygon pts) `containsS` p

> = let leftOfList = map (isLeftOf p) (zip pts (tail pts ++ [head pts]))

> in and (map (>=0) leftOfList) || and (map (<=0) leftOfList)

To preserve code formatting, use <pre> tags around it.

This is my solution and works even with [] because of and function:

(Polygon pts) `containsS` p = let leftOfList = map (isLeftOf p)

(zip pts (tail pts ++ [head pts]))

in and (map (==head leftOfList) leftOfList)

@fero, your solution is similar to the first one given by Wieslaw. As Wieslaw already said it did not work when p lies on one of the edges of the polygon.