# Exercise 2.4

```{-
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 responses to “Exercise 2.4”

1. […] Exercises 2.4 and 5.1. […]

2. sam says:

```-- | 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 says:

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 says:

``` 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 says:

Again inspired from Sams.

```crossProd :: Vertex -> Vertex -> Vertex -> 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] -> Bool
convexClockwise     :: [Float] -> Bool
convexAnticlockwise  = all (>= 0)
convexClockwise      = all (<= 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 (>= 0) directions || all (<= 0) directions
where
vxs                  = vs++[v1,v2]
directions           =
zipWith3 crossProd vxs (tail vxs) (tail (tail vxs))
```
6. Julian says:

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

7. Julian says:

(Oops – the > and < signs got garbled 🙁 )