{"id":433,"date":"2025-03-18T18:13:00","date_gmt":"2025-03-18T18:13:00","guid":{"rendered":"https:\/\/permutationcity.co.uk\/bp\/?p=433"},"modified":"2025-03-18T19:41:19","modified_gmt":"2025-03-18T19:41:19","slug":"area-of-a-polygon","status":"publish","type":"post","link":"https:\/\/permutationcity.co.uk\/bp\/2025\/03\/18\/area-of-a-polygon\/","title":{"rendered":"Area of a polygon"},"content":{"rendered":"\n

I wasn’t planning on a follow up but here we go.\nYou’ve calculated the\nclosest distance between a point and a line<\/a> and\ncalculated the area of a triangle<\/a>\nbut now want more,\nthe area of a polygon!<\/p>\n\n\n\n

Winging it<\/h2>\n\n\n\n

Let’s try to remember our school geometry lessons.\nYou can divide any polygon up into triangles.\nSo do that, calculate the area of each and add it all together?\nThat’s going be easy for\nconvex polygons<\/a> but\nI’m not sure about\nconcave polygons<\/a>.\nFor the first any\ntriangle fan<\/a>\nor\ntriangle strip<\/a>\nis going to work but\nnot for the second.\nLots of nieve triangulations methods are going to go outside the bounds of the polygon.\nFortunately it looks like there’s hope with the\ntwo ears theorem<\/a>.\nThat’s not what this post is about so I’m just going to think about convex polygons for now.<\/p>\n\n\n\n

Remember we have:<\/p>\n\n\n\n

struct Point {\n    double x, y;\n};\n\nstruct Triangle {\n    std::array<Point, 3> points;\n};\n\nfloat AreaOf(Triangle triangle);<\/pre><\/div>\n\n\n\n
So could just do this:<\/p>\n\n\n\n
struct Polygon {\n    std::vector<Point> points;\n};\n\nfloat AreaOf(const Polygon& polygon) {\n    float total = 0;\n    const auto initial = polygon.points[0];\n    auto previous = polygon.points[1];\n    for (size_t i = 2; i < polygon.size(); i++) {\n        const auto current = polygon.points[i];\n        total += AreaOf(Triangle(initial, previous, current);\n        previous = current;\n    }\n    return total;\n}<\/pre><\/div>\n\n\n\n
I’m being lazy here and just assuming that the polygon has at least 3 points but\notherwise it’s sound.<\/p>\n\n\n\n
Area of a trapezium<\/h2>\n\n\n\n
We need to take a brief detour.\nA trapezium<\/a> or trapezoid\nis a four sided shape with two parallel sides.\nWe are interested in a right trapezium where one of the angled sides is at 90 degrees and\nthe other is unconstrained.<\/p>\n\n\n\n
\"\"<\/figure>\n\n\n\n
Think of it as a rectangle with a triangle on top.\nIt’s area is:<\/p>\n\n\n\n
\n
(area of rectangle) + (area of triangle)<\/p>\n<\/blockquote>\n\n\n\n
or:<\/p>\n\n\n\n
\n
(b * h) + ((a – b) * h \/ 2)<\/p>\n<\/blockquote>\n\n\n\n
or:<\/p>\n\n\n\n
\n
b * h + a * h \/ 2 – b * h \/ 2<\/p>\n<\/blockquote>\n\n\n\n
or:<\/p>\n\n\n\n
\n
(a + b) * h \/ 2<\/p>\n<\/blockquote>\n\n\n\n
Which matches the\ngeneral case<\/a>.<\/p>\n\n\n\n
Trapezium formula<\/h2>\n\n\n\n
We can calculate the area of a polygon based on the area of it’s triangles.\nCan we do better?\nIf you care about such things we already know each triangle area calculation takes\n6 additions \/ subtractions, 7 multiplications, 1 division, 1 square root and 1 branch.\nLet’s simplify and call it 16 operations per triangle.\nSo if our polygon has 5 points, i.e. is made of 3 triangles,\nthen we have 48 operations.<\/p>\n\n\n\n
\"\"<\/figure>\n\n\n\n
Instead we can instead take the polygon and use it to make trapeziums.\nTake two points at a time and project them down on to the x-axis.\nSometimes the next point takes us to the right and\nsometimes to the left.<\/p>\n\n\n\n
Rightward<\/th>Leftward<\/th><\/tr><\/thead>
\"\"<\/td>\"\"<\/td><\/tr>
\"\"<\/td>\"\"<\/td><\/tr>
\"\"<\/td><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
As h<\/code> for each trapezium comes from the x-difference between points sometimes this will be positive and\nsometimes negative.\nWe calculate the area of each trapezium, for example:<\/p>\n\n\n\n
\n
(y0 + y1) * (x1 – x0) \/ 2<\/p>\n<\/blockquote>\n\n\n\n
Then add them all up, respecting their positive and negative areas, and take the absolute value.\nAs many of these areas are outside the polygon it seems a bit like magic.\nFor this example you can think it through like this:<\/p>\n\n\n\n
\"\"<\/figure>\n\n\n\n
The first trapezium shown is an overestimate,\nthe next two are remove the right amount,\nthe next removes too much and\nthe final one corrects for this.<\/p>\n\n\n\n
In code we it’s just:<\/p>\n\n\n\n
float AreaOf(const Polygon& polygon) {\n    float total = 0;    \n    for (size_t i = 0; i < polygon.size(); i++) {\n        const auto current = polygon.points[i];\n        const auto next = polygon.points[(i + 1) % polygons.size()];\n        total += (current.y + next.y) * (next.y - current.y);\n    }\n    return std::abs(0.5 * total);\n}<\/pre><\/div>\n\n\n\n
We now have 2 additions \/ subtractions, 1 multiplication, 1 modulo per triangle plus\n1 multiplication and 1 branch at the end.\nLet’s simplify again and call it 4 operations per triangle plus 2 overall.\nSo if our polygon has 5 points, 3 triangles,\nthen it’s only 14 operations.\nNice.<\/p>\n\n\n\n
In the end<\/h2>\n\n\n\n
If I was writing a geometry library I would go away and\nwrite some tests to check all this.\nIs it producing the right results?\nIs it faster than the nieve method?\nMaybe I’d use the nieve method to unit test this one.\nIn this case I just thought it was an interesting follow on.<\/p>\n\n\n\n
Do keep in mind that there are a lot of clever ideas out there.\nIf it feels like something should be a solved problem spend some time looking for an existing solution.\nThanks to this video on\nsoft body procedural animation<\/a>\nfor providing this one.<\/p>\n","protected":false},"excerpt":{"rendered":"
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 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_import_markdown_pro_load_document_selector":0,"_import_markdown_pro_submit_text_textarea":"","footnotes":""},"categories":[1],"tags":[22,40],"class_list":["post-433","post","type-post","status-publish","format-standard","hentry","category-general","tag-algorithms","tag-geometry"],"_links":{"self":[{"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/posts\/433","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/comments?post=433"}],"version-history":[{"count":3,"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/posts\/433\/revisions"}],"predecessor-version":[{"id":438,"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/posts\/433\/revisions\/438"}],"wp:attachment":[{"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/media?parent=433"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/categories?post=433"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/permutationcity.co.uk\/bp\/wp-json\/wp\/v2\/tags?post=433"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}