wu :: forums « wu :: forums - Computing Area of a Polygon » Welcome, Guest. Please Login or Register. Nov 25th, 2024, 2:54am

RIDDLES SITE WRITE MATH! Home Help Search Members Login Register

wu :: forums    riddles    medium (Moderators: SMQ, Grimbal, towr, Eigenray, ThudnBlunder, Icarus, william wu)    Computing Area of a Polygon « Previous topic | Next topic » Pages: 1  Reply Notify of replies Send Topic Print    Author  Topic: Computing Area of a Polygon  (Read 1448 times) Barukh Uberpuzzler     Gender: Posts: 2276 Computing Area of a Polygon   « on: Jul 4th, 2008, 10:55am » Quote Modify Let a simple polygon P be given in the plane. Its vertices V1, …, Vn have coordinates (x1, y1), …, (xn, yn)  (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 | i = 1…n(xi+1yi - xiyi+1) |, where (xn+1, yn+1) = (x1, y1). « Last Edit: Jul 4th, 2008, 10:56am by Barukh » IP Logged towr wu::riddles Moderator Uberpuzzler Some people are average, some are just mean.     Gender: Posts: 13730 Re: Computing Area of a Polygon   « Reply #1 on: Jul 4th, 2008, 1:19pm » Quote Modify 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 (yi + yi+1)/2 * (xi+1 - xi) | 1/2 | Sum yixi+1 + yi+1xi+1 - yixi - yi+1xi | 1/2 | Sum yixi+1 - yi+1xi | (Two terms drop out because they cancel each other when you go round all indices) « Last Edit: Jul 4th, 2008, 1:21pm by towr » IP Logged Wikipedia, Google, Mathworld, Integer sequence DB Grimbal wu::riddles Moderator Uberpuzzler     Gender: Posts: 7527 Re: Computing Area of a Polygon   « Reply #2 on: Jul 5th, 2008, 2:13am » Quote Modify In fact,     1/2 (xi+1yi - xiyi+1) is the oriented surface of the triangle     (0,0), (xiyi), (xi+1yi+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. « Last Edit: Jul 5th, 2008, 2:15am by Grimbal » IP Logged JohanC Senior Riddler     Posts: 460 Re: Computing Area of a Polygon   « Reply #3 on: Jul 5th, 2008, 12:42pm » Quote Modify Nice. Follow up question: Extend this method to calculate the volume of a polyhedron in 3D ... IP Logged towr wu::riddles Moderator Uberpuzzler Some people are average, some are just mean.     Gender: Posts: 13730 Re: Computing Area of a Polygon   « Reply #4 on: Jul 6th, 2008, 7:07am » Quote Modify on Jul 5th, 2008, 12:42pm, JohanC wrote: Follow up question: Extend this method to calculate the volume of a polyhedron in 3D ... 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. It's not really as neat as in the 2D case, because you can't get away with a single run around the vertices. IP Logged Wikipedia, Google, Mathworld, Integer sequence DB Grimbal wu::riddles Moderator Uberpuzzler     Gender: Posts: 7527 Re: Computing Area of a Polygon   « Reply #5 on: Jul 6th, 2008, 11:46am » Quote Modify Actually,     1/2 (xi+1yi - xiyi+1) is     1/2! det( vi vj ) where the vi and vj define the edges of the polygon.  (modulo a sign). Extending to 3D gives     1/3! det( vi vj vk ) where the vi, vj, vk 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. « Last Edit: Jul 6th, 2008, 11:50am by Grimbal » IP Logged towr wu::riddles Moderator Uberpuzzler Some people are average, some are just mean.     Gender: Posts: 13730 Re: Computing Area of a Polygon   « Reply #6 on: Jul 6th, 2008, 12:29pm » Quote Modify Except that faces of a polyhedron needn't be triangles. And you still have the problem of how to run over the indices. IP Logged Wikipedia, Google, Mathworld, Integer sequence DB Grimbal wu::riddles Moderator Uberpuzzler     Gender: Posts: 7527 Re: Computing Area of a Polygon   « Reply #7 on: Jul 6th, 2008, 12:42pm » Quote Modify 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. IP Logged towr wu::riddles Moderator Uberpuzzler Some people are average, some are just mean.     Gender: Posts: 13730 Re: Computing Area of a Polygon   « Reply #8 on: Jul 6th, 2008, 1:07pm » Quote Modify on Jul 6th, 2008, 12:42pm, Grimbal wrote: Well, if they aren't triangular, just cut them into triangles. That gives us even more work to do   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? IP Logged Wikipedia, Google, Mathworld, Integer sequence DB Grimbal wu::riddles Moderator Uberpuzzler     Gender: Posts: 7527 Re: Computing Area of a Polygon   « Reply #9 on: Jul 6th, 2008, 1:12pm » Quote Modify I guess so, but it's a bit difficult to visualize.  Especially, what is "clockwise" in 4D? « Last Edit: Jul 6th, 2008, 1:13pm by Grimbal » IP Logged Pages: 1  Reply Notify of replies Send Topic Print Forum Jump: ----------------------------- riddles -----------------------------  - easy => medium   - hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board