CODEWITHSUNDEEP
algorithmcomputational-geometry
firev2
firev2

Reputation: 145

Calculating the area of a simple polygon

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?

Upvotes: 1

Views: 502

Answers (1)

user1196549
user1196549

Reputation:

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

Upvotes: 4

Related Questions