```   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

Clip_raster defined in line 276; used 5 times
Clip_rectangle defined in line 317; used 4 times
Do_overlap defined in line 58; used 6 times
Merge_vertical defined in line 344; used 19 times
Rec_intersection defined in line 298; used 4 times

#### Defined variables

rcsid_overlap_c defined in line 13; never used
 Last modified: 1986-02-01 Generated: 2016-12-26 Generated by src2html V0.67 page hit count: 1566