This is a bit specific but that is the way with some algorithms, or formulas in this case.\nLet’s say you want to calculate the area of a triangle.\nI’m not sure why.\nIt could be something in a graphics shader for a fancy effect.<\/p>\n\n\n\n
It’s been a long time since high school geometry.\nI definitely remember that the area of a right angled triangle is That’s fine in a maths example when things are aligned to the axes but\nwe dealing arbitrary triangle.\nWe are likely to have three random points.\nWe can calculate the length of any side easily but\nabout the height relative to that?\nActually two points make a line and\nI already have the code to calculate the\ndistance between a point and a line<\/a>.\nI’ll assume we have:<\/p>\n\n\n\n With that the area is just:<\/p>\n\n\n\n That seems okay for now.\nThere might be some edge cases to worry about such as points overlapping or being in a line.\nIs this a good<\/em> algorithm?\nIf I assume that the function for the distance between a point and a line is a given then it’s simple.\nLooking through it there are 6 additions \/ subtractions, 7 multiplications, 1 division, 1 square root and 1 branch.<\/p>\n\n\n\n The inspiration for the post is\nHeron’s formula<\/a>.\nLet’s say we have a triangle with points P<\/strong>, Q<\/strong> and R<\/strong>.\nWe can call the side lengths PQ<\/strong>, QR<\/strong> and RP<\/strong>.\nAs if by magic:<\/p>\n\n\n\n Alternatively we can use the semiperimeter<\/em> which is maths speak for “half the perimeter”:<\/p>\n\n\n\n So it just takes the perimeter of the triangle and the length of each pair of sides minus the odd one out.\nMixes them all together with a bit of multiplication and a square root.\nIs this a good<\/em> algorithm?\nI have no idea why it works but it apparently does.\nIt takes 6 additions \/ subtractions, 4 multiplications and 1 square root.<\/p>\n\n\n\n I’ve got a sneaking suspicion that the additions and multiplications might not matter.\nThere are a number of\nmethods for calculating square roots<\/a>\nwith varying levels of complexity.\nBoth algorithms use a square root but\nHeron’s formula uses it as a last step.\nThat means it would be easy to skip if you can make do with the area squared.<\/p>\n\n\n\n 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<\/a>. 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.<\/p>\n\n\n\n First of all I looked at the actual areas being calculated:<\/p>\n\n\n\n I can’t be certain these are the correct areas but both methods are producing the same areas.<\/p>\n\n\n\nbase * height \/ 2<\/code>.\nThat makes sense as it’s half<\/em> of a rectangle.\nActually that formula works even if it\nisn’t a right angle triangle<\/a>.\nAny triangle will do as long as the base is the length of one side and\nthe height is measured relative to that side.<\/p>\n\n\n\nstruct Point {\n double x, y;\n};\n\nstruct Line {\n Point start, end;\n};\n\ndouble DistanceBetween(Point point, Point other);\ndouble DistanceBetween(Point point, Line line);<\/pre><\/div>\n\n\n\nstruct Triangle {\n std::array<Point, 3> points;\n};\n\nfloat AreaOf(Triangle triangle) {\n Line line(triangle.points[0], triangle.points[1]);\n Point point(triangle.points[2]);\n\n float base = DistanceBetween(line.start, line.end);\n float height = DistanceBetween(point, line);\n return 0.5 * base * height;\n}<\/pre><\/div>\n\n\n\nHeron’s formula<\/h2>\n\n\n\n
auto area = 0.25f * sqrt(\n ( PQ + QR + RP) *\n (-PQ + QR + RP) *\n ( PQ - QR + RP) *\n ( PQ + QR - RP)\n );<\/pre><\/div>\n\n\n\n
auto semiperimeter = 0.5f * (PQ + QR + RP);\n auto area = sqrt(\n semiperimeter *\n (semiperimeter - PQ) *\n (semiperimeter - QR) *\n (semiperimeter - RP)\n );<\/pre><\/div>\n\n\n\n
The real world<\/h2>\n\n\n\n
i:0 4.9413,4.9413\ni:1 9.20024,9.20024\ni:2 0.458383,0.458383\ni:3 1.51573,1.51573\n...\ni:97 5.81562,5.81562\ni:98 0.578402,0.578402\ni:99 19.0903,19.0903<\/pre><\/div>\n\n\n\n