Author |
Topic: Polygon Area (Read 2641 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Polygon Area
« on: Mar 8th, 2003, 10:40pm » |
 Quote  Modify
|
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
|
| « Last Edit: Mar 9th, 2003, 2:10am by william wu » |
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Polygon Area
« Reply #1 on: Mar 9th, 2003, 7:52am » |
Quote Modify
|
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..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Polygon Area
« Reply #2 on: Mar 9th, 2003, 8:11am » |
Quote Modify
|
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).
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
wolfgang
Newbie
Posts: 12
|
|
Re: Polygon Area
« Reply #3 on: Mar 9th, 2003, 9:33am » |
Quote Modify
|
I doubt I've got the simple solution, but I can give you a simplistic one: 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.
|
|
IP Logged |
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Polygon Area
« Reply #4 on: Mar 9th, 2003, 11:06am » |
Quote Modify
|
(Hidden text):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.
|
|
IP Logged |
|
|
|
aero_guy
Senior Riddler
Gender:
Posts: 513
|
|
Re: Polygon Area
« Reply #5 on: Mar 9th, 2003, 12:51pm » |
Quote Modify
|
The method from SWF is what I came up with first (though I unnecessarily constrained the point to be inside the shape) 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 as area calculations are just integrals you simply integrate along the length of the perimeter. This gives:
.5*sum((xi+1-xi)*(yi+1+yi))
This would lead to numerical inaccuracies if the y values were particularly large though, so you can modify it to:
.5*sum((xi+1-xi)*(yi+1+yi-2*y1) )
This may be similar to what Wolfgang suggested, but as it stands, unless I misunderstand him I don't think that method would work.
|
| « Last Edit: Mar 9th, 2003, 12:52pm by aero_guy » |
IP Logged |
|
|
|
aero_guy
Senior Riddler
Gender:
Posts: 513
|
|
Re: Polygon Area
« Reply #6 on: Mar 9th, 2003, 1:01pm » |
Quote Modify
|
OK Wolfgang, I get it. Pretty cool. Only trick comes in determining concavity, which shouldn't actually be too bad.
|
|
IP Logged |
|
|
|
wolfgang
Newbie
Posts: 12
|
|
Re: Polygon Area
« Reply #7 on: Mar 9th, 2003, 3:52pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Polygon Area
« Reply #8 on: Mar 9th, 2003, 5:40pm » |
Quote Modify
|
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 (xiyi+1-yixi+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.
|
| « Last Edit: Mar 10th, 2003, 5:12pm by SWF » |
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Polygon Area
« Reply #9 on: Mar 10th, 2003, 6:26pm » |
Quote Modify
|
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.
|
| « Last Edit: Mar 10th, 2003, 6:27pm by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print