Crazy polygon

Computer Science Level 3

A polygon $P$ with $n$ sides can be represented by a tuple $P = (P_0, P_1, \dots, P_{n-1})$ that contains the vertices $P_i = (x_i, y_i) \in \mathbb{R}^2$ of the polygon as elements. Successive points in the tuple are connected by an edge. In addition, last point $P_ {n-1}$ is connected to the first point $P_0$ .

How large is the area of the polygon shown on the right?

This simple polygon is represented by the following tuple of vertices:

1
2
3

polygon = ((0,0),(1.5,1),(2,-0.5),(2,1.5),(0.5,2),(2.5,2.5),
           (3,-2),(3.5,-1),(3,0),(3.5,0.5),(4,-0.5),(3.5,2),
           (3,1),(3.5,3),(3,4),(1,2.5),(0,3.5),(-1,3),(0,2))

The answer is 9.625.

1 solution

Markus Michelmann
May 22, 2018

Relevant wiki: Irregular Polygons

The area of a polygon with vertices $(x_i,y_i)$ , $i = 1, \dots, n-1$ is given by the formula $A = \sum_{i = 0}^{n-1} A_i = \frac{1}{2} \sum_{i=0}^{n-1} (x_{i-1} \cdot y_i - x_i \cdot y_{j-1})$ where $(x_{-1},y_{-1}) = (x_{n-1},y_{n-1})$ . Each summand of this equation corresponds to the area of a single triangle, which is formed by the points $P_{i-1}$ , $P_i$ and the origin $O = (0,0)$ . This triangular area is calculated with the determinant $A_i = \frac{1}{2} \left| \begin{array}{cc} x_{i-1} & y_{i-1} \\ x_i & y_i \end{array} \right| = \frac{1}{2} (x_{i-1} \cdot y_i - x_i \cdot y_{j-1})$ Note, that some of summands $A_i$ are negative and corrospond to an area outside of the polygon, that has to be subtracted.

The following python program calculates the area for the given polygon:

polygon = ((0,0),(1.5,1),(2,-0.5),(2,1.5),(0.5,2),(2.5,2.5),
           (3,-2),(3.5,-1),(3,0),(3.5,0.5),(4,-0.5),(3.5,2),
           (3,1),(3.5,3),(3,4),(1,2.5),(0,3.5),(-1,3),(0,2))

def area(p):
    result = 0
    A = p[-1]
    for B in p:
        result = result + 0.5*(A[0]*B[1] - B[0]*A[1])
        A = B
    return result

print(area(polygon))

How do you derive the formula for the area of a polygon with given vertices?

Tom Finet - 2 years, 12 months ago

It is easier to illustrate this formula in a single triangle. Draw a single triangle with the points $A = (a_x, a_y)$ , $B = (b_x, b_y)$ and $C = (c_x, c_y)$ . The triangular area can be represented as the enclosed area of two functions $f (x)$ and $g (x)$ . Let's assume that the function $g (x)$ is the line $AB$ and the function $f (x)$ is composed of the lines $AC$ and $CB$ . The triangle area then results as the integral $I = \int (f (x) - g (x)) dx$ . The integrals can be easily calculated since only trapezoidal shapes need to be considered $\begin{aligned} I &= \int f (x) dx - \int g (x) dx \\ &= \frac{1}{2} (a_y + c_y) (c_x - a_x) + \frac{1}{2} (c_y + b_y) (b_x - c_x) - \frac{1}{2} (a_y + b_y) (b_x - a_x) \\ &= \frac{1}{2} ((c_x a_y - c_y a_x) + (b_x c_y - b_y c_x) + (a_x b_y - a_y b_x) ) \end{aligned}$ That's already the formula for the polygon for the case n = 3. For the general case, we just have to show two things:

The formula applies, no matter how the triangle is oriented in the xy plane.
The formula also holds if we combine two triangles (polygons) into one larger polygon.

If you can understand German, this video might be helpful. Just jump to the minute 44 in the video.

Markus Michelmann - 2 years, 12 months ago

Crazy polygon

The answer is 9.625.

1 solution

0 pending reports