Area of a polygon

I wasn’t planning on a follow up but here we go. You’ve calculated the closest distance between a point and a line and calculated the area of a triangle but now want more, the area of a polygon!

Winging it

Let’s try to remember our school geometry lessons. You can divide any polygon up into triangles. So do that, calculate the area of each and add it all together? That’s going be easy for convex polygons but I’m not sure about concave polygons. For the first any triangle fan or triangle strip is going to work but not for the second. Lots of nieve triangulations methods are going to go outside the bounds of the polygon. Fortunately it looks like there’s hope with the two ears theorem. That’s not what this post is about so I’m just going to think about convex polygons for now.

Remember we have:

struct Point {
    double x, y;
};

struct Triangle {
    std::array<Point, 3> points;
};

float AreaOf(Triangle triangle);

So could just do this:

struct Polygon {
    std::vector<Point> points;
};

float AreaOf(const Polygon& polygon) {
    float total = 0;
    const auto initial = polygon.points[0];
    auto previous = polygon.points[1];
    for (size_t i = 2; i < polygon.size(); i++) {
        const auto current = polygon.points[i];
        total += AreaOf(Triangle(initial, previous, current);
        previous = current;
    }
    return total;
}

I’m being lazy here and just assuming that the polygon has at least 3 points but otherwise it’s sound.

Area of a trapezium

We need to take a brief detour. A trapezium or trapezoid is a four sided shape with two parallel sides. We are interested in a right trapezium where one of the angled sides is at 90 degrees and the other is unconstrained.

Think of it as a rectangle with a triangle on top. It’s area is:

(area of rectangle) + (area of triangle)

or:

(b * h) + ((a – b) * h / 2)

or:

b * h + a * h / 2 – b * h / 2

or:

(a + b) * h / 2

Which matches the general case.

Trapezium formula

We can calculate the area of a polygon based on the area of it’s triangles. Can we do better? If you care about such things we already know each triangle area calculation takes 6 additions / subtractions, 7 multiplications, 1 division, 1 square root and 1 branch. Let’s simplify and call it 16 operations per triangle. So if our polygon has 5 points, i.e. is made of 3 triangles, then we have 48 operations.

Instead we can instead take the polygon and use it to make trapeziums. Take two points at a time and project them down on to the x-axis. Sometimes the next point takes us to the right and sometimes to the left.

Rightward	Leftward

As h for each trapezium comes from the x-difference between points sometimes this will be positive and sometimes negative. We calculate the area of each trapezium, for example:

(y0 + y1) * (x1 – x0) / 2

Then add them all up, respecting their positive and negative areas, and take the absolute value. As many of these areas are outside the polygon it seems a bit like magic. For this example you can think it through like this:

The first trapezium shown is an overestimate, the next two are remove the right amount, the next removes too much and the final one corrects for this.

In code we it’s just:

float AreaOf(const Polygon& polygon) {
    float total = 0;    
    for (size_t i = 0; i < polygon.size(); i++) {
        const auto current = polygon.points[i];
        const auto next = polygon.points[(i + 1) % polygons.size()];
        total += (current.y + next.y) * (next.y - current.y);
    }
    return std::abs(0.5 * total);
}

We now have 2 additions / subtractions, 1 multiplication, 1 modulo per triangle plus 1 multiplication and 1 branch at the end. Let’s simplify again and call it 4 operations per triangle plus 2 overall. So if our polygon has 5 points, 3 triangles, then it’s only 14 operations. Nice.

In the end

If I was writing a geometry library I would go away and write some tests to check all this. Is it producing the right results? Is it faster than the nieve method? Maybe I’d use the nieve method to unit test this one. In this case I just thought it was an interesting follow on.

Do keep in mind that there are a lot of clever ideas out there. If it feels like something should be a solved problem spend some time looking for an existing solution. Thanks to this video on soft body procedural animation for providing this one.