home *** CD-ROM | disk | FTP | other *** search
/ Programmer 7500 / MAX_PROGRAMMERS.iso / CLIPPER / MISC / EMXLIB8F.ZIP / EMX / LIB / GRAPH / GPOLYGON.C < prev    next >
Encoding:
C/C++ Source or Header  |  1993-01-02  |  6.0 KB  |  253 lines
  1. /* gpolygon.c (emx+gcc) -- Copyright (c) 1987-1993 by Eberhard Mattes */
  2.  
  3. #include <stdlib.h>
  4. #include <graph.h>
  5. #define INCL_VIO
  6. #include <os2emx.h>
  7. #include "graph2.h"
  8.  
  9. struct dda
  10. {
  11.   int n, m;
  12.   int e, x, y;
  13.   int xi, yi;
  14.   int c;
  15. };
  16.  
  17. struct line
  18. {
  19.   int x0, y0, x1, y1;
  20.   int y;
  21. };
  22.  
  23. struct seg
  24. {
  25.   int x0, x1, i;
  26. };
  27.  
  28.  
  29. static int cmpx (const void *p1, const void *p2)
  30. {
  31.   const struct seg *s1, *s2;
  32.   int n1, n2;
  33.  
  34.   s1 = p1; s2 = p2;
  35.   n1 = s1->x0;
  36.   n2 = s2->x0;
  37.   if (n1 == n2)
  38.     {
  39.       n1 = s1->x1;
  40.       n2 = s2->x1;
  41.     }
  42.   if (n1 < n2)
  43.     return (-1);
  44.   else if (n1 > n2)
  45.     return (1);
  46.   else
  47.     return (0);
  48. }
  49.  
  50.  
  51. static void gpolyfill (const int *x, const int *y, int n, int color)
  52. {
  53.   int y1;
  54.   struct line lt;
  55.   struct dda dt;
  56.   int i, j1, j2, k, t, m;
  57.   int x1, x2;
  58.   struct dda *dda;
  59.   struct seg *seg;
  60.   struct line *line;
  61.  
  62.   dda = alloca (n * sizeof (*dda));
  63.   seg = alloca (n * sizeof (*seg));
  64.   line = alloca (n * sizeof (*line));
  65.   /* initialize line descriptors */
  66.   y1 = y[0];
  67.   for (i = 0; i < n; ++i)
  68.     {
  69.       lt.x0 = x[i];
  70.       lt.y0 = y[i];
  71.       if (i < n-1)
  72.         {
  73.           lt.x1 = x[i+1];
  74.           lt.y1 = y[i+1];
  75.         }
  76.       else
  77.         {
  78.           lt.x1 = x[0];
  79.           lt.y1 = y[0];
  80.         }
  81.       if (lt.y0 > lt.y1)
  82.         {
  83.           t = lt.x0; lt.x0 = lt.x1; lt.x1 = t;
  84.           t = lt.y0; lt.y0 = lt.y1; lt.y1 = t;
  85.         }
  86.       if (lt.y0 < y1)
  87.         y1 = lt.y0;
  88.       line[i] = lt;
  89.     }
  90.   /* initialize DDAs */
  91.   for (i = 0; i < n; ++i)
  92.     {
  93.       lt = line[i];
  94.       dt.y = lt.y0;
  95.       dt.x = lt.x0;
  96.       dt.n = 1 + abs (lt.y1 - lt.y0);
  97.       dt.m = 1 + abs (lt.x1 - lt.x0);
  98.       if (lt.y1 > lt.y0)
  99.         dt.yi = 1;
  100.       else
  101.         dt.yi = -1;
  102.       if (lt.x1 > lt.x0)
  103.         dt.xi = 1;
  104.       else
  105.         dt.xi = -1;
  106.       if (dt.n > dt.m)
  107.         {
  108.           dt.c = dt.n;
  109.           dt.e = dt.m/2;
  110.         }
  111.       else
  112.         {
  113.           dt.c = dt.m;
  114.           dt.e = dt.n/2;
  115.         }
  116.       dda[i] = dt;
  117.       lt.y = lt.y0-1;
  118.       line[i] = lt;
  119.     }
  120.   /* one iteration per scan line */
  121.   for (;;)
  122.     {
  123.       m = 0;
  124.       /* find intersection of lines with scan line */
  125.       for (i = 0; i < n; ++i)
  126.         {
  127.           if (line[i].y == y1-1)
  128.             {
  129.               dt = dda[i];
  130.               if (dt.c < 1)
  131.                 line[i].y = y1 - 2;
  132.               else
  133.                 {
  134.                   line[i].y = dt.y;
  135.                   x1 = dt.x;
  136.                   if (dt.n > dt.m)
  137.                     {
  138.                       x2 = dt.x;
  139.                       --dt.c;
  140.                       dt.y += dt.yi;
  141.                       dt.e += dt.m;
  142.                       if (dt.e >= dt.n)
  143.                         {
  144.                           dt.e -= dt.n;
  145.                           dt.x += dt.xi;
  146.                         }
  147.                     }
  148.                   else
  149.                     {
  150.                       for (;;)
  151.                         {
  152.                           --dt.c;
  153.                           dt.x += dt.xi;
  154.                           dt.e += dt.n;
  155.                           if (dt.e >= dt.m)
  156.                             {
  157.                               dt.e -= dt.m;
  158.                               dt.y += dt.yi;
  159.                               break;
  160.                             }
  161.                         }
  162.                       x2 = dt.x - dt.xi;
  163.                     }
  164.                   dda[i] = dt;
  165.                   if (x1 < x2)
  166.                     {
  167.                       seg[m].x0 = x1;
  168.                       seg[m].x1 = x2;
  169.                     }
  170.                   else
  171.                     {
  172.                       seg[m].x0 = x2;
  173.                       seg[m].x1 = x1;
  174.                     }
  175.                   if (y1 == line[i].y0 || y1 == line[i].y1)
  176.                     seg[m].i = i;
  177.                   else
  178.                     seg[m].i = -1;
  179.                   ++m;
  180.                 }
  181.             }
  182.         }
  183.       /* find vertices to be removed */
  184.       if (m == 0)
  185.         break;
  186.       for (i = 0; i < m; ++i)
  187.         if (seg[i].i >= 0)
  188.           {
  189.             if (i < m-1)
  190.               k = i + 1;
  191.             else
  192.               k = 0;
  193.             if (seg[k].i >= 0)
  194.               {
  195.                 j1 = seg[i].i;
  196.                 j2 = seg[k].i;
  197.                 t = abs(j1-j2);
  198.                 if (t == 1 || t == n-1)
  199.                   /* segments of two adjacent line */
  200.                   if ((y1 == line[j1].y0) != (y1 == line[j2].y0))
  201.                     /* it's not a `v' or `^' corner */
  202.                     if (line[j1].y0 != line[j1].y1 &&
  203.                         line[j2].y0 != line[j2].y1)
  204.                       /* no horizontal line */
  205.                       {
  206.                         if (seg[k].x0 < seg[i].x0)
  207.                           seg[i].x0 = seg[k].x0;
  208.                         if (seg[k].x1 > seg[i].x1)
  209.                           seg[i].x1 = seg[k].x1;
  210.                         seg[i].i = -1; /* ignore */
  211.                         seg[k].i = -2; /* remove */
  212.                       }
  213.               }
  214.           }
  215.       /* remove line segments */
  216.       for (i = 0; i < m;)
  217.         if (seg[i].i == -2)
  218.           seg[i] = seg[--m];
  219.         else
  220.           ++i;
  221.       /* draw line segments */
  222.       if (m >= 2)
  223.         qsort (seg, m, sizeof (struct seg), cmpx);
  224.       for (i = 0; i+1 < m; i += 2)
  225.         g_hline (y1, seg[i].x0, seg[i+1].x1, color);
  226.       ++y1;
  227.     }
  228. }
  229.  
  230.  
  231. void g_polygon (const int *x, const int *y, int n, int color, int fill_flag)
  232. {
  233.   int i;
  234.  
  235.   if (n >= 3)
  236.     {
  237.       GLOCK;
  238.       if (fill_flag)
  239.         gpolyfill (x, y, n, color);
  240.       else
  241.         {
  242.           for (i = 0; i < n-1; ++i)
  243.             g_line (x[i], y[i], x[i+1], y[i+1], color);
  244.           g_line (x[n-1], y[n-1], x[0], y[0], color);
  245.         }
  246.       GUNLOCK;
  247.     }
  248.   else if (n == 2)
  249.     g_line (x[0], y[0], x[1], y[1], color);
  250.   else if (n == 1)
  251.     g_set (x[0], y[0], color);
  252. }
  253.