CS 8, Winter 2009

Short Assignment 2: Alternate area Function for a Polygon

This short assignment asks you to write a version of the area function for a Polygon that works correctly for non-convex polygons.

Instructions

You should print out your solutions to this assignment, and either turn them in at lecture, or leave them in the TA's mailbox at Sudikoff by class time on Mon. Jan. 12, 2009.

Please also e-mail an electronic version of your code to cs8hw@cs.dartmouth.edu, with the subject "CS 8 Short Assignment 2". Please attach your code as one or more enclosures to the message, and do not include it directly in the body of the e-mail message.

You must work alone on this short assignment.

Finding the Minimum of a list
Write a function findMin that takes a non-empty list of Floats and returns their minimum. Solve this using a higher-order function rather than recursion. You may use the built-in function min that takes the minimum of its two arguments, but should not use the built-in function minimum. (I am in effect asking you to implement this built-in function.)
Computing the area of a non-convex polygon
Exercise 2.5 on p. 33 gives a way to compute the area of a clockwise-oriented polygon that lies in the first quadrant. It sums signed areas of trapezoids whose top is an edge of the polygon and whose bottom is the x-axis. However, it will work for any clockwise-oriented polygon if instead of using the x-axis as the bottom you use a horizontal line through a vertex with minimum y-coordinate.

Modify the Shape module to use this approach to compute the area of a polygon which can be oriented either clockwise or counterclockwise, but where edges do not cross. A file Shape.hs which has only the code needed for the Shape class is available here.
Hint: The area of a trapezoid with vertical sides and a horizontal bottom is the average of the lengths of the sides times the length of the bottom.

Useful Haskell fact: given a 2-tuple, fst returns the first coordinate and snd returns the second. Thus
```
fst (1,2) => 1
snd (1,2) => 2
```
Demonstrate your area function on the following polygons, as well as some you develop yourself.
```
Polygon []
Polygon [(1.0,1.0)]
Polygon [(1.0,1.0), (2.0,2.0)]
Polygon [(0.0, 0.0), (0.0, 1.0), (1.0, 1.0)]
Polygon [(0.0, 0.0), (1.0, 1.0), (0.0, 2.0), (2.0, 2.0), (1.0, 1.0), (2.0, 0.0)]
```
Extra Credit: Does this algorithm work for self-crossing polygons? Argue that it does or give an example that shows it fails.

Department of Computer Science, Dartmouth College, Hanover, New Hampshire, USA

Last modified: 27-December-2008