The Shoelace Algorithm

The shoelace formula or shoelace algorithm is a mathematical algorithm to determine the area of a simple polygon whose vertices are described by their Cartesian coordinates in the plane.

The method consists of cross-multiplying corresponding coordinates of the different vertices of a polygon to find its area. It is called the shoelace formula because of the constant cross-multiplying for the coordinates making up the polygon, like tying shoelaces. (See table below). This algorithm has applications in 2D and 3D computer graphics graphics, in surveying or in forestry, among other areas.

To apply the shoelace algorithm you will need to:

• List all the vertices in anticlockwise order. (e.g. A,B,C,D,E) in a table, and note the x and y coordinates in two separate columns of the table,
• Calculate the sum of multiplying each x coordinate with the y coordinate in the row below (wrapping around back to the first line when you reach the bottom of the table),
• Calculate the sum of multiplying each y coordinate with the x coordinate in the row below (wrapping around back to the first line when you reach the bottom of the table),
• Subtract the second sum from the first, get the absolute value (Absolute dfference |sum₁-sum₂|,
• Divide the resulting value by 2 to get the actual area of the polygon.

The Shoelace Algorithm using Python:

To implement the shoelace algorithm we will define a polygon as a list of vertices, listed in anticlockwise order. Each vertex will be a list of 2 values: its x and y coordinates.

Alternative Approach

The above algorithm requires the computer to calculate two different sums that could potentially lead to very high numbers. On occasion these numbers could generate an overflow error if they reach the maximum capacity of an integer value.

The Shoelace formula can be rewritten as follows:

In this case the python code given above can be adapted to reflect this new formula and reduce the risk of creating an overflow error.

Your task is to tweak the above code to base the code on this alternative Shoelace formula.