Exercise 8.6

Posted in Uncategorized at 11:55 pm by admin

polygon :: [Coordinate] -> Region
polygon [] = Empty
polygon [x] = Empty
polygon (x:xs) = halfPlanes x (xs ++ [x])
    where halfPlanes x1 (x2:xs) = HalfPlane x1 x2 `Intersect` halfPlanes x2 xs
          halfPlanes xlast [] = Complement Empty


  1. Wieslaw Poszewiecki said,

    April 17, 2008 at 6:06 am

    I surrender. Correct text is at

    polygon ver = 
        foldl Intersect Empty [HalfPlane a b| (a,b)< -zip ver (tail ver++[head ver])] 

    or if you don't like Empty constructor

    polygon' ver = 
       let zipped = [HalfPlane a b| (a,b)< -zip ver (tail ver++[head ver])] 
       in foldl Intersect (head zipped) (tail zipped)

    [Edited by admin to add code from the above URL]

  2. admin said,

    April 17, 2008 at 9:31 pm

    I’ve removed your false starts and added the code. Try using <pre> tags around the code – that should preserve it.

  3. fero said,

    July 22, 2008 at 11:11 am

    Hi Wieslaw, I think this is no correct
    polygon ver =
    foldl Intersect Empty [HalfPlane a b| (a,b)<-zip ver (tail ver++[head ver])]

    it should be
    polygon ver =
    foldl Intersect (Complement Empty) [HalfPlane a b| (a,b)<-zip ver (tail ver++[head ver])]

    beacause “anything `Intersect` Empty” is “Empty”. You should Intersect it with all the space which is “Complement Empty”. I wrote the same solution with “Complement Empty” and it is working.

  4. Jon Gallagher said,

    January 7, 2009 at 2:36 pm

    No. There is no such thing as a polygon with one or two sides. There needs to be a check, on the length of the list of coordinates, and if less than 3 it should be Empty. Then proceed as folding the Intersection into these planes.

  5. Wiesław Poszewiecki said,

    December 14, 2010 at 2:44 am

    Fero,Jon you are both right. Thanks.
    Jon – assuming there is no polygon with less than 3 sides then the check should return error and not Empty.

  6. Ricky Liu said,

    March 5, 2014 at 4:28 am

    The solution given does not guard against the case of a 2-point list. The region will then become the extended infinite line created from the 2 points. I suggest to modify it as follows:

    polygon :: [Coordinate] -> Region
    polygon x
    | (length x) < 3 = error "polygon: requires at least 3 points"
    | otherwise = halfPlane (head x) (tail x ++ [head x])
    where halfPlane x1 (x2:xs) = HalfPlane x1 x2 `Intersect` halfPlane x2 xs
    halfPlane _ [] = Complement Empty

Leave a Comment