Area of a triangle

This is a bit specific but that is the way with some algorithms, or formulas in this case. Let’s say you want to calculate the area of a triangle. I’m not sure why. It could be something in a graphics shader for a fancy effect.

Winging it

It’s been a long time since high school geometry. I definitely remember that the area of a right angled triangle is base * height / 2. That makes sense as it’s half of a rectangle. Actually that formula works even if it isn’t a right angle triangle. Any triangle will do as long as the base is the length of one side and the height is measured relative to that side.

That’s fine in a maths example when things are aligned to the axes but we dealing arbitrary triangle. We are likely to have three random points. We can calculate the length of any side easily but about the height relative to that? Actually two points make a line and I already have the code to calculate the distance between a point and a line. I’ll assume we have:

struct Point {
    double x, y;
};

struct Line {
    Point start, end;
};

double DistanceBetween(Point point, Point other);
double DistanceBetween(Point point, Line line);

With that the area is just:

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

float AreaOf(Triangle triangle) {
    Line line(triangle.points[0], triangle.points[1]);
    Point point(triangle.points[2]);

    float base = DistanceBetween(line.start, line.end);
    float height = DistanceBetween(point, line);
    return 0.5 * base * height;
}

That seems okay for now. There might be some edge cases to worry about such as points overlapping or being in a line. Is this a good algorithm? If I assume that the function for the distance between a point and a line is a given then it’s simple. Looking through it there are 6 additions / subtractions, 7 multiplications, 1 division, 1 square root and 1 branch.

Heron’s formula

The inspiration for the post is Heron’s formula. Let’s say we have a triangle with points P, Q and R. We can call the side lengths PQ, QR and RP. As if by magic:

    auto area = 0.25f * sqrt(
            ( PQ + QR + RP) *
            (-PQ + QR + RP) *
            ( PQ - QR + RP) *
            ( PQ + QR - RP)
        );

Alternatively we can use the semiperimeter which is maths speak for “half the perimeter”:

    auto semiperimeter = 0.5f * (PQ + QR + RP);
    auto area = sqrt(
             semiperimeter *
            (semiperimeter - PQ) *
            (semiperimeter - QR) *
            (semiperimeter - RP)
        );

So it just takes the perimeter of the triangle and the length of each pair of sides minus the odd one out. Mixes them all together with a bit of multiplication and a square root. Is this a good algorithm? I have no idea why it works but it apparently does. It takes 6 additions / subtractions, 4 multiplications and 1 square root.

I’ve got a sneaking suspicion that the additions and multiplications might not matter. There are a number of methods for calculating square roots with varying levels of complexity. Both algorithms use a square root but Heron’s formula uses it as a last step. That means it would be easy to skip if you can make do with the area squared.

The real world

Guessing about performance can only go so far. In the end you have to do a real comparison and it’s not what I expected. The “off the top of my head” method is about twice as fast as this magic little formula. I tried to count up the instructions and it seemed as though Heron’s formula should come out ahead.

First of all I looked at the actual areas being calculated:

i:0     4.9413,4.9413
i:1     9.20024,9.20024
i:2     0.458383,0.458383
i:3     1.51573,1.51573
...
i:97    5.81562,5.81562
i:98    0.578402,0.578402
i:99    19.0903,19.0903

I can’t be certain these are the correct areas but both methods are producing the same areas.

Maybe the problem is that in Heron’s formula I assumed we already had the side lengths. That’s not true and each of those calculations involves 3 additions / subtractions, 2 multiplications and a square root. By pre-calculating the lengths should see a better comparison. So Heron’s formula is still slower but only just.

In the end

I heard about this clever little formula for calculating the area of a triangle. It looked as though that could save some computation. That doesn’t mean that its actually faster. Profiling is everything when measuring performance.

It may seem odd that one week I’ll tell you that performance tricks aren’t that important. The next week I’ll dive into detail about the performance of a particular algorithm. It just happens that I enjoy some of the details about algorithms. I could sit down for a few days or a week to optimise a bit of code to get it 10% faster. However I also think that in day to day programming that 10% won’t matter unless it’s the right piece of code that gets optimised.