wu :: forums - Print Page


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

        riddles >> hard >> Polygon Area
        
(Message started by: william wu on Mar 8^th, 2003, 10:40pm)

Title: Polygon Area
Post by william wu on Mar 8^th, 2003, 10:40pm

Given a bunch of (x,y) coordinates that form the vertices of one non-self-intersecting polygon, how would you go about finding the area of that polygon? What is the most clever / elegant solution you can devise? The desired answer is remarkably simple.

Note: Notice I did not say the polygon has to be regular or convex. A regular polygon has all sides of equal length. A convex polygon is a polygon such that all line segments formed between any two vertices must lie inside the polygon boundaries.

Contributor: Yosen Lin

Title: Re: Polygon Area
Post by towr on Mar 9^th, 2003, 7:52am

unless I missunderstand the question I would have to say that there may not be one definite answer..
Unless you know which vertices are connected to each other..

Title: Re: Polygon Area
Post by william wu on Mar 9^th, 2003, 8:11am

Sorry, I forgot that part. You are given the connections also. This can be easily done by giving the vertices in an order such that consecutive coordinate pairs are connected (thereby tracing the perimeter of the polygon).

Title: Re: Polygon Area
Post by wolfgang on Mar 9^th, 2003, 9:33am

I doubt I've got the simple solution, but I can give you a simplistic one: [hide]Start at any point, figure the area of the triangle formed by it and the 2 points it is adjacent to, and whether the area is positive or negative, concave or convex. Eliminate that point from the drawing and pick another point. Keep going until you have just 3 points left. Add all the areas together.[/hide]

Title: Re: Polygon Area
Post by SWF on Mar 9^th, 2003, 11:06am

(Hidden text):[hide]Pick an aribrary point X in the plane of the polygon. For each pair of consecutive points on the perimeter sum the out of plane components of the cross product A x B. A and B are vectors originating at point X. Vector A ends at the first point in a pair, and B ends at the second point in the pair. The area is one half the absolute value of that sum.[/hide]

Title: Re: Polygon Area
Post by aero_guy on Mar 9^th, 2003, 12:51pm

The method from SWF is what I came up with first (though I [hide]unnecessarily constrained the point to be inside the shape[/hide]) as it is actually very similar to the equations I use to calculate induced velocity due to a vortex element (aerospace stuff).

I am not sure which would be called easier, but [hide]as area calculations are just integrals you simply integrate along the length of the perimeter. This gives:
.5*sum((x_i+1-x_i)*(y_i+1+y_i))
This would lead to numerical inaccuracies if the y values were particularly large though, so you can modify it to:
.5*sum((x_i+1-x_i)*(y_i+1+y_i-2*y₁))[/hide]

This may be similar to what Wolfgang suggested, but as it stands, unless I misunderstand him I don't think that method would work.

Title: Re: Polygon Area
Post by aero_guy on Mar 9^th, 2003, 1:01pm

OK Wolfgang, I get it. Pretty cool. Only trick comes in determining concavity, which shouldn't actually be too bad.

Title: Re: Polygon Area
Post by wolfgang on Mar 9^th, 2003, 3:52pm

I may be in the minority on this board, but since I've never taken calculus or any advanced math, I'm pretty much limited to simplistic solutions.

Title: Re: Polygon Area
Post by SWF on Mar 9^th, 2003, 5:40pm

That point X that was suggested doesn't even need to be in the plane. If you choose X to be the origin, the equation becomes simple:

Take half the absolute value of sum of (x_iy_i+1-y_ix_i+1). Where i+1 means the next point, so the if i is the last point, i+1 refers back to the first point.

If you are familar with Stokes' Theorem, choose a vector function whose out of plane component of the curl is a non-zero constant. Then the line integral around the perimeter is proportional to the area. For example, the formula proposed by aero_guy is related to the vector function f=y*i, where i is the unit vector in the x direction.

Title: Re: Polygon Area
Post by Icarus on Mar 10^th, 2003, 6:26pm

There are mechanical devices for determining areas that are based on the formula Area = line integral (xdy), taken around the boundary. They were used by geographers and geologists to determine land areas from a map ("were" since I assume this is done by computer today). The device has a double-swinging arm with a view-finder at the end. The operator would take the view-finder along the outside contour of the region. The values of x and y were determined by the orientation of the two arm segments. As the operator moved the view-finder along the contour, a counter gave the value of the line integral, taken from the starting point to the current location. When the operator got all the way around the contour to the starting point again, the counter showed the map area. Multiplying by the scaling factor (squared) gave the land area.