Archived

This topic is now archived and is closed to further replies.

MButchers

Area of polygon

Recommended Posts

v71    100
Yes, integral form of a parametrized surface in 3d space
first write the triangle as a parametrized plane
x=x0+u*l+v*l1
y=y0+u*m+v*m1
z=z0+u*n+v*n1

where x0,y0,z0, is the first point, (l,m,n) is the vector going
form the first point to the second ,(l1,m1,n1 ) is the second vector going form the first point to the third ,u, v are parameters, write the integral form for a surface in space in which the integrating parameter go from 0 to 1 for both u and v
write the jacobian matrix for the metric switching and remember that the matrix is formed by the derivative of each component respect the parameter u and v , calculate the square of each second order determinant and do the square root of the sum of the tree determinant , calculate the double integral , and you get the surface of a trinangle in space , note that you can calculate in this way the area of a more general surface and even a function where its domain is a function itslef , but if you don''t want to deal with advanced math here is the c funtion i did for my engine

float TriangleArea ( fVect P0,fVect P1,fVect P2 )
{
fVect N,N1;
qVect P;
N[0]=P1[0]-P0[0];
N[1]=P1[1]-P0[1];
N[2]=P1[2]-P0[2];
N1[0]=P2[0]-P0[0];
N1[1]=P2[1]-P0[1];
N1[2]=P2[2]-P0[2];
P[0]=SQR( N[0] )+SQR( N[1] )+SQR( N[2] );
P[1]=SQR( N1[0] )+SQR( N1[1] )+SQR( N1[2] );
P[2]=N[0]*N1[0]+N[1]*N1[1]+N[2]*N1[2];
P[3]=(float)sqrt(P[0]*P[1]-P[2]*P[2]);
return ( P[3] );
}


Share this post


Link to post
Share on other sites
grhodes_at_work    1385
quote:
Original post by Seyedof
Hi
divide your polygon to triangles, the area of triangle ABC is :

S = 1/2*a*b*Sin(C)



Almost. Just slight confusion. Don't you mean sin(theta), where theta is the angle between edges A and B? I think so. The corrected equation is:

S = 1/2*A*B*sin(theta)

Problem is, how do you get theta? Dot product to get cos(theta) then do an acos to get theta or use a trig relationship to get sin(theta) directly? Why not just use the cross product instead? Let the triangle be defined by points P1, P2, and P3:

Normal_Vec = (P3 - P1) cross (P2 - P1)

*DO NOT* make this a unit vector!

Then the area S is calculated by:


S = sqrt(Normal_Vec.x2 + Normal_Vec.y2 + Normal_Vec.z2)


You could then divide Normal_Vec by S to make Normal_Vec a unit vector.

So, really, you can automatically get the area of the triangle in the process of computing per-triangle unit normal vectors!

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Edited by - grhodes_at_work on October 17, 2001 10:59:58 AM

Share this post


Link to post
Share on other sites
grhodes_at_work    1385
quote:
Original post by v71
Yes, integral form of a parametrized surface in 3d space
first write the triangle as a parametrized plane
x=x0+u*l+v*l1
y=y0+u*m+v*m1
z=z0+u*n+v*n1

....



That analysis may be a bit of overkill. Why not just use the cross product rule I mentioned in my other reply without bothering with the calculus at all? For a flat triangle it makes perfect sense geometrically without thinking about integrals.

quote:
Original post by v71
P[0]=SQR( N[0] )+SQR( N[1] )+SQR( N[2] );
P[1]=SQR( N1[0] )+SQR( N1[1] )+SQR( N1[2] );



Okay, so P[0] is the square of the length of edge 1 and P[1] is the square of the length of edge 2.

quote:
Original post by v71
P[2]=N[0]*N1[0]+N[1]*N1[1]+N[2]*N1[2];



P[2] is the dot product of edge 1 onto edge 2, or the length of the projection of edge 1 onto edge 2.

quote:
Original post by v71
P[3]=(float)sqrt(P[0]*P[1]-P[2]*P[2]);



You need to multiply P[3] by 0.5 to get the area.

Effectively, you''re getting the magnitude of the cross product here, just using a different approach than I would use. Nothing wrong with that, .

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Share this post


