{-
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”
[…] Exercises 2.4 and 5.1. […]
-- | 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)
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
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.
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 verticesThe 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))(Although all the > and < signs got garbled; hopefully it will still make sense!)
(Oops – the > and < signs got garbled 🙁 )