Back to index

texmacs  1.0.7.15
rectangles.cpp
Go to the documentation of this file.
00001 
00002 /******************************************************************************
00003 * MODULE     : rectangles.cpp
00004 * DESCRIPTION: Rectangles and lists of rectangles with reference counting.
00005 *              Used in graphical programs.
00006 * COPYRIGHT  : (C) 1999  Joris van der Hoeven
00007 *******************************************************************************
00008 * This software falls under the GNU general public license version 3 or later.
00009 * It comes WITHOUT ANY WARRANTY WHATSOEVER. For details, see the file LICENSE
00010 * in the root directory or <http://www.gnu.org/licenses/gpl-3.0.html>.
00011 ******************************************************************************/
00012 
00013 #include "rectangles.hpp"
00014 
00015 /******************************************************************************
00016 * Routines for rectangles
00017 ******************************************************************************/
00018 
00019 rectangle_rep::rectangle_rep (SI x1b, SI y1b, SI x2b, SI y2b):
00020   x1 (x1b), y1 (y1b), x2 (x2b), y2 (y2b) { }
00021 
00022 rectangle::rectangle (SI x1b, SI y1b, SI x2b, SI y2b):
00023   rep (tm_new<rectangle_rep> (x1b, y1b, x2b, y2b)) { }
00024 
00025 rectangle::operator tree () {
00026   return tree (TUPLE,
00027               as_string (rep->x1), as_string (rep->y1),
00028               as_string (rep->x2), as_string (rep->y2));
00029 }
00030 
00031 tm_ostream&
00032 operator << (tm_ostream& out, rectangle r) {
00033   out << "rectangle ("
00034       << r->x1 << ", " << r->y1 << ", "
00035       << r->x2 << ", " << r->y2 << ")";
00036   return out;
00037 }
00038 
00039 rectangle
00040 copy (rectangle r) {
00041   return rectangle (r->x1, r->y1, r->x2, r->y2);
00042 }
00043 
00044 bool
00045 operator == (rectangle r1, rectangle r2) {
00046   return
00047     (r1->x1==r2->x1) && (r1->y1==r2->y1) &&
00048     (r1->x2==r2->x2) && (r1->y2==r2->y2);
00049 }
00050 
00051 bool
00052 operator != (rectangle r1, rectangle r2) {
00053   return
00054     (r1->x1!=r2->x1) || (r1->y1!=r2->y1) ||
00055     (r1->x2!=r2->x2) || (r1->y2!=r2->y2);
00056 }
00057 
00058 bool
00059 operator <= (rectangle r1, rectangle r2) {
00060   return
00061     (r1->x1>=r2->x1) && (r1->x2<=r2->x2) &&
00062     (r1->y1>=r2->y1) && (r1->y2<=r2->y2);
00063 }
00064 
00065 bool
00066 intersect (rectangle r1, rectangle r2) {
00067   return
00068     (r1->x1<r2->x2) && (r1->x2>r2->x1) &&
00069     (r1->y1<r2->y2) && (r1->y2>r2->y1);
00070 }
00071 
00072 rectangle
00073 translate (rectangle r, SI x, SI y) {
00074   return rectangle (r->x1+x, r->y1+y, r->x2+x, r->y2+y);
00075 }
00076 
00077 double
00078 area (rectangle r) {
00079   double w= max (r->x2 - r->x1, 0);
00080   double h= max (r->y2 - r->y1, 0);
00081   return w*h;
00082 }
00083 
00084 /******************************************************************************
00085 * Miscellaneous subroutines
00086 ******************************************************************************/
00087 
00088 // FIXME: Why do we need this? Compiler bug?
00089 #define min(x,y) ((x)<=(y)?(x):(y))
00090 #define max(x,y) ((x)<=(y)?(y):(x))
00091 
00092 void
00093 complement (rectangle r1, rectangle r2, rectangles& l) {
00094   if (!intersect (r1, r2)) { r1 >> l; return; }
00095   if (r1->x1 < r2->x1) rectangle (r1->x1, r1->y1, r2->x1, r1->y2) >> l;
00096   if (r1->x2 > r2->x2) rectangle (r2->x2, r1->y1, r1->x2, r1->y2) >> l;
00097   if (r1->y1 < r2->y1) rectangle (max (r1->x1, r2->x1), r1->y1,
00098                               min (r1->x2, r2->x2), r2->y1) >> l;
00099   if (r1->y2 > r2->y2) rectangle (max (r1->x1, r2->x1), r2->y2,
00100                               min (r1->x2, r2->x2), r1->y2) >> l;
00101 }
00102 
00103 void
00104 complement (rectangles l1, rectangle r2, rectangles& l) {
00105   for (; !is_nil (l1); l1= l1->next)
00106     complement (l1->item, r2, l);
00107 }
00108 
00109 void
00110 intersection (rectangle r1, rectangle r2, rectangles& l) {
00111   if (!intersect (r1, r2)) return;
00112   rectangle (max (r1->x1, r2->x1), max (r1->y1, r2->y1),
00113             min (r1->x2, r2->x2), min (r1->y2, r2->y2)) >> l;
00114 }
00115 
00116 rectangle
00117 operator * (rectangle r, int d) {
00118   return rectangle (r->x1*d, r->y1*d, r->x2*d, r->y2*d);
00119 }
00120 
00121 rectangle
00122 operator / (rectangle r, int d) {
00123   return rectangle (r->x1/d, r->y1/d, r->x2/d, r->y2/d);
00124 }
00125 
00126 /******************************************************************************
00127 * Exported routines for rectangles
00128 ******************************************************************************/
00129 
00130 rectangles
00131 operator - (rectangles l1, rectangles l2) {
00132   rectangles a=l1;
00133   for (; !is_nil (l2); l2= l2->next) {
00134     rectangles b;
00135     complement (a, l2->item, b);
00136     a=b;
00137   }
00138   return a;
00139 }
00140 
00141 rectangles
00142 operator & (rectangles l1, rectangles l2) {
00143   rectangles l, lc1, lc2;
00144   for (lc1= l1; !is_nil (lc1); lc1= lc1->next)
00145     for (lc2= l2; !is_nil (lc2); lc2= lc2->next)
00146       intersection (lc1->item, lc2->item, l);
00147   return l;
00148 }
00149 
00150 bool
00151 adjacent (rectangle r1, rectangle r2) {
00152   return
00153     (((r1->x2==r2->x1) || (r1->x1==r2->x2)) &&
00154      ((r1->y1==r2->y1) && (r1->y2==r2->y2))) ||
00155     (((r1->y2==r2->y1) || (r1->y1==r2->y2)) &&
00156      ((r1->x1==r2->x1) && (r1->x2==r2->x2)));
00157 }
00158 
00159 rectangles
00160 disjoint_union (rectangles l, rectangle r) {
00161   if (is_nil (l)) return r;
00162   if (adjacent (l->item, r))
00163     return disjoint_union (l->next,
00164                         least_upper_bound (rectangles (l->item, r)));
00165   return rectangles (l->item, disjoint_union (l->next, r));
00166 }
00167 
00168 rectangles
00169 operator | (rectangles l1, rectangles l2) {
00170   rectangles l (l1-l2);
00171   while (!is_nil (l2)) {
00172     l = disjoint_union (l, l2->item);
00173     l2= l2->next;
00174   }
00175   return l;
00176 }
00177 
00178 rectangles
00179 translate (rectangles l, SI x, SI y) {
00180   if (is_nil (l)) return l;
00181   rectangle& r= l->item;
00182   return rectangles (rectangle (r->x1+ x, r->y1+ y, r->x2+ x, r->y2+ y),
00183                    translate (l->next, x, y));
00184 }
00185 
00186 rectangles
00187 thicken (rectangles l, SI width, SI height) {
00188   if (is_nil (l)) return l;
00189   rectangle& r= l->item;
00190   return rectangles (rectangle (r->x1- width, r->y1- height,
00191                             r->x2+ width, r->y2+ height),
00192                    thicken (l->next, width, height));
00193 }
00194 
00195 rectangles
00196 outline (rectangles rs, SI pixel) {
00197   return simplify (correct (thicken (rs, pixel, 3*pixel) -
00198                          thicken (rs, 0, 2*pixel)));
00199 }
00200 
00201 rectangles
00202 operator * (rectangles l, int d) {
00203   if (is_nil (l)) return l;
00204   return rectangles (l->item*d, l->next*d);
00205 }
00206 
00207 rectangles
00208 operator / (rectangles l, int d) {
00209   if (is_nil (l)) return l;
00210   return rectangles (l->item/d, l->next/d);
00211 }
00212 
00213 rectangles
00214 correct (rectangles l) {
00215   if (is_nil (l)) return l;
00216   if ((l->item->x1 >= l->item->x2) || (l->item->y1 >= l->item->y2))
00217     return correct (l->next);
00218   return rectangles (l->item, correct (l->next));
00219 }
00220 
00221 rectangles
00222 simplify (rectangles l) {
00223   if (is_nil (l) || is_atom (l)) return l;
00224   return simplify (l->next) | rectangles (l->item);
00225 }
00226 
00227 rectangle
00228 least_upper_bound (rectangles l) {
00229   ASSERT (!is_nil (l), "no rectangles in list");
00230   rectangle r1= copy (l->item);
00231   while (!is_nil (l->next)) {
00232     l= l->next;
00233     rectangle r2= l->item;
00234     r1->x1= min (r1->x1, r2->x1);
00235     r1->y1= min (r1->y1, r2->y1);
00236     r1->x2= max (r1->x2, r2->x2);
00237     r1->y2= max (r1->y2, r2->y2);
00238   }
00239   return r1;
00240 }
00241 
00242 double
00243 area (rectangles r) {
00244   double sum= 0.0;
00245   while (!is_nil (r)) {
00246     sum += area (r->item);
00247     r= r->next;
00248   }
00249   return sum;
00250 }