C 7
R1.c Guest on 16th July 2020 03:00:47 AM
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <string.h>
  4.  
  5. typedef struct Region   Region;
  6. typedef struct Rect     Rect;
  7. typedef struct Point    Point;
  8. typedef struct Edge     Edge;
  9.  
  10. struct Point
  11. {
  12.         int x;
  13.         int y;
  14. };
  15.  
  16. struct Rect
  17. {
  18.         Point min;
  19.         Point max;
  20. };
  21.  
  22. struct Region
  23. {
  24.         int rectbuflen;
  25.         Rect rectbuf[100];
  26.  
  27.         int outbuflen;
  28.         Rect outbuf[100];
  29. };
  30.  
  31. struct Edge
  32. {
  33.         int x;
  34.         int flag;
  35. };
  36.  
  37. void
  38. region_insert_rect(Region *region, Rect *rect)
  39. {
  40.         memcpy(&region->rectbuf[region->rectbuflen++], rect, sizeof (Rect));
  41. }
  42.  
  43. void
  44. region_insert_outrect(Region *reg, int minx, int miny, int maxx, int maxy)
  45. {
  46.         int i;
  47.  
  48.         /* first try to enlarge existing rectangle */
  49.         for (i = 0; i < reg->outbuflen; i++) {
  50.                 if (reg->outbuf[i].max.y == miny) {
  51.                         if (reg->outbuf[i].min.x == minx &&
  52.                                 reg->outbuf[i].max.x == maxx)
  53.                         {
  54.                                 reg->outbuf[i].max.y = maxy;
  55.                                 return;
  56.                         }
  57.                 }
  58.         }
  59.  
  60.         /* else add new rectangle */
  61.         reg->outbuf[reg->outbuflen].min.x = minx;
  62.         reg->outbuf[reg->outbuflen].max.x = maxx;
  63.         reg->outbuf[reg->outbuflen].min.y = miny;
  64.         reg->outbuf[reg->outbuflen].max.y = maxy;
  65.         reg->outbuflen ++;
  66. }
  67.  
  68. int
  69. compare_rect_y(const void *a0, const void *b0)
  70. {
  71.         Rect *a = (Rect*)a0;
  72.         Rect *b = (Rect*)b0;
  73.         return a->min.y - b->min.y;
  74. }
  75.  
  76. int
  77. compare_edge(const void *a0, const void *b0)
  78. {
  79.         Edge *a = (Edge*)a0;
  80.         Edge *b = (Edge*)b0;
  81.         return a->x - b->x;
  82. }
  83.  
  84. int
  85. compare_int(const void *a0, const void *b0)
  86. {
  87.         int *a = (int*)a0;
  88.         int *b = (int*)b0;
  89.         return *a - *b;
  90. }
  91.  
  92. void
  93. region_calculate(Region *reg)
  94. {
  95.         int ylist[200];
  96.         int ylistlen;
  97.         Edge edgebuf[200];
  98.         int edgebuflen;
  99.         int a, b;
  100.         int y0, y1;
  101.         int flag, oldflag, left;
  102.         int i, k;
  103.  
  104.         reg->outbuflen = 0;
  105.  
  106.         /* make list of all y coords */
  107.         ylistlen = 0;
  108.         for (i = 0; i < reg->rectbuflen; i++) {
  109.                 ylist[ylistlen++] = reg->rectbuf[i].min.y;
  110.                 ylist[ylistlen++] = reg->rectbuf[i].max.y;
  111.         }
  112.  
  113.         /* sort list of y coords */
  114.         qsort(ylist, ylistlen, sizeof (int), compare_int);
  115.  
  116.         a = b = 0;
  117.         while (1)
  118.         {
  119.                 /* advance to next y-region */
  120.                 b = a;
  121.                 while (ylist[a] == ylist[b]) {
  122.                         if (b >= ylistlen - 1) {
  123.                                 return;
  124.                         }
  125.                         b ++;
  126.                 }
  127.  
  128.                 /* current y-region */
  129.                 y0 = ylist[a];
  130.                 y1 = ylist[b];
  131.                 a = b;
  132.  
  133.                 /* add edges that exist here */
  134.                 edgebuflen = 0;
  135.                 for (i = 0; i < reg->rectbuflen; i++) {
  136.                         if (y0 >= reg->rectbuf[i].min.y &&
  137.                                 y1 <= reg->rectbuf[i].max.y)
  138.                         {
  139.                                 edgebuf[edgebuflen].x = reg->rectbuf[i].min.x;
  140.                                 edgebuf[edgebuflen].flag = 1;
  141.                                 edgebuflen ++;
  142.  
  143.                                 edgebuf[edgebuflen].x = reg->rectbuf[i].max.x;
  144.                                 edgebuf[edgebuflen].flag = -1;
  145.                                 edgebuflen ++;
  146.                         }
  147.                 }
  148.  
  149.                 /* sort edges */
  150.                 qsort(edgebuf, edgebuflen, sizeof (Edge), compare_edge);
  151.  
  152.                 /* add rects (merging edge spans) */
  153.                 flag = oldflag = 0;
  154.                 left = 0;
  155.                 for (k = 0; k < edgebuflen; k++) {
  156.                         flag += edgebuf[k].flag;
  157.  
  158.                         /* begin span */
  159.                         if (oldflag == 0 && flag == 1) {
  160.                                 left = k;
  161.                         }
  162.  
  163.                         /* end span */
  164.                         if (oldflag == 1 && flag == 0) {
  165.                                 region_insert_outrect(reg,
  166.                                                 edgebuf[left].x,
  167.                                                 y0,
  168.                                                 edgebuf[k].x,
  169.                                                 y1);
  170.                         }
  171.  
  172.                         oldflag = flag;
  173.                 }
  174.         }
  175. }
  176.  
  177. int
  178. main(int argc, char **argv)
  179. {
  180.         Region reg;
  181.         Rect r;
  182.         int i;
  183.  
  184.         reg.rectbuflen = 0;
  185.  
  186.         r.min.x = 1;
  187.         r.min.y = 1;
  188.         r.max.x = 4;
  189.         r.max.y = 4;
  190.  
  191.         region_insert_rect(&reg, &r);
  192.  
  193.         r.min.x = 2;
  194.         r.min.y = 2;
  195.         r.max.x = 6;
  196.         r.max.y = 6;
  197.  
  198.         region_insert_rect(&reg, &r);
  199.  
  200.         r.min.x = 8;
  201.         r.min.y = 3;
  202.         r.max.x = 10;
  203.         r.max.y = 5;
  204.  
  205.         region_insert_rect(&reg, &r);
  206.  
  207.         printf("before:\n");
  208.         for (i = 0; i < reg.rectbuflen; i++) {
  209.                 printf("[%d,%d %d,%d]\n",
  210.                                 reg.rectbuf[i].min.x,
  211.                                 reg.rectbuf[i].min.y,
  212.                                 reg.rectbuf[i].max.x,
  213.                                 reg.rectbuf[i].max.y);
  214.         }
  215.  
  216.         region_calculate(&reg);
  217.  
  218.         printf("after:\n");
  219.         for (i = 0; i < reg.outbuflen; i++) {
  220.                 printf("[%d,%d %d,%d]\n",
  221.                                 reg.outbuf[i].min.x,
  222.                                 reg.outbuf[i].min.y,
  223.                                 reg.outbuf[i].max.x,
  224.                                 reg.outbuf[i].max.y);
  225.         }
  226.  
  227.         return 0;
  228. }

Paste is for source code and general debugging text.

Login or Register to edit, delete and keep track of your pastes and more.

Raw Paste

Login or Register to edit or fork this paste. It's free.