4.3BSD - /usr/src/new/X/X/overlap.c

   1: #include <X/mit-copyright.h>
   2: 
   3: /* Copyright    Massachusetts Institute of Technology    1985	*/
   4: 
   5: /*	Routines to calculate how rectangles overlap and abut:
   6:  *
   7:  *	Calc_overlaps, Do_overlap,
   8:  *	Clip_raster, Clip_rectangle, Rec_intersection,
   9:  *	Merge_vertical, Merge_rectangles
  10:  */
  11: 
  12: #ifndef lint
  13: static char *rcsid_overlap_c = "$Header: overlap.c,v 10.6 86/02/01 15:16:58 tony Rel $";
  14: #endif
  15: 
  16: #include "Xint.h"
  17: 
  18: extern RECTANGLE *free_rectangles;
  19: 
  20: RECTANGLE **Do_overlap(), *Alloc_rectangle();
  21: 
  22: /* Calc_overlaps figures out how raster rast overlaps rectangles rects and
  23:  * recreates in rects a list of the maximally wide visible rectangles.
  24:  * It returns 0 if no overlap, 1 if overlap.
  25:  */
  26: 
  27: int Calc_overlaps (rast, rects)
  28:     register RASTER *rast;
  29:     register RECTANGLE **rects;
  30: {
  31:     register RECTANGLE *rbot, **prev;
  32:     int obscured;
  33: 
  34:     obscured = 0;
  35: 
  36:     prev = rects;
  37: 
  38:     /* Go through the bottom rectangles and see which are obscured */
  39: 
  40:     while (rbot = *prev) {
  41:         if (rast->left >= rbot->right || rbot->left >= rast->right ||
  42:         rast->top >= rbot->bottom || rbot->top >= rast->bottom) {
  43:         prev = &rbot->next;
  44:         } else {
  45:         prev = Do_overlap (rast, prev, rects);
  46:         FREERECT(rbot);
  47:         obscured = 1;
  48:         }
  49:     }
  50:     return (obscured);
  51: }
  52: 
  53: /* Do_overlap figures out how raster front overlaps rectangle *prev and
  54:  * replaces *prev in recs with a list of the maximally wide visible
  55:  * rectangles.  Returns an updated list pointer that points to *prev->next.
  56:  */
  57: 
  58: RECTANGLE **Do_overlap (front, prev, recs)
  59:     register RASTER *front;
  60:     register RECTANGLE **prev;
  61:     RECTANGLE **recs;
  62: {
  63:     register RECTANGLE *back, *r;
  64:     int overlap;
  65: 
  66:     back = *prev;
  67:     *prev = back->next;
  68:     overlap = 0;
  69:     if (front->right < back->right)     overlap += 8;
  70:     if (front->left > back->left)       overlap += 4;
  71:     if (front->bottom < back->bottom)   overlap += 2;
  72:     if (front->top > back->top)         overlap += 1;
  73: 
  74:     switch (overlap) {
  75:         case 0:     /* Top completely covers bottom */
  76:         goto done;
  77: 
  78:         /* In the next four cases the bottom shows in one rectangle. */
  79:         case 1:         /* Back peeks out on top */
  80:         NEWRECT(r, back->left, back->right,
  81:             back->top, front->top, back->type);
  82:         break;
  83:         case 2:         /* ...on bottom */
  84:         NEWRECT(r, back->left, back->right,
  85:             front->bottom, back->bottom, back->type);
  86:         break;
  87:         case 4:         /* ...on left */
  88:         NEWRECT(r, back->left, front->left,
  89:             back->top, back->bottom, back->type);
  90:         *prev = back;
  91:         if TRUE(Merge_vertical (r, recs, 1))
  92:             goto refind;
  93:         break;
  94:         case 8:         /* ...on right */
  95:         NEWRECT(r, front->right, back->right,
  96:             back->top, back->bottom, back->type);
  97:         *prev = back;
  98:         if TRUE(Merge_vertical (r, recs, 1))
  99:             goto refind;
 100:         break;
 101: 
 102:         /* Now we have the cases where there are 2 rectangles */
 103: 
 104:         case 3:         /* ...on top & bottom */
 105:         NEWRECT(r, back->left, back->right,
 106:             back->top, front->top, back->type);
 107:         *prev = r;
 108:         prev = &r->next;
 109:         NEWRECT(r, back->left, back->right,
 110:             front->bottom, back->bottom, back->type);
 111:         break;
 112:         case 5:         /* ...on top & left */
 113:         NEWRECT(r, back->left, back->right,
 114:             back->top, front->top, back->type);
 115:         r->next = *prev;
 116:         *prev = r;
 117:         prev = &r->next;
 118:         NEWRECT(r, back->left, front->left,
 119:             front->top, back->bottom, back->type);
 120:         if TRUE(Merge_vertical (r, recs, 0))
 121:             goto done;
 122:         break;
 123:         case 6:         /* ...on bottom & left */
 124:         NEWRECT(r, back->left, back->right,
 125:             front->bottom, back->bottom, back->type);
 126:         r->next = *prev;
 127:         *prev = r;
 128:         prev = &r->next;
 129:         NEWRECT(r, back->left, front->left,
 130:             back->top, front->bottom, back->type);
 131:         if TRUE(Merge_vertical (r, recs, 0))
 132:             goto done;
 133:         break;
 134:         case 9:         /* ...on top & right */
 135:         NEWRECT(r, back->left, back->right,
 136:             back->top, front->top, back->type);
 137:         r->next = *prev;
 138:         *prev = r;
 139:         prev = &r->next;
 140:         NEWRECT(r, front->right, back->right,
 141:             front->top, back->bottom, back->type);
 142:         if TRUE(Merge_vertical (r, recs, 0))
 143:             goto done;
 144:         break;
 145:         case 10:            /* ...on bottom & right */
 146:         NEWRECT(r, back->left, back->right,
 147:             front->bottom, back->bottom, back->type);
 148:         r->next = *prev;
 149:         *prev = r;
 150:         prev = &r->next;
 151:         NEWRECT(r, front->right, back->right,
 152:             back->top, front->bottom, back->type);
 153:         if TRUE(Merge_vertical (r, recs, 0))
 154:             goto done;
 155:         break;
 156:         case 12:            /* ...on left & right */
 157:         NEWRECT(r, back->left, front->left,
 158:             back->top, back->bottom, back->type);
 159:         *prev = back;
 160:         if TRUE(Merge_vertical (r, recs, 1)) {
 161:             /* refind insertion point */
 162:             prev = recs;
 163:             while ((r = *prev) != back)
 164:             prev = &r->next;
 165:             NEWRECT(r, front->right, back->right,
 166:                 back->top, back->bottom, back->type);
 167:             if TRUE(Merge_vertical (r, recs, 1))
 168:             goto refind;
 169:         } else {
 170:             r->next = back->next;
 171:             *prev = r;
 172:             prev = &r->next;
 173:             NEWRECT(r, front->right, back->right,
 174:                 back->top, back->bottom, back->type);
 175:             if TRUE(Merge_vertical (r, recs, 1))
 176:             goto done;
 177:         }
 178:         break;
 179: 
 180:         /* Now the cases where there are 3 rectangles */
 181: 
 182:         case 7:         /* ...top, bottom, & left */
 183:         NEWRECT(r, back->left, front->left,
 184:             front->top, front->bottom, back->type);
 185:         *prev = r;
 186:         prev = &r->next;
 187:         NEWRECT(r, back->left, back->right,
 188:             back->top, front->top, back->type);
 189:         *prev = r;
 190:         prev = &r->next;
 191:         NEWRECT(r, back->left, back->right,
 192:             front->bottom, back->bottom, back->type);
 193:         break;
 194:         case 11:            /* ...top, bottom, & right */
 195:         NEWRECT(r, front->right, back->right,
 196:             front->top, front->bottom, back->type);
 197:         *prev = r;
 198:         prev = &r->next;
 199:         NEWRECT(r, back->left, back->right,
 200:             back->top, front->top, back->type);
 201:         *prev = r;
 202:         prev = &r->next;
 203:         NEWRECT(r, back->left, back->right,
 204:             front->bottom, back->bottom, back->type);
 205:         break;
 206:         case 13:        /* ...top, left, & right */
 207:         NEWRECT(r, back->left, back->right,
 208:             back->top, front->top, back->type);
 209:         r->next = *prev;
 210:         *prev = r;
 211:         prev = &r->next;
 212:         NEWRECT(r, back->left, front->left,
 213:             front->top, back->bottom, back->type);
 214:         if FALSE(Merge_vertical (r, recs, 0)) {
 215:             r->next = *prev;
 216:             *prev = r;
 217:             prev = &r->next;
 218:         }
 219:         NEWRECT(r, front->right, back->right,
 220:             front->top, back->bottom, back->type);
 221:         if TRUE(Merge_vertical (r, recs, 0))
 222:             goto done;
 223:         break;
 224:         case 14:        /* ...left, right, & bottom */
 225:         NEWRECT(r, back->left, back->right,
 226:             front->bottom, back->bottom, back->type);
 227:         r->next = *prev;
 228:         *prev = r;
 229:         prev = &r->next;
 230:         NEWRECT(r, back->left, front->left,
 231:             back->top, front->bottom, back->type);
 232:         if FALSE(Merge_vertical (r, recs, 0)) {
 233:             r->next = *prev;
 234:             *prev = r;
 235:             prev = &r->next;
 236:         }
 237:         NEWRECT(r, front->right, back->right,
 238:             back->top, front->bottom, back->type);
 239:         if TRUE(Merge_vertical (r, recs, 0))
 240:             goto done;
 241:         break;
 242: 
 243:         /* And the case where there are 4 rectangles */
 244: 
 245:         case 15:        /* ...left, right, top, & bottom */
 246:         NEWRECT(r, back->left, back->right,
 247:             back->top, front->top, back->type);
 248:         *prev = r;
 249:         prev = &r->next;
 250:         NEWRECT(r, back->left, front->left,
 251:             front->top, front->bottom, back->type);
 252:         *prev = r;
 253:         prev = &r->next;
 254:         NEWRECT(r, front->right, back->right,
 255:             front->top, front->bottom, back->type);
 256:         *prev = r;
 257:         prev = &r->next;
 258:         NEWRECT(r, back->left, back->right,
 259:             front->bottom, back->bottom, back->type);
 260:         break;
 261:     }
 262:     r->next = back->next;
 263:     *prev = r;
 264:     return (&r->next);
 265: refind: /* refind insertion point */
 266:     prev = recs;
 267:     while ((r = *prev) != back)
 268:         prev = &r->next;
 269:     *prev = back->next;
 270: done:   return (prev);
 271: }
 272: 
 273: /* Clip_raster modifies raster1 so that it all fits in raster2.
 274:  */
 275: 
 276: Clip_raster (rast1, rast2)
 277:     register RASTER *rast1, *rast2;
 278: {
 279:     if (rast1->right > rast2->right)
 280:         rast1->right = rast2->right;
 281:     if (rast1->left < rast2->left)
 282:         rast1->left = rast2->left;
 283:     if (rast1->bottom > rast2->bottom)
 284:         rast1->bottom = rast2->bottom;
 285:     if (rast1->top < rast2->top)
 286:         rast1->top = rast2->top;
 287:     if (rast1->left >= rast1->right ||
 288:         rast1->top >= rast1->bottom) {
 289:         rast1->right = rast1->left;
 290:         rast1->bottom = rast1->top;
 291:     }
 292: }
 293: 
 294: /* Rec_intersection returns a rectangle which is the intersection of its
 295:  * 2 arguments.  If they don't interesect, it returns NULL.
 296:  */
 297: 
 298: RECTANGLE *Rec_intersection (rec1, rec2)
 299:     register RECTANGLE *rec1, *rec2;
 300: {
 301:     register int l, r, t, b;
 302: 
 303:     l = max(rec1->left, rec2->left);
 304:     r = min(rec1->right, rec2->right);
 305:     t = max(rec1->top, rec2->top);
 306:     b = min(rec1->bottom, rec2->bottom);
 307:     if (l >= r || t >= b)
 308:         return (NULL);
 309:     NEWRECT(rec1, l, r, t, b, new_rec);
 310:     return (rec1);
 311: }
 312: 
 313: /* Clips a rectangle to fit in a raster.  Returns 0 if part of the rectangle
 314:  * is inside, else frees the rectangle and returns 1.
 315:  */
 316: 
 317: int Clip_rectangle (rect, rast)
 318:     register RECTANGLE *rect;
 319:     register RASTER *rast;
 320: {
 321:     if (rect->left < rast->left)
 322:         rect->left = rast->left;
 323:     if (rect->right > rast->right)
 324:         rect->right = rast->right;
 325:     if (rect->top < rast->top)
 326:         rect->top = rast->top;
 327:     if (rect->bottom > rast->bottom)
 328:         rect->bottom = rast->bottom;
 329: 
 330:     if (rect->left < rect->right &&
 331:         rect->top < rect->bottom)
 332:         return (0);
 333:     FREERECT(rect);
 334:     return (1);
 335: }
 336: 
 337: /* Merge_vertical tries to find a rectangle in the list that abuts above or
 338:  * below with rec, and merges rec into it.  If bothsides is non-zero, the
 339:  * merge might allow a further merge with an existing rectangle in the list,
 340:  * and if so, the earlier rectangle is merged into the later rectangle in
 341:  * the list.  Returns 1 if a merge was made, else 0.
 342:  */
 343: 
 344: Merge_vertical (rec, list, bothsides)
 345:     register RECTANGLE *rec, **list;
 346:     int bothsides;
 347: {
 348:     register RECTANGLE *r;
 349: 
 350:     r = *list;
 351:     while (1) {
 352:         if (r->type == rec->type &&
 353:         r->left == rec->left && r->right == rec->right) {
 354:         if (r->top == rec->bottom) {
 355:             r->top = rec->top;
 356:             FREERECT(rec);
 357:             if FALSE(bothsides)
 358:             return (1);
 359:             break;
 360:         } else if (r->bottom == rec->top) {
 361:             r->bottom = rec->bottom;
 362:             FREERECT(rec);
 363:             if FALSE(bothsides)
 364:             return (1);
 365:             break;
 366:         }
 367:         }
 368:         if ((r = r->next) == NULL)
 369:         return (0);
 370:     }
 371:     rec = r;
 372:     while (r = r->next) {
 373:         if (r->type == rec->type &&
 374:         r->left == rec->left && r->right == rec->right) {
 375:         if (r->top == rec->bottom)
 376:             r->top = rec->top;
 377:         else if (r->bottom == rec->top)
 378:             r->bottom = rec->bottom;
 379:         else
 380:             continue;
 381:         while ((r = *list) != rec)
 382:             list = &r->next;
 383:         *list = rec->next;
 384:         FREERECT(rec);
 385:         return (1);
 386:         }
 387:     }
 388:     return (1);
 389: }
 390: 
 391: /* Merge_rectangles merges one list of rectangles into another.  It may also
 392:  * resize rectangles to get wide rather than tall rectangles.  It makes
 393:  * multiple passes since doing some merges may enable others to be made.
 394:  * Since the lists might be long, you would think sorting would help, but
 395:  * sorting actually seems to run slower.
 396:  */
 397: 
 398: Merge_rectangles (r1, recs)
 399:     register RECTANGLE *r1, **recs;
 400: {
 401:     register RECTANGLE *r2, **prev;
 402: 
 403:     while (1) {
 404:         prev = recs;
 405:         while (r2 = *prev) {
 406:         if (r1->type != r2->type) {
 407:             prev = &r2->next;
 408:             continue;
 409:         }
 410:         if (r1->top == r2->top) {
 411:             if (r1->right == r2->left) {
 412:             if (r1->bottom == r2->bottom) {
 413:                 r1->right = r2->right;
 414:                 goto free;
 415:             } else if (r1->bottom < r2->bottom) {
 416:                 r1->right = r2->right;
 417:                 r2->top = r1->bottom;
 418:                 goto remerge;
 419:             } else {
 420:                 r1->top = r2->bottom;
 421:                 r2->left = r1->left;
 422:                 goto remerge;
 423:             }
 424:             } else if (r1->left == r2->right) {
 425:             if (r1->bottom == r2->bottom) {
 426:                 r1->left = r2->left;
 427:                 goto free;
 428:             } else if (r1->bottom < r2->bottom) {
 429:                 r1->left = r2->left;
 430:                 r2->top = r1->bottom;
 431:                 goto remerge;
 432:             } else {
 433:                 r1->top = r2->bottom;
 434:                 r2->right = r1->right;
 435:                 goto remerge;
 436:             }
 437:             }
 438:         } else if (r1->bottom == r2->bottom) {
 439:             if (r1->right == r2->left) {
 440:             if (r1->top < r2->top) {
 441:                 r2->left = r1->left;
 442:                 r1->bottom = r2->top;
 443:                 goto remerge;
 444:             } else {
 445:                 r1->right = r2->right;
 446:                 r2->bottom = r1->top;
 447:                 goto remerge;
 448:             }
 449:             } else if (r1->left == r2->right) {
 450:             if (r1->top < r2->top) {
 451:                 r2->right = r1->right;
 452:                 r1->bottom = r2->top;
 453:                 goto remerge;
 454:             } else {
 455:                 r1->left = r2->left;
 456:                 r2->bottom = r1->top;
 457:                 goto remerge;
 458:             }
 459:             }
 460:         } else if (r1->left == r2->left && r1->right == r2->right) {
 461:             if (r1->bottom == r2->top) {
 462:             r1->bottom = r2->bottom;
 463:             goto free;
 464:             } else if (r1->top == r2->bottom) {
 465:             r1->top = r2->top;
 466:             goto free;
 467:             }
 468:         }
 469:         prev = &r2->next;
 470:         continue;
 471: 
 472: free:       *prev = r2->next;
 473:         FREERECT(r2);
 474:         prev = recs;
 475:         continue;
 476: 
 477: remerge:    *prev = r2->next;
 478:         r2->next = r1;
 479:         r1 = r2;
 480:         prev = recs;
 481:         }
 482:         *prev = r1;
 483:         if ((r2 = r1->next) == NULL)
 484:         return;
 485:         r1->next = NULL;
 486:         r1 = r2;
 487:     }
 488: }

Defined functions

Defined variables