src/src/Kernel/Types/rectangles.cpp

   1
   2 /******************************************************************************
   3 * MODULE     : rectangles.cpp
   4 * DESCRIPTION: Rectangles and lists of rectangles with reference counting.
   5 *              Used in graphical programs.
   6 * COPYRIGHT  : (C) 1999  Joris van der Hoeven
   7 *******************************************************************************
   8 * This software falls under the GNU general public license version 3 or later.
   9 * It comes WITHOUT ANY WARRANTY WHATSOEVER. For details, see the file LICENSE
  10 * in the root directory or <http://www.gnu.org/licenses/gpl-3.0.html>.
  11 ******************************************************************************/
  12
  13 #include "rectangles.hpp"
  14
  15 /******************************************************************************
  16 * Routines for rectangles
  17 ******************************************************************************/
  18
  19 rectangle_rep::rectangle_rep (SI x1b, SI y1b, SI x2b, SI y2b):
  20   x1 (x1b), y1 (y1b), x2 (x2b), y2 (y2b) { }
  21
  22 rectangle::rectangle (SI x1b, SI y1b, SI x2b, SI y2b):
  23   rep (tm_new<rectangle_rep> (x1b, y1b, x2b, y2b)) { }
  24
  25 rectangle::operator tree () {
  26   return tree (TUPLE,
  27                as_string (rep->x1), as_string (rep->y1),
  28                as_string (rep->x2), as_string (rep->y2));
  29 }
  30
  31 tm_ostream&
  32 operator << (tm_ostream& out, rectangle r) {
  33   out << "rectangle ("
  34       << r->x1 << ", " << r->y1 << ", "
  35       << r->x2 << ", " << r->y2 << ")";
  36   return out;
  37 }
  38
  39 rectangle
  40 copy (rectangle r) {
  41   return rectangle (r->x1, r->y1, r->x2, r->y2);
  42 }
  43
  44 bool
  45 operator == (rectangle r1, rectangle r2) {
  46   return
  47     (r1->x1==r2->x1) && (r1->y1==r2->y1) &&
  48     (r1->x2==r2->x2) && (r1->y2==r2->y2);
  49 }
  50
  51 bool
  52 operator != (rectangle r1, rectangle r2) {
  53   return
  54     (r1->x1!=r2->x1) || (r1->y1!=r2->y1) ||
  55     (r1->x2!=r2->x2) || (r1->y2!=r2->y2);
  56 }
  57
  58 bool
  59 operator <= (rectangle r1, rectangle r2) {
  60   return
  61     (r1->x1>=r2->x1) && (r1->x2<=r2->x2) &&
  62     (r1->y1>=r2->y1) && (r1->y2<=r2->y2);
  63 }
  64
  65 bool
  66 intersect (rectangle r1, rectangle r2) {
  67   return
  68     (r1->x1<r2->x2) && (r1->x2>r2->x1) &&
  69     (r1->y1<r2->y2) && (r1->y2>r2->y1);
  70 }
  71
  72 rectangle
  73 translate (rectangle r, SI x, SI y) {
  74   return rectangle (r->x1+x, r->y1+y, r->x2+x, r->y2+y);
  75 }
  76
  77 double
  78 area (rectangle r) {
  79   double w= max (r->x2 - r->x1, 0);
  80   double h= max (r->y2 - r->y1, 0);
  81   return w*h;
  82 }
  83
  84 /******************************************************************************
  85 * Miscellaneous subroutines
  86 ******************************************************************************/
  87
  88 // FIXME: Why do we need this? Compiler bug?
  89 #define min(x,y) ((x)<=(y)?(x):(y))
  90 #define max(x,y) ((x)<=(y)?(y):(x))
  91
  92 void
  93 complement (rectangle r1, rectangle r2, rectangles& l) {
  94   if (!intersect (r1, r2)) { r1 >> l; return; }
  95   if (r1->x1 < r2->x1) rectangle (r1->x1, r1->y1, r2->x1, r1->y2) >> l;
  96   if (r1->x2 > r2->x2) rectangle (r2->x2, r1->y1, r1->x2, r1->y2) >> l;
  97   if (r1->y1 < r2->y1) rectangle (max (r1->x1, r2->x1), r1->y1,
  98                                   min (r1->x2, r2->x2), r2->y1) >> l;
  99   if (r1->y2 > r2->y2) rectangle (max (r1->x1, r2->x1), r2->y2,
 100                                   min (r1->x2, r2->x2), r1->y2) >> l;
 101 }
 102
 103 void
 104 complement (rectangles l1, rectangle r2, rectangles& l) {
 105   for (; !is_nil (l1); l1= l1->next)
 106     complement (l1->item, r2, l);
 107 }
 108
 109 void
 110 intersection (rectangle r1, rectangle r2, rectangles& l) {
 111   if (!intersect (r1, r2)) return;
 112   rectangle (max (r1->x1, r2->x1), max (r1->y1, r2->y1),
 113              min (r1->x2, r2->x2), min (r1->y2, r2->y2)) >> l;
 114 }
 115
 116 rectangle
 117 operator * (rectangle r, int d) {
 118   return rectangle (r->x1*d, r->y1*d, r->x2*d, r->y2*d);
 119 }
 120
 121 rectangle
 122 operator / (rectangle r, int d) {
 123   return rectangle (r->x1/d, r->y1/d, r->x2/d, r->y2/d);
 124 }
 125
 126 /******************************************************************************
 127 * Exported routines for rectangles
 128 ******************************************************************************/
 129
 130 rectangles
 131 operator - (rectangles l1, rectangles l2) {
 132   rectangles a=l1;
 133   for (; !is_nil (l2); l2= l2->next) {
 134     rectangles b;
 135     complement (a, l2->item, b);
 136     a=b;
 137   }
 138   return a;
 139 }
 140
 141 rectangles
 142 operator & (rectangles l1, rectangles l2) {
 143   rectangles l, lc1, lc2;
 144   for (lc1= l1; !is_nil (lc1); lc1= lc1->next)
 145     for (lc2= l2; !is_nil (lc2); lc2= lc2->next)
 146       intersection (lc1->item, lc2->item, l);
 147   return l;
 148 }
 149
 150 bool
 151 adjacent (rectangle r1, rectangle r2) {
 152   return
 153     (((r1->x2==r2->x1) || (r1->x1==r2->x2)) &&
 154      ((r1->y1==r2->y1) && (r1->y2==r2->y2))) ||
 155     (((r1->y2==r2->y1) || (r1->y1==r2->y2)) &&
 156      ((r1->x1==r2->x1) && (r1->x2==r2->x2)));
 157 }
 158
 159 rectangles
 160 disjoint_union (rectangles l, rectangle r) {
 161   if (is_nil (l)) return r;
 162   if (adjacent (l->item, r))
 163     return disjoint_union (l->next,
 164                            least_upper_bound (rectangles (l->item, r)));
 165   return rectangles (l->item, disjoint_union (l->next, r));
 166 }
 167
 168 rectangles
 169 operator | (rectangles l1, rectangles l2) {
 170   rectangles l (l1-l2);
 171   while (!is_nil (l2)) {
 172     l = disjoint_union (l, l2->item);
 173     l2= l2->next;
 174   }
 175   return l;
 176 }
 177
 178 rectangles
 179 translate (rectangles l, SI x, SI y) {
 180   if (is_nil (l)) return l;
 181   rectangle& r= l->item;
 182   return rectangles (rectangle (r->x1+ x, r->y1+ y, r->x2+ x, r->y2+ y),
 183                      translate (l->next, x, y));
 184 }
 185
 186 rectangles
 187 thicken (rectangles l, SI width, SI height) {
 188   if (is_nil (l)) return l;
 189   rectangle& r= l->item;
 190   return rectangles (rectangle (r->x1- width, r->y1- height,
 191                                 r->x2+ width, r->y2+ height),
 192                      thicken (l->next, width, height));
 193 }
 194
 195 rectangles
 196 outline (rectangles rs, SI pixel) {
 197   return simplify (correct (thicken (rs, pixel, 3*pixel) -
 198                             thicken (rs, 0, 2*pixel)));
 199 }
 200
 201 rectangles
 202 operator * (rectangles l, int d) {
 203   if (is_nil (l)) return l;
 204   return rectangles (l->item*d, l->next*d);
 205 }
 206
 207 rectangles
 208 operator / (rectangles l, int d) {
 209   if (is_nil (l)) return l;
 210   return rectangles (l->item/d, l->next/d);
 211 }
 212
 213 rectangles
 214 correct (rectangles l) {
 215   if (is_nil (l)) return l;
 216   if ((l->item->x1 >= l->item->x2) || (l->item->y1 >= l->item->y2))
 217     return correct (l->next);
 218   return rectangles (l->item, correct (l->next));
 219 }
 220
 221 rectangles
 222 simplify (rectangles l) {
 223   if (is_nil (l) || is_atom (l)) return l;
 224   return simplify (l->next) | rectangles (l->item);
 225 }
 226
 227 rectangle
 228 least_upper_bound (rectangles l) {
 229   ASSERT (!is_nil (l), "no rectangles in list");
 230   rectangle r1= copy (l->item);
 231   while (!is_nil (l->next)) {
 232     l= l->next;
 233     rectangle r2= l->item;
 234     r1->x1= min (r1->x1, r2->x1);
 235     r1->y1= min (r1->y1, r2->y1);
 236     r1->x2= max (r1->x2, r2->x2);
 237     r1->y2= max (r1->y2, r2->y2);
 238   }
 239   return r1;
 240 }
 241
 242 double
 243 area (rectangles r) {
 244   double sum= 0.0;
 245   while (!is_nil (r)) {
 246     sum += area (r->item);
 247     r= r->next;
 248   }
 249   return sum;
 250 }