given a polygon P, i want to calculate the area of the polygon.

my solution: find a triangulation, and sum all the area of the triangles.

Total time complexity: o(nlogn).

Does there exist a better solution?

CodePudding user response：

You don't need to explicitly decompose, use the shoelace formula. It is easy and O(n).

https://en.wikipedia.org/wiki/Shoelace_formula

The method generalizes to the computation of geometric moments

https://en.wikipedia.org/wiki/Second_moment_of_area#Any_polygon