ConvexPolygon

Problem:

TopCoder Problem Statement - ConvexPolygon

Single Round Match 166 Round 1 - Division II, Level Three

Overview:

Calculate the area of a convex polygon.

Java Source:

01: public class ConvexPolygon {
02: 
03:     public double findArea(int[] x, int[] y)  {
04: 
05:         double area = 0.0;
06: 
07:         /*
08:         * Sum the areas of the triangles {0,1,2}, {0,2,3}, ... {0,n-1,n}
09:         */
10:         for (int v = 2; v < x.length; v++)  {
11:             area += areaOfTriangle(x[0], y[0], x[v-1], y[v-1], x[v], y[v]);
12:         }
13: 
14:         return area;
15:     }
16: 
17:     /*
18:     * Given the coordinates of the three vertices, the area of a triangle is
19:     * given by:
20:     *
21:     * area = abs((X1(Y2-Y3) + X2(Y3 - Y1) + X3(Y1-Y2)) / 2)
22:     *
23:     */
24:     private double areaOfTriangle(int x1, int y1,
25:                                   int x2, int y2,
26:                                   int x3, int y3) {
27: 
28:         double term1 = x1 * (y2 - y3);
29:         double term2 = x2 * (y3 - y1);
30:         double term3 = x3 * (y1 - y2);
31: 
32:         double result = (term1 + term2 + term3) / 2.0;
33: 
34:         return Math.abs(result);
35: 
36:     }
37: 
38: }

Notes:

The simple formula for the area of a triangle (A = (b * h) / 2) won't help us much. Instead we use a formula like the one given here

The area of the polygon can be calculated by dividing it up into triangles. For a polygon with n points, the area is the sum of the triangles formed by the points {0,1,2} + {0,2,3} + ... {0,n-1,n}. This becomes obvious is you draw any convex polygon on a piece of paper.

An alternate approach is to carve off a triangle (and calculate its area), and then recursively call findArea() to get the area of the remaining polygon.

Thank you for taking the time to read this solution. I welcome any feedback you may have.

All Solutions and descriptions are now available on GitHub at https://github.com/pmonkelban/TopCodingSolutions