Link to post
Share on other sites
v71    100
Nope, do the calculus and you''ll see i''ve just done it again
probably you are thinking about the already differentiated function that caomes with 0.5 ahead.

Share this post


Link to post
Share on other sites
grhodes_at_work    1385
quote:
Original post by v71
Nope, do the calculus and you''ll see i''ve just done it again
probably you are thinking about the already differentiated function that caomes with 0.5 ahead.



Its entirely possible I''ve missed something here. I didn''t copy your function into a compiler and build it, but I did implement your calculations in an Excel spreadsheet. Try your function on a triangle defined by points P0 = (0,0,0), P1 = (1,0,0), P2 = (1,1,0). That triangle has half the area of the unit square, or an area of 0.5. When I run your calcs without the 0.5 multiplier, I get an area of 1, which is twice the correct area. I varied the position of the points a bit, e.g., change P1 to (1, -.25, 0), and in every case your function gave twice the correct area.... What am I missing? You do mean that SQR(N[0]) = N[0] * N[0], don''t you?

I''ve double checked my spreadsheet against your formulas and I''m fairly sure I''m doing exactly what your function does.

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
Graham is correct, the method v71 presented should be adjusted by a factor 0.5, after which there''s no doubt the two approaches are identical.

As Graham stated, the area of a triangle ABC is half the magnitude of of the cross product of the edges AB and AC. Or expressed differently: Area(ABC)/2 = sqrt(x), where x = Dot(Cross(AB,AC), Cross(AB,AC)).

This expression for x can be rewritten using Lagrange''s identity resulting in:

x = Dot(Cross(AB,AC), Cross(AB,AC))
= Dot(AB,AB)*Dot(AC,AC) - Dot(AB,AC)^2

which is exactly what v71 presented (except for a missing division by two at the end).


Christer Ericson
Sony Computer Entertainment, Santa Monica

Share this post


Link to post
Share on other sites
v71    100
Guys, maybe i''m getting dumber as i get older , but i have done it once again and 0.5 doesn''t come from nowhere using an integral form.

Share this post


Link to post
Share on other sites
grhodes_at_work    1385
I suggest you look for an error in your integration. The error must be there. Perhaps you''ve actually done the integration for a parallelogram instead of half the parallelogram?

Graham Rhodes
Senior Scientist
Applied Research Associates, Inc.

Share this post


Link to post
Share on other sites
AndyMan    148
I think I have a simpler method for finding the area of a polygon in 2D.

For every line (x1,y1)-(x2,y2) calculate (x1-x2)*(y1+y2)/2. Add this up for every line segment. Simple, isn''t it.

I''ll do an example (to check that it works!)
A quadralateral (0,0)-(5,0)-(-2,4)-(-2,-3)-(0,0):
(0,0)-(5,0) (0 - 5)*(0 + 0) = 0
(5,0)-(-2,4) (5 - -2)*(0 + 4) = 28
(-2,4)-(-2,-3) (-2 - -2)*(4 + -3) = 0
(-2,-3)-(0,0) (-2 - 0)*(-3 + 0) = 6
Area = (0 + 28 + 0 + 6)/2 = 17.

Yep, it works. I did choose an example which gave me 0''s, but the method works, with any number of sides. If you go around clockwise, you get the negative result.

If you''re in 3 dimensions, you can''t do this. But chances are if you''ve got a polygon you''ve worked it out in 2D anyway.

Speaking of three dimensions, did you know that Pythagoras'' theorem works for area of a right angled pyramid? The three small sides must all have a right angle, eg a pyramid on the floor, flat against two walls meeting at right angles. The square of the AREAS of the three small sides equal the square of the AREA of the large side, which is diagonal in all 3 directions.

With this in mind, if you are in 3D coords (and if you are your vertices have to be in the plane else it isn''t a proper polygon) you might be able to use this method anyway. Calculate the area looking from the z-direction by ignoring all the z-values. Then get the area looking from the two other directions. Clockwise/anticlockwise won''t matter because you''ll be squaring it anyway. So you square these three areas, add them together, get the square root of the total, and you''ve got the whole area.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
The method just presented is the Green''s Theorem. Kudos for figuring this out just by yourself if that is indeed the case!

Share this post


Link to post
Share on other sites