ingoldsb@ctycal.COM (Terry Ingoldsby) (10/03/89)
This is probably a trivial problem, and one that has been much
discussed, but I need an algorithm that will calculate (quickly)
the area of an arbitrary polygon. It would be *nice* if it could
handle objects that include arcs, instead of lines for the edges of
the `polygon'. I have to be able to handle complicated cases like
*--------------------------*
| *________________|
| |
| *_______*
| /
*_____* /
/ / It's hard to draw diagonal lines!
*/------*
Sorry if this is trivial or has been discussed ad nauseum before.
--
Terry Ingoldsby ctycal!ingoldsb@calgary.UUCP
Land Information Systems or
The City of Calgary ...{alberta,ubc-cs,utai}!calgary!ctycal!ingoldsbjosh@cditi.UUCP (Josh Muskovitz) (10/04/89)
In article <484@ctycal.UUCP>, ingoldsb@ctycal.COM (Terry Ingoldsby) writes:
# I need an algorithm that will calculate (quickly)
# the area of an arbitrary polygon. It would be *nice* if it could
# handle objects that include arcs, instead of lines for the edges of
# the `polygon'. I have to be able to handle complicated cases like
#
# *--------------------------*
# | *________________|
# | |
# | *_______*
# | /
# *_____* /
# / / It's hard to draw diagonal lines!
# */------*
#
# --
# Terry Ingoldsby ctycal!ingoldsb@calgary.UUCP
You should be able to pick an arbitrary point in the plane, and build a list
of triangles from every pair of adjacent endpoints. The trick is determining
whether to add or subtract the area of the tirangle from the ongoing subtotal.
Does anyone have an easy way to determine this?
josh @ uunet!cditibill@stuart.stat.washington.edu (Bill Dunlap) (10/05/89)
In article <619@cditi.UUCP> josh@cditi.UUCP (Josh Muskovitz) writes: >In article <484@ctycal.UUCP>, ingoldsb@ctycal.COM (Terry Ingoldsby) writes: ># I need an algorithm that will calculate (quickly) ># the area of an arbitrary polygon. > >You should be able to pick an arbitrary point in the plane, and build a list >of triangles from every pair of adjacent endpoints. The trick is determining >whether to add or subtract the area of the tirangle from the ongoing subtotal. 1/2 * sum( x(i)*y(i-1) - y(i)*x(i-1) ), wrapping the indexes around the ends will give the (signed) area of a polygon. The sign is positive if the vertices are given clockwise. Each summand is the signed area of a triangle with one edge an edge of the polygon and the remaining vertex (0,0). Note the similarity to Green's (or is it Stoke's?) theorem in calculus which relates an integral over a boundary to an integral over the area within that boundary. Bill Dunlap
ksbooth@watcgl.waterloo.edu (Kelly Booth) (10/05/89)
In article <484@ctycal.UUCP> ingoldsb@ctycal.COM (Terry Ingoldsby) writes: >This is probably a trivial problem, and one that has been much >discussed, but I need an algorithm that will calculate (quickly) >the area of an arbitrary polygon. Use Newell's formula, which is in the appendix of the second edition of Neuman and Sproull. It works for any planar polygon (convex/concave, simple/non-simple) and has the nice property that it gracefully degrades when the polygon is not planar (due to roundoff errors in the vertex coordinates or simply bad data to begin with). For the special case n=3, this is just the cross product formula for the area of a triangle (actually twice the area, you need to divide the answer by two in all cases), given two vectors which form the base and side of the parallelogram. What you get is a vector whose magnitude is the area of the polygon and whose direction is normal to the plane of the polygon.
jackg@tekirl.LABS.TEK.COM (Jack Gjovaag) (10/05/89)
In article <484@ctycal.UUCP>, ingoldsb@ctycal.COM (Terry Ingoldsby) writes: > I need an algorithm that will calculate (quickly) > the area of an arbitrary polygon. It would be *nice* if it could > handle objects that include arcs, instead of lines for the edges of > the `polygon'. I have to be able to handle complicated cases like > > *--------------------------* > | *________________| > | | > | *_______* > | / > *_____* / > / / It's hard to draw diagonal lines! > */------* > > -- > Terry Ingoldsby ctycal!ingoldsb@calgary.UUCP > If you have the polygon described in terms of an ordered list of n vertices (x(i), y(i)), where i=1 to n, and where (x(n), y(n)) = (x(1), y(1)), i.e., the first point of the list is duplicated at the end of the list, then the area can be found by the following formula: A = abs(sum (i=1 to n) (x(i+1)-x(i))*(y(i+1)+y(i))/2) If the edges of the polygon cross, then the value of A won't mean much. Removing the absolute value function and looking at the sign of the sum will tell you if the polygon was described in a clockwise (>0) or counterclockwise (<0) direction. Since each term of the sum is the signed area under the segment describing an edge, the formula can be generalized to edges other than straight line segments by replacing the appropriate terms with the definite integral representing the signed area under the curve segment. Jack Gjovaag Tek Labs
ksbooth@watcgl.waterloo.edu (Kelly Booth) (10/06/89)
In article <6059@tekgvs.LABS.TEK.COM> jackg@tekirl.LABS.TEK.COM (Jack Gjovaag) writes: > >A = abs(sum (i=1 to n) (x(i+1)-x(i))*(y(i+1)+y(i))/2) > This is Newell's formula (with the abs and the /2 added). The general form works in 3-D and computes three terms which are the components of a vector whose magnitude (abs again) is the area. The formula does have meaning if the edges cross in the sense that it subtracts out areas.
bond@delta.CES.CWRU.Edu (angus bond) (10/06/89)
I see that a lot of replys to this question suggest breaking the polygon down into triangular pieces. This is not necessary. I also wish I had a copy of Newmann and Sproul handy to see if the solution I am proposing matches theirs. But here goes... I found this algorithm in the _Handbook_of_Mathematical_Tables_ published by the Chemical Rubber Company, affectionately referred to as the CRC Math Tables book. Every edition has this algorithm in it. I don't have it handy so you will have to go get the book or a similar one to get the precise scoop. The formula is sort of like a laterally extended 2x2 determinant: - - - - - / / / / / xn x1 x2 x3 ... xn-1 xn yn y1 y2 y3 ... yn-1 yn \ \ \ \ \ + + + + + That is, (xn * y1) + (x1 * y2) + (x2 * y3) + ... + (xn-1 * yn) - (yn * x1) - (y1 * x2) - (y2 * x3) - ... - (yn-1 * xn) This formula (provided I remembered it correctly), gives the area of the polygon formed by the points (x1,y1), (x2,y2), ... (xn, yn). If the curve crosses itself, it subtracts the area of the reversed section. Order the points one way and you get a positive area; order them the other way and you get a negative area. This equation works for any number of points. One thing I don't know is how well this formula handles round-off errors for large n. It does work well for reasonable values of n. I hope this helped. Angus Bond bond@alpha.cwru.edu (did I get my address right?) school: (216) 368-5506 work: (216) 349-2548
allan@didsgn.uucp (didsgn) (10/06/89)
ingoldsb@ctycal.COM (Terry Ingoldsby) writes: >This is probably a trivial problem, and one that has been much >discussed, but I need an algorithm that will calculate (quickly) >the area of an arbitrary polygon. It would be *nice* if it could >handle objects that include arcs, instead of lines for the edges of >the `polygon'. I have to be able to handle complicated cases like > *--------------------------* > | *________________| > | | > | *_______* > | / > *_____* / > / / It's hard to draw diagonal lines! > */------* >Sorry if this is trivial or has been discussed ad nauseum before. If this is an image that has been stored in "pixel"-type memory, and not just a list of coordinates (i.e. given an arbitrary shape, determine the area of the shape), then I have a very simple approach that works fairly quickly (it depends on the length of the outside perimeter). As a side benifit, the perimeter of the object and knowledge as to whether it is a hole or an object is also given. If you're interested, I forward the details to anyone interested. -- Allan G. Schrum | Sign it? Without reading the fine print? Digital Design, Inc. |----------------------------------------- 3060 Business Park Drive | (404) 447-0274 Norcross, GA 30071 | ...!gatech!rebel!didsgn!allan
kensy@microsoft.UUCP (Ken Sykes) (10/06/89)
One technique that has been mentioned in the past is to "FloodFill" the area, but instead of drawing the interior points, count them. This will handle all of the irregular areas as well. The two drawbacks to this approach is it *can* be slow and you need to find the interior of the area to use as the seed point for FloodFill. Of course, the areas will have to be closed as well. If you need a faster solution you could ScanConvert the polygons, again counting points instead of plotting them. This could also work for other areas such as arcs, but the ScanConverter would have to be smart enough to deal with non-polygonal areas. ----------------------- Ken Sykes SDE at large.
Kenneth.Maier@p3.f11.n369.z1.FIDONET.ORG (Kenneth Maier) (10/09/89)
>If this is an image that has been stored in "pixel"-type memory, and not >just a list of coordinates (i.e. given an arbitrary shape, determine >the area of the shape), then I have a very simple approach that works >fairly quickly (it depends on the length of the outside perimeter). As >a side benifit, the perimeter of the object and knowledge as to >whether it is a hole or an object is also given. If you're interested, >I forward the details to anyone interested. > >-- >Allan G. Schrum | Sign it? Without reading the fine >print? >Digital Design, Inc. >|----------------------------------------- >3060 Business Park Drive | (404) 447-0274 >Norcross, GA 30071 | ...!gatech!rebel!didsgn!allan >m Allan, I would very much like to hear your idea. I would assume this method will be fast if the area under discussion is very small. For large areas, it would seem using the coordinates to calculate the area would be better. It will be interesting to see how you go about this! -Kenneth -- Kenneth Maier via FidoNet node 1:369/11 UUCP: {attctc,<internet>!mthvax}!ankh,novavax!branch!11.3!Kenneth.Maier
airey@matisse.cs.unc.edu (John Airey) (10/09/89)
In article <2273@uw-entropy.ms.washington.edu> bill@stuart.UUCP () writes: >>In article <484@ctycal.UUCP>, ingoldsb@ctycal.COM (Terry Ingoldsby) writes: >># I need an algorithm that will calculate (quickly) >># the area of an arbitrary polygon. ^^^^^^^^^ If arbitrary means possibly concave, the following suggestion is inadequate. >1/2 * sum( x(i)*y(i-1) - y(i)*x(i-1) ), wrapping the indexes around the ends >will give the (signed) area of a polygon. The sign is positive if the >vertices are given clockwise. Each summand is the signed area of a triangle >with one edge an edge of the polygon and the remaining vertex (0,0). > Bill Dunlap john m. airey airey@cs.unc.edu
MARWK@levels.sait.edu.au (10/11/89)
In article <Oct5.1989.5868@didsgn.uucp>, allan@didsgn.uucp (didsgn) writes: > ingoldsb@ctycal.COM (Terry Ingoldsby) writes: > >>This is probably a trivial problem, and one that has been much >>discussed, but I need an algorithm that will calculate (quickly) >>the area of an arbitrary polygon. It would be *nice* if it could >>handle objects that include arcs, instead of lines for the edges of >>the `polygon'. I have to be able to handle complicated cases like > >> *--------------------------* >> | *________________| >> | | >> | *_______* >> | / >> *_____* / >> / / It's hard to draw diagonal lines! >> */------* > >>Sorry if this is trivial or has been discussed ad nauseum before. > > If this is an image that has been stored in "pixel"-type memory, and not > just a list of coordinates (i.e. given an arbitrary shape, determine > the area of the shape), then I have a very simple approach that works > fairly quickly (it depends on the length of the outside perimeter). As > a side benifit, the perimeter of the object and knowledge as to > whether it is a hole or an object is also given. If you're interested, > I forward the details to anyone interested. > Please post it. Ray
ksbooth@watcgl.waterloo.edu (Kelly Booth) (10/11/89)
In article <9885@thorin.cs.unc.edu> airey@matisse.cs.unc.edu (John Airey) writes: >In article <2273@uw-entropy.ms.washington.edu> bill@stuart.UUCP () writes: >>>In article <484@ctycal.UUCP>, ingoldsb@ctycal.COM (Terry Ingoldsby) writes: >>># I need an algorithm that will calculate (quickly) >>># the area of an arbitrary polygon. > ^^^^^^^^^ > >If arbitrary means possibly concave, the following suggestion is inadequate. > >>1/2 * sum( x(i)*y(i-1) - y(i)*x(i-1) ), wrapping the indexes around the ends >>will give the (signed) area of a polygon. The sign is positive if the >>vertices are given clockwise. Each summand is the signed area of a triangle >>with one edge an edge of the polygon and the remaining vertex (0,0). >> Bill Dunlap The formula works. It is Newell's formula. It handles concave polygons quite well. It can be derived by an easy induction starting with the formula for the cross product of two vectors and the fact that this gives the area of the parall..gram (I never could spell this!) defined by the two vectors. The algorithm is "optimal" in the sense that it looks at each vertex only once and does a relatively small amount of work for each.
phil@hpsmdca.HP.COM (Philip Walden) (10/12/89)
>> >>A = abs(sum (i=1 to n) (x(i+1)-x(i))*(y(i+1)+y(i))/2) >> > >This is Newell's formula (with the abs and the /2 added). The general form >works in 3-D and computes three terms which are the components of a vector >whose magnitude (abs again) is the area. > If the ABS was not done, would the sign of A also be an indication of "handedness" of the polygon? Is there a proof for this? -------------------------------------------------------------------------- Philip Walden Hewlett Packard Surface Mount Development Center 3500 Deer Creek Road Palo Alto, CA 94304 (415) 857-3899 --------------------------------------------------------------------------
Bill.Hale@f42.n363.z1.FIDONET.ORG (Bill Hale) (10/13/89)
The files dancad1-2-3-4.zip may solve your problem. This is pckeydraw and combines grafice, and the ability to make artists drawings. If this helps you out maybe you can give me some tips on how to use the program.. It's very powerful, and beyond me at this time. -- Fidonet: Bill Hale via 1:363/9 Internet: Bill.Hale@f42.n363.z1.FIDONET.ORG UUCP: uunet!sceard!tarpit!libcmp!mamab!42!Bill.Hale
ingoldsb@ctycal.UUCP (Terry Ingoldsby) (10/14/89)
This message is empty.
ksbooth@watcgl.waterloo.edu (Kelly Booth) (10/16/89)
In article <22240001@hpsmdca.HP.COM> phil@hpsmdca.HP.COM (Philip Walden) writes: >>> >>>A = abs(sum (i=1 to n) (x(i+1)-x(i))*(y(i+1)+y(i))/2) >>> >> >>This is Newell's formula (with the abs and the /2 added). The general form >>works in 3-D and computes three terms which are the components of a vector >>whose magnitude (abs again) is the area. >> > If the ABS was not done, would the sign of A also be > an indication of "handedness" of the polygon? Is there > a proof for this? Yes. This was mentioned in the original posting. Newell's formula gives (a,b,c), which is a 3-D vector whose magnitude (absolute value) is the area of the polygon (times two). The direction of the vector is normal to the plane of the polygon, with the convention that the normal points in the direction (handedness) of a point that would view the vertices in a clockwise order of traversal as they are summed in the formula. Look in the appendix to the second edition of Newman and Sproull for more info.
davidle@microsoft.UUCP (David Levine) (10/20/89)
The "Newell" algorithm is based on Green's theorem which you can find in many mathematics books. It basically turns an integral over an area into an integral over a contour. I don't have the book in my office but I can provide the algorithm to you. For the case of a polygon in the X-Y plane, it does indeed reduce to Newell's algorithm. You can use Greens theorem to calculate the area of a figure with curved edges but the resulting formula is, of course, more complex. I have used Greens theorm to derive Newell's algorithm and also to derive formulas for center of mass and moment/product of inertia. The method works for arbitrary polygons (convex/concave). In the area case, the "equation" being integrated over the area of the polygon is just the constant "1". David Levine
grace@iitmax.IIT.EDU (Thom Grace) (10/20/89)
In article <8115@microsoft.UUCP> David Levine cites Green's Theorem which
he contends "you can find in many mathematics books". Well, my suboptimal
contribution to this discussion is to provide the references I have here at
hand to Green's Theorem:
Spivak, "Calculus On Manifolds", W.A. Benjamin, Inc., NY, 1965,
ISBN 0-8053-9021-9, p. 134.
Churchill, Brown, and Verhey, "Complex Variables and Applications",
Mc-Graw Hill, NY, 1974, ISBN 0-07-010855-2, p. 115.
Now I have a question for D. Levine: I know about Green's Theorem, and I
know about Newell's Formula, yet I have never (formally) tried to connect
the two. So --- how do you do it???
==============================================================================
Thom Grace grace@iitvax
10 W. 31 St. (312) 567-3918
IIT Center
Chicago, IL 60616
==============================================================================