SOE ex.2.5
{- version #1 -}
area1 :: Shape -> Float
area1 (Polygon []) = 0
area1 (Polygon vss@(v1:_)) = polyArea (vss ++ [v1])
where
polyArea :: [Vertex] -> Float
polyArea ((x1, y1) : vs@((x2, y2) : _)) = (y1 + y2) * (x2 - x1) / 2 + polyArea(vs)
polyArea _ = 0
{- version #2 -}
area2 :: Shape -> Float
area2 (Polygon vs) = abs $ sum $ map trapezoidArea (zip vs (tail (cycle vs)))
where trapezoidArea ((x1, y1), (x2, y2)) = 0.5 * (y2 + y1) * (x2 - x1)
{-
Some test results:
area1 $ Polygon [(0,0), (1,0), (1,1)] = -0.5
area1 $ Polygon [(0,0), (1,1), (1,0)] = 0.5
area2 $ Polygon [(0,0), (1,0), (1,1)] = 0.5
area2 $ Polygon [] = 0.0
area2 $ Polygon [(0,0)] = 0.0
area2 $ Polygon [(0,0), (1,1)] = 0.0
-}
Polygon of vertices: (x1,y1), (x2,y2), …, (xn-1, yn-1), (xn, yn)
will have area equals to: (see book’s figure 2.3: polygon area equals sum of trapezoids’ area)
0.5 * (y2+y1) * (x2-x1) +
0.5 * (y3+y2) * (x3-x2) +
…
0.5 * (yn+yn-1) * (xn-xn-1) +
0.5 * (y1+yn) * (x1-xn)
Question #1: Do we need to translate polygon to first quadrant?
Answer: No.
Prove:
Let x’ = x + a and y’ = y + b to translate polygon to first quadrant.
Apply the algorithm, we get:
0.5 * (y2+b+y1+b) * (x2+a-x1-a) +
0.5 * (y3+b+y2+b) * (x3+a-x2-a) +
…
0.5 * (yn+b+yn-1+b) * (xn+a-xn-1-a) +
0.5 * (y1+b+yn+b) * (x1+a-xn-a)
=
0.5 * (y2+y1) * (x2-x1) + b * (x2-x1) +
0.5 * (y3+y2) * (x3-x2) + b * (x3-x2) +
…
0.5 * (yn+yn-1) * (xn-xn-1) + b * (xn-xn-1) +
0.5 * (y1+yn) * (x1-xn) + b * (x1-xn) +
Those “extra values” b * (xn-xn-1) will sum up equals to zero!
so
=
0.5 * (y2+y1) * (x2-x1) +
0.5 * (y3+y2) * (x3-x2) +
…
0.5 * (yn+yn-1) * (xn-xn-1) +
0.5 * (y1+yn) * (x1-xn)
Which is the same value without translate.
Question #2: The book said “Starting at any vertex and working clockwise…”
What happen if we work anti-clockwise?
Answer: we will get area value in negative form.
Prove:
Let’s assume (x1, y1), (x2, y2), …, (xn, yn) is clockwise order.
Now, apply algorithm to anti-clockwise order (x1, y1), (xn, yn), (xn-1, yn-1), …, (x3, y3), (x2, y2)
=
0.5 * (yn+y1) * (xn-x1) +
0.5 * (yn-1+yn) * (xn-1-xn) +
…
0.5 * (y2+y3) * (x2-x3) +
0.5 * (y1+y2) * (x1-x2)
=
-1 * 0.5 * (y2+y1) * (x2-x1) +
-1 * 0.5 * (y3+y2) * (x3-x2) +
…
-1 * 0.5 * (yn+yn-1) * (xn-xn-1) +
-1 * 0.5 * (y1+yn) * (x1-xn)
=
-1 * (
0.5 * (y2+y1) * (x2-x1) +
0.5 * (y3+y2) * (x3-x2) +
…
0.5 * (yn+yn-1) * (xn-xn-1) +
0.5 * (y1+yn) * (x1-xn)
)
So, reverse order, we get negative of origin value.
So, I added “abs” function call for my solution#2 to ignore the order.
Question #3: (Book’s question) This algorithm is also more efficient than our previous algorithm. (Why?)
Answer: Because less calculations. Previous algorithm called four times “sqrt” function for each triangle area.
Question #4: (Book’s question) Do any of the algorithms discussed here compute self-crossing polygon area properly?
Answer: No.
bowtie = Polygon [(0,0), (0,4), (4,0), (4,4)] — area = 4*4/2 = 8
area bowtie = 16.0 — algorithm with sum of triangles’ area
area2 bowtie = 0.0 — algorithm with sum of trapezoids’ area
(Maybe come back later to study/fix this issue)