# 07.25.07

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

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

August 3, 2007 at 10:38 pm

[…] Exercises 2.4 and 5.1. […]

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)

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

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.

Julian said,

April 4, 2010 at 2:07 am

Again inspired from Sams.

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

Julian said,

April 4, 2010 at 2:12 am

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

Julian said,

April 4, 2010 at 2:13 am

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