Algorithm for Area of a closed polygon.
Torsten Hans
hans at tat.physik.uni-tuebingen.de
Thu Nov 13 00:17:42 PST 2003
Hi,
a very elegant and fast (since it is linear) way to do this is
to use Green's theorem over the border of the closed polygon.
the polygon doesn't need to be convex.
Just as a reminder: Green's theorem reduces a surface integral
to a line integral over the border of the surface integral.
(sorry for my bad english).
here is a c code fragmet that calculates the area
and center.
num_vertices is the number of vertices of the polygon.
v2dx[] and v2dy[] are double arrays that store the x and y positions.
for easier computation the first vertex v2dx[0] and v2dy[0]
is stored in v2dx[n] and v2dy[n] again.
-------------------------------------------------------
double area = 0;
double center2dx = 0;
double center2dy = 0;
for (int i=0; i<num_vertices; i++)
{
tmreal t = 2*v2dx[i]*v2dy[i+0] +
v2dy[i]*v2dx[i+1] +
v2dx[i]*v2dy[i+1] +
2*v2dx[i+1]*v2dy[i+1];
area += (v2dx[i]-v2dx[i+1]) * (v2dy[i]+v2dy[i+1]);
center2d.x += (+v2dx[i]-v2dx[i+1])*t;
center2d.y += (-v2dy[i]+v2dy[i+1])*t;
}
area *= 0.5;
center2dx *= 1/(6*area);
center2dy *= 1/(6*area);
-------------------------------------------------------
if you don't require the center calculation, the code is
extremly short:
-------------------------------------------------------
area = 0;
for (int i=0; i<num_vertices; i++)
{
area += (v2dx[i]-v2dx[i+1]) * (v2dy[i]+v2dy[i+1]);
}
area *= 0.5;
-------------------------------------------------------
let me know if it works.
regards,
torsten hans
On Wed, 12 Nov 2003, Ted Hill wrote:
> I want to be able to calculate the area inside a closed many-sided
> polygon.
>
> Given an array of the (x,y) vertices that define the polygon, is there a
> well-known algorithm that can calculate the enclosed area quickly?
>
> Thanks,
>
> Ted Hill
>
>
>
>
-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.
More information about the Compgeom-announce
mailing list