home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / graphics / 13003 < prev    next >
Encoding:
Text File  |  1992-12-17  |  2.9 KB  |  108 lines
  1. Path: sparky!uunet!pipex!warwick!uknet!cvedg!medusa.prime.com!mrj
  2. From: mrj@CIS.Prime.COM (Mohammad Reza Jahanbin)
  3. Newsgroups: comp.graphics
  4. Subject: Re: Calculating polygon areas
  5. Summary: Proof of.
  6. Message-ID: <1992Dec17.154323.17206@medusa.prime.com>
  7. Date: 17 Dec 92 15:43:23 GMT
  8. References: <1992Dec16.173613.5737@medusa.prime.com>
  9. Sender: news@medusa.prime.com
  10. Reply-To: mrj@CIS.Prime.COM
  11. Organization: Computervision R&D Ltd
  12. Lines: 94
  13.  
  14. In article 5737@medusa.prime.com, mrj@CIS.Prime.COM (Mohammad Reza Jahanbin) writes:
  15. > 
  16. > There is a more general form of the above:
  17. > 
  18. >     Area = 0.5 \sum_{i=0}^{n} (P_i X P_{i+1})         
  19. > 
  20. >     s.t. i+1 = (i+1) mod n i.e. when i = n then P_{i+1} = P_0
  21. > 
  22. > Where X denotes a vector cross product. 
  23. > 
  24. > This holds for 2-d or 3-d (coplanar), convex or concave, polygons with n+1 vertices
  25. > P_0,...,P_n. Note, if the Area is negative then the order of points are describing a left handed polygon.
  26. > 
  27. > The proof is simple. If anyone is interested I'll post it to the net.
  28.  
  29. Since I have had a number of people asking me for this proof I am posting it:
  30.  
  31.  
  32.               _______      
  33.              /.     .\
  34.             /  .   .  \ a2
  35.            /    .C.    \ 
  36.        Pn /..bn..o..b2..\
  37.           \    .   .    / P2
  38.         an \ b0   b1.  /
  39.             \.       ./  a1
  40.              ---------
  41.         P0  a0   P1
  42.  
  43.  
  44.  
  45. Consider the above polygon with n+1 vertices. The vertices are
  46. P0...Pn. C is any point inside the polygon such that all vertices are
  47. "visible" from C.
  48.  
  49. Assume the polygon is triangulated into n+1 triangles P0P1C, P1P2C,
  50. ..., PiP(i+1)C, ..., PnP0C. Now the area of the polygon is equal to
  51. the sum of the areas of triangles. This holds wheather or not the
  52. polygon is convace or convex, due to the choice of C.
  53.  
  54.  
  55. Let the area of the ith triangle PiP(i+1)C be Ai. Clearly 
  56.  
  57.             Ai = 0.5 * |ai X bi|
  58. where 
  59.             ai = P(i+1) - Pi     and                        (1)
  60.             bi = C - Pi
  61.  
  62. So the area of the polygon, A(p) is:
  63.  
  64.             A(p) = sum{i=0}^{n} Ai
  65.                  = 0.5 * sum{i=0}^{n} (|ai X bi|)           (2)
  66.  
  67. For a coplanar polygon all the vectors ai X bi are in the same direction so
  68. Eqn.(2) can be written as:
  69.  
  70.             A(p) = 0.5 * |sum{i=0}^{n} (ai X bi)|           (2a)
  71.                 
  72.  
  73.  
  74. Using Eqn.(1) and (2a) 
  75.  
  76.       sum{i=0}^{n} (ai X bi) = sum{i=0}^{n} (P(i+1) - Pi) X (C - Pi)
  77.      = sum{i=0}^{n} (((P(i+1) - Pi) X C) - (P(i+1) X Pi) + (Pi X Pi))
  78.                                 \-----/
  79.                                    =0
  80.      = sum{i=0}^{n} ((P(i+1) - Pi) X C) + sum{i=0}^{n} (Pi X P(i+1))  (3)
  81.        \------------------------------/
  82.             = 0
  83.  
  84. Note: it can be shown (using Tensor notaion or otherwise) that:
  85.  
  86.         sum{i=0}^{n} ((P(i+1) - Pi) X C) = 0 
  87.     
  88. for a closed polygon.
  89.  
  90.  
  91. So from (2a) and (3)
  92.  
  93.         A(p) = 0.5 * |sum{i=0}^{n} (Pi X P(i+1))|                (4)
  94.  
  95. Since (4) is independent of C it must hold true for both concave and convex
  96. polygons.
  97.  
  98.  
  99.  
  100.  
  101.  
  102. ---
  103. float o=0.075,h=1.5,T,r,O,l,I;int _,L=80,s=3200;main(){for(;s%L||
  104. (h-=o,T= -2),s;4 -(r=O*O)<(l=I*I)|++ _==L&&write(1,(--s%L?_<L?--_
  105. %6:6:7)+"World! \n",1)&&(O=I=l=_=r=0,T+=o /2))O=I*2*O+h,I=l+T-r;}
  106.  
  107. mohammed.
  108.