home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / graphics / 9212 < prev    next >
Encoding:
Text File  |  1992-08-27  |  3.0 KB  |  124 lines
  1. Newsgroups: comp.graphics
  2. Path: sparky!uunet!newsgate.watson.ibm.com!yktnews!admin!curt
  3. From: curt@watson.ibm.com (Curt McDowell)
  4. Subject: Re: Area of polygons
  5. Sender: news@watson.ibm.com (NNTP News Poster)
  6. Message-ID: <1992Aug27.180851.5035@watson.ibm.com>
  7. Date: Thu, 27 Aug 1992 18:08:51 GMT
  8. Lines: 109
  9. Disclaimer: This posting represents the poster's views, not necessarily those of IBM
  10. References:  <1464@igd.fhg.de>
  11. Nntp-Posting-Host: gorby.watson.ibm.com
  12. Organization: IBM T.J. Watson Research Center
  13. Keywords: polygon,triangle,constraints
  14.  
  15. In article <1464@igd.fhg.de>, willm@igd.fhg.de (Matt Will) writes:
  16. > I don't know if this is the right place to ask, but I'll give it a try.
  17. > I am currently trying to find constraints for planar (2D) polygons, and in
  18. > particular, I have troubles finding a constraint (=a formula) to calculate
  19. > the area of a polygon.
  20. > 
  21. > I know that it is possible to subdivide a polygon into triangles, but I haven't
  22. > found a general formula to find out which diagonals to use for this. With 
  23. > convex polygons, things are easy, but I got stuck as far as concave polygons
  24. > are concerned.
  25. > 
  26. > Please e-mail me, since I am not reading this list. You can reach me at the
  27. > address listed below.
  28. > 
  29. > Thank you for your help,
  30. > Matt Will <willm@igd.fhg.de>
  31.  
  32. Here's an area formula that so neat I thought I'd post it in addition
  33. to sending it to Matt.  It probably extends to 3D as well, but right now
  34. I don't have time to test that theory.
  35.  
  36. /*
  37.  * polyarea
  38.  *
  39.  *   Computes the area of an arbitrary n-point polygon using the following
  40.  *   amazingly beautiful formula from high school geometry:
  41.  *
  42.  *            | x(0) y(0) |       | x(1) y(1) |             | x(n-1) y(n-1) |
  43.  *   2A = det |           | + det |           | + ... + det |               |
  44.  *            | x(1) y(1) |       | x(2) y(2) |             | x(0)   y(0)   |
  45.  *
  46.  *   The area is positive if the points are in counter-clockwise order,
  47.  *   negative if they are clockwise.
  48.  *
  49.  *   Curt McDowell, IBM 08-27-92
  50.  */
  51.  
  52. double polyarea(x, y, n)
  53.     double           *x, *y;
  54.     int        n;
  55. {
  56.     double        a;
  57.     int        i;
  58.  
  59.     a = x[n - 1] * y[0] - x[0] * y[n - 1];
  60.  
  61.     for (i = 0; i < n - 1; i++)
  62.         a += x[i] * y[i + 1] - x[i + 1] * y[i];
  63.  
  64.     return (a / 2.0);
  65. }
  66.  
  67. /*
  68.  * Test main program for polyarea
  69.  */
  70.  
  71. #include <stdio.h>
  72. #include <math.h>
  73.  
  74. extern    void           *malloc();
  75.  
  76. main(argc, argv)
  77.     int        argc;
  78.     char           *argv[];
  79. {
  80.     int        n, i;
  81.     double           *x, *y;
  82.  
  83.     if (argc != 2) {
  84.         fprintf(stderr,
  85.             "Usage: polyarea npoints\n");
  86.         exit(1);
  87.     }
  88.  
  89.     n    = atoi(argv[1]);
  90.  
  91.     /*
  92.      * Input array of n points
  93.      */
  94.  
  95.     printf("Please enter %d points.\n", n);
  96.  
  97.     x    = malloc(n * sizeof (*x));
  98.     y    = malloc(n * sizeof (*y));
  99.  
  100.     for (i = 0; i < n; i++) {
  101.         char    buf[256];
  102.  
  103.         printf("p%d.x? ", i);
  104.         fflush(stdout);
  105.         if (gets(buf) == 0)
  106.             exit(0);
  107.         x[i]    = atof(buf);
  108.  
  109.         printf("p%d.y? ", i);
  110.         fflush(stdout);
  111.         if (gets(buf) == 0)
  112.             exit(0);
  113.         y[i]    = atof(buf);
  114.     }
  115.  
  116.     printf("The area of the polygon is %f units.\n", polyarea(x, y, n));
  117.  
  118.     exit(0);
  119. }
  120.  
  121. --
  122. Curt McDowell
  123. IBM T. J. Watson Research Center
  124.