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.

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