wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Computing Area of a Polygon
        
(Message started by: Barukh on Jul 4^th, 2008, 10:55am)

Title: Computing Area of a Polygon
Post by Barukh on Jul 4^th, 2008, 10:55am

Let a simple polygon P be given in the plane. Its vertices V₁, …, V_n have coordinates (x₁, y₁), …, (x_n, y_n) (any two adjacent vertices form a side of the polygon).

Prove that the area of the polygon can be computed by the following formula:

A = 1/2 | http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_{i = 1…n}(x_i+1y_i - x_iy_i+1) |,
where (x_n+1, y_n+1) = (x₁, y₁).

Title: Re: Computing Area of a Polygon
Post by towr on Jul 4^th, 2008, 1:19pm

[hide]You can sum all the areas of trapezoid formed by a linepiece and the x-axis, bearing in might the area can be negative depending on the order of the end points.

| Sum (y_i + y_i+1)/2 * (x_i+1 - x_i) |
1/2 | Sum y_ix_i+1 + y_i+1x_i+1 - y_ix_i - y_i+1x_i |
1/2 | Sum y_ix_i+1 - y_i+1x_i |
(Two terms drop out because they cancel each other when you go round all indices)[/hide]

Title: Re: Computing Area of a Polygon
Post by Grimbal on Jul 5^th, 2008, 2:13am

[hide]In fact,
1/2 (x_i+1y_i - x_iy_i+1)
is the oriented surface of the triangle
(0,0), (x_iy_i), (x_i+1y_i+1)
counted positive if the 3 points follow the clockwise direction, negative if not. Adding up all the triangles results in only the inside of the polygon being counted.[/hide]

Title: Re: Computing Area of a Polygon
Post by JohanC on Jul 5^th, 2008, 12:42pm

Nice.
Follow up question:
Extend this method to calculate the volume of a polyhedron in 3D ...

Title: Re: Computing Area of a Polygon
Post by towr on Jul 6^th, 2008, 7:07am

on 07/05/08 at 12:42:16, JohanC wrote:

Follow up question:
Extend this method to calculate the volume of a polyhedron in 3D ...

[hide]For each polygon find the distance between the plane it's in and the origin and calculate the oriented volume of the pyramid between the polygon and origin; then sum these.[/hide]
It's not really as neat as in the 2D case, because you can't get away with a single run around the vertices.

Title: Re: Computing Area of a Polygon
Post by Grimbal on Jul 6^th, 2008, 11:46am

[hide]Actually,
1/2 (x_i+1y_i - x_iy_i+1)
is
1/2! det( v_i v_j )
where the v_i and v_j define the edges of the polygon. (modulo a sign).
Extending to 3D gives
1/3! det( v_i v_j v_k )
where the v_i, v_j, v_k define the triangular faces of the polyhedron (taken all in the same orientation, anticlockwise as seen from the outside).
It's even neater than the 2D case. ::)[/hide]

Title: Re: Computing Area of a Polygon
Post by towr on Jul 6^th, 2008, 12:29pm

Except that faces of a polyhedron needn't be triangles.
And you still have the problem of how to run over the indices.

Title: Re: Computing Area of a Polygon
Post by Grimbal on Jul 6^th, 2008, 12:42pm

Well, if they aren't triangular, just cut them into triangles.
And indeed, figuring out over which triplets of vertices to run the sum is more complicated. I just wanted to echo your comment. It is what I do with the triplets that is a simpler expression than the expression we had for the 2D case.

Title: Re: Computing Area of a Polygon
Post by towr on Jul 6^th, 2008, 1:07pm

on 07/06/08 at 12:42:22, Grimbal wrote:

Well, if they aren't triangular, just cut them into triangles.

That gives us even more work to do :P

Quote:

It is what I do with the triplets that is a simpler expression than the expression we had for the 2D case.

Well, ok, that was kind of neat. And I suppose it goes for higher dimensions too?

Title: Re: Computing Area of a Polygon
Post by Grimbal on Jul 6^th, 2008, 1:12pm

I guess so, but it's a bit difficult to visualize. Especially, what is "clockwise" in 4D?