07.29.07

Exercise 8.4

Posted in Uncategorized at 11:49 pm by admin

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

9 Comments »

  1. The Haskell School of Expression: Exercises » Exercise 8.10 said,

    August 3, 2007 at 10:29 pm

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

  2. The Haskell School of Expression: Exercises » Exercise 8.12 said,

    August 5, 2007 at 9:30 pm

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

  3. Wieslaw Poszewiecki said,

    April 16, 2008 at 8:31 am

    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)

  4. Wieslaw Poszewiecki said,

    April 16, 2008 at 8:39 am

    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)

  5. Wieslaw Poszewiecki said,

    April 16, 2008 at 8:47 am

    Sorry,
    I noticed that my previous solution does not work
    if some points are on sides.

  6. Wieslaw Poszewiecki said,

    April 16, 2008 at 9:03 am

    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)

  7. admin said,

    April 17, 2008 at 9:38 pm

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

  8. fero said,

    July 22, 2008 at 10:15 am

    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)

  9. Ricky Liu said,

    March 4, 2014 at 7:15 am

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

Leave a Comment