07.25.07

Exercise 2.4

Posted in Uncategorized at 10:26 pm by admin

{-
Is a shape convex: compute the cross product of the two vectors
formed by each 3 vertices - a convex shape will have all the
cross products the same sign.
-}
 
crossProduct :: Vertex -> Vertex -> Vertex -> Float
crossProduct (x1, y1) (x2, y2) (x3, y3) = (x2 - x1) * (y3 - y2)
                                          - (y2 - y1) * (x3 - x2)
 
convex :: Shape -> Bool
convex (Rectangle a b) = True
convex (RtTriangle a b) = True
convex (Ellipse r1 r2) = True
convex (Polygon [ _ , _ , _ ]) = True
convex (Polygon (vfirst : vsecond : vthird : vs))
    = let sign = crossProduct vfirst vsecond vthird
      in polyConvex sign vsecond (vthird : vs)
          where polyConvex s v1 (v2 : v3 : vs')
                    = let newSign = crossProduct v1 v2 v3
                      in if newSign * s < 0
                         then False
                         else polyConvex s v2 (v3 : vs')
                polyConvex s vn (vlast : [])
                    = let newSign = crossProduct vn vlast vfirst
                      in if newSign * s < 0
                         then False
                         else polyConvex s vlast []
                polyConvex s vlast []
                    = let newSign = crossProduct vlast vfirst vsecond
                      in newSign * s > 0

This function is crying out for some higher order help! But it works, and it’s even straightforward, if inelegant in the end-of-list pattern matching.

7 Comments »

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

    August 3, 2007 at 10:38 pm

    […] Exercises 2.4 and 5.1. […]

  2. sam said,

    January 18, 2008 at 7:43 am

    -- | assume vs lists 'Vertex'es counter clockwise.
    -- and no two 'Vertex'es are equal.
    convex (Polygon vs) | length vs < 3 = False
    convex (Polygon (v:vs)) =
    let
    verts = (v:vs) ++ [v] -- ^ closed polygon
    xes = zipWith3 crossProduct verts (tail verts) (tail (tail verts))
    -- ^ cross products
    in
    and (zipWith (\a b -> signum a == signum b) xes (tail xes))

    crossProduct :: Vertex -> Vertex -> Vertex -> Float
    crossProduct (x1,y1) (x2,y2) (x3,y3) =
    ax * by - ay * bx
    where
    (ax, ay) = (x1 - x2, y1 - y2)
    (bx, by) = (x3 - x2, y3 - y2)

  3. fero said,

    July 16, 2008 at 7:20 am

    Hi, I am not sure if this works, cos I don’t have area for concave polygons. Idea is that 4-edges convex polygon should have bigger area than arbitrary triangle formed when we left one angle.

    convex (Polygon (v1:v2:v3:v4:vs)) = isEveryAngleConvex (v1:v2:v3:v4:vs++v1:v2:v3:[])
    where isEveryAngleConvex :: [Vertex] -> Bool;
    isEveryAngleConvex (v1:v2:v3:v4:vs) =
    if (area (Polygon (v1:v2:v3:[v4])) < area (Polygon (v1:v2:[v4]))) then False
    else isEveryAngleConvex (v2:v3:v4:vs)
    isEveryAngleConvex _ = True
    convex (Polygon _ ) = True

  4. benj said,

    August 7, 2009 at 7:29 am


    convex (Polygon vs) = and $ zipWith (==) xs (tail xs)
    where verts = vs ++ take 2 vs
    xs = zipWith3 isClockwise verts (tail verts) (tail . tail $ verts)

    isClockwise :: Vertex -> Vertex -> Vertex -> Bool
    isClockwise (v1x,v1y) (v2x,v2y) (v3x,v3y) = (x1*y2 - y1*x2) < 0
    where x1 = v2x - v1x
    y1 = v2y - v1y
    x2 = v2x - v3x
    y2 = v2y - v3y

    Inspired from sams.. but I think if you tail twice to capture all the vertices you need to add on the the first 2 vertices not just the first.

  5. Julian said,

    April 4, 2010 at 2:07 am

    Again inspired from Sams.

    crossProd :: Vertex -&gt; Vertex -&gt; Vertex -&gt; Float
    crossProd (x1,y1) (x2,y2) (x3,y3) = (x2-x1)*(y3-y1) - (x3-x1)*(y2-y1)
     
    convex (Polygon vs@(v1:v2:vs')) =
      convexAnticlockwise directions || convexClockwise directions
      where
        vxs                  = vs++[v1,v2]
        directions           =
          zipWith3 crossProd vxs (tail vxs) (tail (tail vxs))
        convexAnticlockwise :: [Float] -&gt; Bool
        convexClockwise     :: [Float] -&gt; Bool
        convexAnticlockwise  = all (&gt;= 0)
        convexClockwise      = all (&lt;= 0)
    convex (Polygon _)              = True  -- fewer than two vertices

    The last section can be shortened, at the possible cost of some readability, to

    convex (Polygon vs@(v1:v2:vs')) =
      all (&gt;= 0) directions || all (&lt;= 0) directions
      where
        vxs                  = vs++[v1,v2]
        directions           =
          zipWith3 crossProd vxs (tail vxs) (tail (tail vxs))
  6. Julian said,

    April 4, 2010 at 2:12 am

    (Although all the > and < signs got garbled; hopefully it will still make sense!)

  7. Julian said,

    April 4, 2010 at 2:13 am

    (Oops – the > and < signs got garbled šŸ™ )

Leave a Comment