1 /* geometry.c --
2 *
3 * *********************************************************************
4 * * Copyright (C) 1985, 1990 Regents of the University of California. *
5 * * Permission to use, copy, modify, and distribute this *
6 * * software and its documentation for any purpose and without *
7 * * fee is hereby granted, provided that the above copyright *
8 * * notice appear in all copies. The University of California *
9 * * makes no representations about the suitability of this *
10 * * software for any purpose. It is provided "as is" without *
11 * * express or implied warranty. Export of this software outside *
12 * * of the United States of America may require an export license. *
13 * *********************************************************************
14 *
15 * This file contains a bunch of utility routines for manipulating
16 * boxes, points, and transforms.
17 */
18
19 #ifndef lint
20 static char rcsid[] __attribute__ ((unused)) = "$Header: /usr/cvsroot/magic-8.0/utils/geometry.c,v 1.5 2008/12/11 14:11:46 tim Exp $";
21 #endif /* not lint */
22
23 #include <stdio.h>
24 #include <math.h> /* For atan2() function */
25
26 #include "utils/magic.h"
27 #include "utils/geometry.h"
28 #include "utils/utils.h"
29 #include "textio/textio.h"
30
31 #include "tiles/tile.h" /* test only! */
32
33 /*
34 *-------------------------------------------------------------------
35 * Declarations of exported transforms:
36 *-------------------------------------------------------------------
37 */
38
39 global Transform GeoIdentityTransform = { 1, 0, 0, 0, 1, 0 };
40 global Transform GeoUpsideDownTransform = { 1, 0, 0, 0, -1, 0 };
41 global Transform GeoSidewaysTransform = { -1, 0, 0, 0, 1, 0 };
42 global Transform Geo90Transform = { 0, 1, 0, -1, 0, 0 };
43 global Transform Geo180Transform = { -1, 0, 0, 0, -1, 0 };
44 global Transform Geo270Transform = { 0, -1, 0, 1, 0, 0 };
45
46 /*
47 * Additional Transforms (Reflections at 45 and 135 degrees)
48 */
49
50 global Transform GeoRef45Transform = { 0, 1, 0, 1, 0, 0 };
51 global Transform GeoRef135Transform = { 0, -1, 0, -1, 0, 0 };
52
53 /*
54 *-------------------------------------------------------------------
55 * Declaration of the table of opposite directions:
56 *-------------------------------------------------------------------
57 */
58 global int GeoOppositePos[] =
59 {
60 GEO_CENTER, /* GEO_CENTER */
61 GEO_SOUTH, /* GEO_NORTH */
62 GEO_SOUTHWEST, /* GEO_NORTHEAST */
63 GEO_WEST, /* GEO_EAST */
64 GEO_NORTHWEST, /* GEO_SOUTHEAST */
65 GEO_NORTH, /* GEO_SOUTH */
66 GEO_NORTHEAST, /* GEO_SOUTHWEST */
67 GEO_EAST, /* GEO_WEST */
68 GEO_SOUTHEAST, /* GEO_NORTHWEST */
69 };
70
71 /*
72 *-------------------------------------------------------------------
73 * Declarations of exported variables:
74 *-------------------------------------------------------------------
75 */
76
77 global Rect GeoNullRect = { 0, 0, 0, 0 };
78 global Rect GeoInvertedRect = { 0, 0, -1, -1 };
79 global Point GeoOrigin = { 0, 0 };
80
81
82 /*-------------------------------------------------------------------
83 * GeoTransPoint --
84 * Transforms a point from one coordinate system to another.
85 *
86 * Results: None.
87 *
88 * Side Effects:
89 * P2 is set to contain the coordinates that result from transforming
90 * p1 by t.
91 *-------------------------------------------------------------------
92 */
93
94 void
GeoTransPoint(t,p1,p2)95 GeoTransPoint(t, p1, p2)
96 Transform *t; /* A description of the mapping from the
97 * coordinate system of p1 to that of p2.
98 */
99 Point *p1, *p2; /* Pointers to two points; p1 is the old
100 * point, and p2 will contain the transformed
101 * point.
102 */
103
104 {
105 p2->p_x = p1->p_x*t->t_a + p1->p_y*t->t_b + t->t_c;
106 p2->p_y = p1->p_x*t->t_d + p1->p_y*t->t_e + t->t_f;
107 }
108
109 /*
110 *-------------------------------------------------------------------
111 *
112 * GeoTransPointDelta --
113 *
114 * Transforms a point from one coordinate system to another. This
115 * differs from GeoTransPoint in that translation is ignored. It
116 * applies flips and rotations, and so is appropriate to calculate
117 * how an offset value (delta distance) transforms through the
118 * hierarchy.
119 *
120 * Results:
121 * None.
122 *
123 * Side Effects:
124 * P2 is set to contain the coordinates that result from transforming
125 * p1 by t.
126 *-------------------------------------------------------------------
127 */
128 void
GeoTransPointDelta(t,p1,p2)129 GeoTransPointDelta(t, p1, p2)
130 Transform *t; /* A description of the mapping from the
131 * coordinate system of p1 to that of p2.
132 */
133 Point *p1, *p2; /* Pointers to two points; p1 is the old
134 * point, and p2 will contain the transformed
135 * point.
136 */
137
138 {
139 p2->p_x = p1->p_x * t->t_a + p1->p_y * t->t_b;
140 p2->p_y = p1->p_x * t->t_d + p1->p_y * t->t_e;
141 }
142
143 /*
144 *-------------------------------------------------------------------
145 * Determine how an angle changes through transformation via a
146 * tranformation matrix. Expects the transformations to be in
147 * multiples of 90 degrees, plus possible flipping. Expects an
148 * angle between 0 and 360 and returns an angle between 0 and
149 * 360.
150 *-------------------------------------------------------------------
151 */
152
153 int
GeoTransAngle(t,a)154 GeoTransAngle(t, a)
155 Transform *t; /* Transformation matrix */
156 int a; /* Angle to transform */
157 {
158 bool flip = FALSE;
159 int asave = a;
160
161 /* Rotate according to the standard transforms */
162
163 if (t->t_a == 0 && t->t_e == 0)
164 {
165 if (t->t_b > 0)
166 a += 90;
167 else
168 a += 270;
169 if (t->t_b == t->t_d)
170 flip = TRUE;
171 }
172 else
173 {
174 if (t->t_a < 0)
175 a += 180;
176 if (t->t_a != t->t_e)
177 flip = TRUE;
178 }
179 if (a > 360) a -= 360;
180 if (flip)
181 {
182 if (asave > 90 && asave < 270)
183 a = 360 - a;
184 else
185 a = -a;
186 }
187 if (a < 0) a += 360;
188 return a;
189 }
190
191
192 /*-------------------------------------------------------------------
193 * GeoTransRect --
194 * Transforms a rectangle from one coordinate system to another.
195 *
196 * Results: None.
197 *
198 * Side Effects:
199 * R2 is set to contain the coordinates that result from transforming
200 * r1 by t.
201 *-------------------------------------------------------------------
202 */
203
204 void
GeoTransRect(t,r1,r2)205 GeoTransRect(t, r1, r2)
206 Transform *t; /* A description of the mapping from the
207 * coordinate system of r1 to that of r2.
208 */
209 Rect *r1, *r2; /* Pointers to two rectangles, r1 is the old
210 * rectangle, r2 will contain the transformed
211 * rectangle.
212 */
213
214 {
215 int x1, y1, x2, y2;
216 x1 = r1->r_xbot*t->t_a + r1->r_ybot*t->t_b + t->t_c;
217 y1 = r1->r_xbot*t->t_d + r1->r_ybot*t->t_e + t->t_f;
218 x2 = r1->r_xtop*t->t_a + r1->r_ytop*t->t_b + t->t_c;
219 y2 = r1->r_xtop*t->t_d + r1->r_ytop*t->t_e + t->t_f;
220
221 /* Because of rotations, xbot and xtop may have to be switched, and
222 * the same for ybot and ytop.
223 */
224
225 if (x1 < x2)
226 {
227 r2->r_xbot = x1;
228 r2->r_xtop = x2;
229 }
230 else
231 {
232 r2->r_xbot = x2;
233 r2->r_xtop = x1;
234 }
235 if (y1 < y2)
236 {
237 r2->r_ybot = y1;
238 r2->r_ytop = y2;
239 }
240 else
241 {
242 r2->r_ybot = y2;
243 r2->r_ytop = y1;
244 }
245 }
246
247 /*-------------------------------------------------------------------
248 * GeoTranslateTrans --
249 * Translate a transform by the indicated (x, y) amount.
250 *
251 * Results: None.
252 *
253 * Side Effects:
254 * Trans2 is set to the result of transforming trans1 by
255 * a translation of (x, y).
256 *-------------------------------------------------------------------
257 */
258
259 void
GeoTranslateTrans(trans1,x,y,trans2)260 GeoTranslateTrans(trans1, x, y, trans2)
261 Transform *trans1; /* Transform to be translated */
262 int x, y; /* Amount by which to translated */
263 Transform *trans2; /* Result transform */
264 {
265 trans2->t_a = trans1->t_a;
266 trans2->t_b = trans1->t_b;
267 trans2->t_d = trans1->t_d;
268 trans2->t_e = trans1->t_e;
269
270 trans2->t_c = trans1->t_c + x;
271 trans2->t_f = trans1->t_f + y;
272 }
273
274 /*-------------------------------------------------------------------
275 * GeoTransTranslate --
276 * Transform a translation by the indicated (x, y) amount.
277 *
278 * This is the dual of GeoTranslateTrans, in that if
279 * Tinv is the inverse of T,
280 *
281 * GeoTransTranslate(T, x, y) * GeoTranslateTrans(Tinv, -x, -y)
282 * is the identity transform.
283 *
284 * Results: None.
285 *
286 * Side Effects:
287 * Trans2 is set to the result of transforming a translation
288 * of (x, y) by trans1.
289 *-------------------------------------------------------------------
290 */
291
292 void
GeoTransTranslate(x,y,trans1,trans2)293 GeoTransTranslate(x, y, trans1, trans2)
294 int x, y; /* Amount of translation */
295 Transform *trans1; /* Transform to be applied to translation */
296 Transform *trans2; /* Result transform */
297 {
298 trans2->t_a = trans1->t_a;
299 trans2->t_b = trans1->t_b;
300 trans2->t_d = trans1->t_d;
301 trans2->t_e = trans1->t_e;
302
303 trans2->t_c = x*trans1->t_a + y*trans1->t_b + trans1->t_c;
304 trans2->t_f = x*trans1->t_d + y*trans1->t_e + trans1->t_f;
305 }
306
307
308 /*-------------------------------------------------------------------
309 * GeoTransTrans --
310 * This routine transforms a transform.
311 *
312 * Results: None.
313 *
314 * Side Effects:
315 * The transform referred to by net is set to produce a geometrical
316 * transformation equivalent in effect to the application of transform
317 * first, followed by the application of transform second.
318 *-------------------------------------------------------------------
319 */
320
321 void
GeoTransTrans(first,second,net)322 GeoTransTrans(first, second, net)
323 Transform *first; /* Pointers to three transforms */
324 Transform *second;
325 Transform *net;
326 {
327 net->t_a = first->t_a*second->t_a + first->t_d*second->t_b;
328 net->t_b = first->t_b*second->t_a + first->t_e*second->t_b;
329 net->t_c = first->t_c*second->t_a + first->t_f*second->t_b + second->t_c;
330 net->t_d = first->t_a*second->t_d + first->t_d*second->t_e;
331 net->t_e = first->t_b*second->t_d + first->t_e*second->t_e;
332 net->t_f = first->t_c*second->t_d + first->t_f*second->t_e + second->t_f;
333 }
334
335
336 /*-------------------------------------------------------------------
337 * GeoNameToPos --
338 * Map the name of a position into an integer position parameter.
339 * Position names may be unique abbreviations for direction names.
340 *
341 * Results:
342 * Returns a position parameter (0 - 8, corresponding to GEO_CENTER
343 * through GEO_NORTHWEST), -1 if the position name was ambiguous,
344 * and -2 if it was unrecognized.
345 *
346 * Side Effects: None.
347 *-------------------------------------------------------------------
348 */
349
350 int
GeoNameToPos(name,manhattan,verbose)351 GeoNameToPos(name, manhattan, verbose)
352 char *name;
353 bool manhattan; /* If TRUE, only Manhattan directions (up, down,
354 * left, right, and their synonyms) are allowed.
355 */
356 bool verbose; /* If TRUE, we print an error message and list
357 * valid directions.
358 */
359 {
360 static struct pos
361 {
362 char *pos_name;
363 int pos_value;
364 bool pos_manhattan;
365 }
366 positions[] =
367 {
368 "bl", GEO_SOUTHWEST, FALSE,
369 "bottom", GEO_SOUTH, TRUE,
370 "br", GEO_SOUTHEAST, FALSE,
371 "center", GEO_CENTER, FALSE,
372 "d", GEO_SOUTH, TRUE,
373 "dl", GEO_SOUTHWEST, FALSE,
374 "down", GEO_SOUTH, TRUE,
375 "dr", GEO_SOUTHEAST, FALSE,
376 "e", GEO_EAST, TRUE,
377 "east", GEO_EAST, TRUE,
378 "left", GEO_WEST, TRUE,
379 "n", GEO_NORTH, TRUE,
380 "ne", GEO_NORTHEAST, FALSE,
381 "north", GEO_NORTH, TRUE,
382 "northeast", GEO_NORTHEAST, FALSE,
383 "northwest", GEO_NORTHWEST, FALSE,
384 "nw", GEO_NORTHWEST, FALSE,
385 "right", GEO_EAST, TRUE,
386 "s", GEO_SOUTH, TRUE,
387 "se", GEO_SOUTHEAST, FALSE,
388 "south", GEO_SOUTH, TRUE,
389 "southeast", GEO_SOUTHEAST, FALSE,
390 "southwest", GEO_SOUTHWEST, FALSE,
391 "sw", GEO_SOUTHWEST, FALSE,
392 "tl", GEO_NORTHWEST, FALSE,
393 "top", GEO_NORTH, TRUE,
394 "tr", GEO_NORTHEAST, FALSE,
395 "u", GEO_NORTH, TRUE,
396 "ul", GEO_NORTHWEST, FALSE,
397 "up", GEO_NORTH, TRUE,
398 "ur", GEO_NORTHEAST, FALSE,
399 "w", GEO_WEST, TRUE,
400 "west", GEO_WEST, TRUE,
401 0
402 };
403 struct pos *pp;
404 char *fmt;
405 int pos;
406
407 pos = LookupStruct(name, (LookupTable *) positions, sizeof positions[0]);
408
409 if ((pos >= 0) && (!manhattan || positions[pos].pos_manhattan))
410 return positions[pos].pos_value;
411 if (!verbose)
412 {
413 if (pos < 0) return pos;
414 else return -2;
415 }
416 if (pos < 0)
417 {
418 switch (pos)
419 {
420 case -1:
421 TxError("\"%s\" is ambiguous.\n", name);
422 break;
423 case -2:
424 TxError("\"%s\" is not a valid direction or position.\n",
425 name);
426 break;
427 }
428 }
429 else
430 {
431 TxError("\"%s\" is not a Manhattan direction or position.\n", name);
432 pos = -2;
433 }
434 TxError("Legal directions/positions are:\n\t");
435 for (fmt = "%s", pp = positions; pp->pos_name; pp++)
436 {
437 if (manhattan && !pp->pos_manhattan)
438 continue;
439 TxError(fmt, pp->pos_name);
440 fmt = ",%s";
441 }
442 TxError("\n");
443 return (pos);
444 }
445
446
447 /*
448 * ----------------------------------------------------------------------------
449 *
450 * GeoPosToName --
451 *
452 * Given a geometric name, return its position name.
453 *
454 * Results:
455 * Pointer to a static string holding the position name.
456 * NOTE: you'd better not try to alter the returned string!
457 *
458 * Side effects:
459 * None.
460 *
461 * ----------------------------------------------------------------------------
462 */
463 char *
GeoPosToName(pos)464 GeoPosToName(pos)
465 int pos;
466 {
467 switch(pos)
468 {
469 case GEO_CENTER: return("CENTER");
470 case GEO_NORTH: return("NORTH");
471 case GEO_NORTHEAST: return("NORTHEAST");
472 case GEO_EAST: return("EAST");
473 case GEO_SOUTHEAST: return("SOUTHEAST");
474 case GEO_SOUTH: return("SOUTH");
475 case GEO_SOUTHWEST: return("SOUTHWEST");
476 case GEO_WEST: return("WEST");
477 case GEO_NORTHWEST: return("NORTHWEST");
478 default: return("*ILLEGAL*");
479 }
480 }
481
482 /*-------------------------------------------------------------------
483 * GeoTransPos --
484 * This routine computes the transform of a relative position.
485 *
486 * Results:
487 * The return value is a position equal to the position parameter
488 * transformed by t.
489 *
490 * Side Effects: None.
491 *-------------------------------------------------------------------
492 */
493
494 int
GeoTransPos(t,pos)495 GeoTransPos(t, pos)
496 Transform *t; /* Transform to be applied. */
497 int pos; /* Position to which it is to be applied. */
498
499 {
500 if ((pos <= 0) || (pos > 8)) return pos;
501
502 /* Handle rotation first, using modulo arithmetic. */
503
504 pos -= 1;
505 if (t->t_a <= 0)
506 {
507 if (t->t_a < 0) pos += 4;
508 else if (t->t_b < 0) pos += 6;
509 else pos += 2;
510 }
511 while (pos >= 8) pos -= 8;
512 pos += 1;
513
514 /* Handle mirroring across the x-axis on a case-by-case basis. */
515
516 if ((t->t_a != t->t_e) || ((t->t_a == 0) && (t->t_b == t->t_d)))
517 {
518 switch (pos)
519 {
520 case GEO_NORTH: pos = GEO_SOUTH; break;
521 case GEO_NORTHEAST: pos = GEO_SOUTHEAST; break;
522 case GEO_EAST: break;
523 case GEO_SOUTHEAST: pos = GEO_NORTHEAST; break;
524 case GEO_SOUTH: pos = GEO_NORTH; break;
525 case GEO_SOUTHWEST: pos = GEO_NORTHWEST; break;
526 case GEO_WEST: break;
527 case GEO_NORTHWEST: pos = GEO_SOUTHWEST; break;
528 }
529 }
530 return pos;
531 }
532
533 /*-------------------------------------------------------------------
534 * GeoTransOrient --
535 * This routine returns the orientation corresponding to a transform.
536 *
537 * Results:
538 * The return value is an orientation as defined by the enumeration
539 * below (which is also used by the LEF read routine). It has to
540 * agree with the enumeration used by dbOrientUseFunc.
541 *
542 * Side Effects: None.
543 *-------------------------------------------------------------------
544 */
545
546 enum def_orient {ORIENT_NORTH, ORIENT_SOUTH, ORIENT_EAST, ORIENT_WEST,
547 ORIENT_FLIPPED_NORTH, ORIENT_FLIPPED_SOUTH, ORIENT_FLIPPED_EAST,
548 ORIENT_FLIPPED_WEST};
549
550 int
GeoTransOrient(t)551 GeoTransOrient(t)
552 Transform *t; /* Transform to be applied. */
553
554 {
555 int pidx;
556
557 if ((t->t_b == 0) && (t->t_d == 0))
558 {
559 pidx = ((t->t_a) > 0) ? 1 : 0;
560 pidx += ((t->t_e) > 0) ? 2 : 0;
561
562 switch (pidx) {
563 case 0:
564 return ORIENT_SOUTH;
565 case 1:
566 return ORIENT_FLIPPED_SOUTH;
567 case 2:
568 return ORIENT_FLIPPED_NORTH;
569 case 3:
570 return ORIENT_NORTH;
571 }
572 }
573 else if ((t->t_a == 0) && (t->t_e == 0))
574 {
575 pidx = ((t->t_b) > 0) ? 1 : 0;
576 pidx += ((t->t_d) > 0) ? 2 : 0;
577
578 switch (pidx) {
579 case 0:
580 return ORIENT_FLIPPED_EAST;
581 case 1:
582 return ORIENT_EAST;
583 case 2:
584 return ORIENT_WEST;
585 case 3:
586 return ORIENT_FLIPPED_WEST;
587 }
588 }
589 }
590
591
592 /*-------------------------------------------------------------------
593 * GeoInvertTrans --
594 * This routine computes the inverse of a transform.
595 *
596 * Results: None.
597 *
598 * Side Effects:
599 * The transform pointed to by inverse is overwritten with
600 * the inverse transform of t. Note: this method of inversion
601 * only works for rotations that are multiples of 90 degrees with
602 * unit scale factor. Beware any changes to this!
603 *-------------------------------------------------------------------
604 */
605
606 void
GeoInvertTrans(t,inverse)607 GeoInvertTrans(t, inverse)
608 Transform *t; /* Pointer to a transform */
609 Transform *inverse; /* Place to store the inverse */
610
611 {
612 Transform t2, t3;
613 t2.t_a = t2.t_e = 1;
614 t2.t_b = t2.t_d = 0;
615 t2.t_c = -t->t_c;
616 t2.t_f = -t->t_f;
617 t3.t_a = t->t_a;
618 t3.t_b = t->t_d;
619 t3.t_d = t->t_b;
620 t3.t_e = t->t_e;
621 t3.t_c = t3.t_f = 0;
622 GeoTransTrans(&t2, &t3, inverse);
623 }
624
625
626 /*-------------------------------------------------------------------
627 * GeoInclude --
628 * This routine includes one rectangle into another by expanding
629 * the second.
630 *
631 * Results:
632 * TRUE is returned if the destination had to be enlarged.
633 *
634 * Side Effects:
635 * The destination is enlarged (if necessary) so that it completely
636 * contains the area of both the original src and dst rectangles.
637 *-------------------------------------------------------------------
638 */
639
640 bool
GeoInclude(src,dst)641 GeoInclude(src, dst)
642 Rect *src, *dst;
643 {
644 int value;
645
646 if (GEO_RECTNULL(src)) return FALSE;
647 else if (GEO_RECTNULL(dst))
648 {
649 *dst = *src;
650 return TRUE;
651 }
652
653 value = FALSE;
654 if (dst->r_xbot > src->r_xbot)
655 {
656 dst->r_xbot = src->r_xbot;
657 value = TRUE;
658 }
659 if (dst->r_ybot > src->r_ybot)
660 {
661 dst->r_ybot = src->r_ybot;
662 value = TRUE;
663 }
664 if (dst->r_xtop < src->r_xtop)
665 {
666 dst->r_xtop = src->r_xtop;
667 value = TRUE;
668 }
669 if (dst->r_ytop < src->r_ytop)
670 {
671 dst->r_ytop = src->r_ytop;
672 value = TRUE;
673 }
674 return value;
675 }
676
677
678 /*-------------------------------------------------------------------
679 * GeoIncludeAll --
680 * This routine includes one rectangle into another by expanding
681 * the second. This routine differs from GeoInclude in that zero-
682 * size source rectangles are processed. The source or destination
683 * rectangle is considered to be NULL only if its lower-left corner
684 * is above or to the right of its upper right corner. In this
685 * case, the other rectangle is the result.
686 *
687 * Results:
688 * TRUE is returned if the destination is enlarged; otherwise FALSE.
689 *
690 * Side Effects:
691 * The destination is enlarged (if necessary) so that it completely
692 * contains the area of both the original src and dst rectangles.
693 *-------------------------------------------------------------------
694 */
695
696 bool
GeoIncludeAll(src,dst)697 GeoIncludeAll(src, dst)
698 Rect *src, *dst;
699 {
700 bool value;
701
702 if ((dst->r_xbot > dst->r_xtop) || (dst->r_ybot > dst->r_ytop))
703 {
704 *dst = *src;
705 return TRUE;
706 }
707
708 if ((src->r_xbot > src->r_xtop) || (src->r_ybot > src->r_ytop))
709 return FALSE;
710
711 value = FALSE;
712 if (dst->r_xbot > src->r_xbot)
713 {
714 dst->r_xbot = src->r_xbot;
715 value = TRUE;
716 }
717 if (dst->r_ybot > src->r_ybot)
718 {
719 dst->r_ybot = src->r_ybot;
720 value = TRUE;
721 }
722 if (dst->r_xtop < src->r_xtop)
723 {
724 dst->r_xtop = src->r_xtop;
725 value = TRUE;
726 }
727 if (dst->r_ytop < src->r_ytop)
728 {
729 dst->r_ytop = src->r_ytop;
730 value = TRUE;
731 }
732 return value;
733 }
734
735
736 /*-------------------------------------------------------------------
737 * GeoIncludePoint --
738 * This routine includes a point into a rectangle by expanding
739 * the rectangle if necessary. If the destination rectangle has
740 * its lower left corner above or to the right of its upper right
741 * corner, then use the source point to initialize the destination
742 * rectangle.
743 *
744 * Results:
745 * None.
746 *
747 * Side Effects:
748 * The destination is enlarged (if necessary) so that it completely
749 * contains the area of both the original src and dst.
750 *-------------------------------------------------------------------
751 */
752
753 void
GeoIncludePoint(src,dst)754 GeoIncludePoint(src, dst)
755 Point *src;
756 Rect *dst;
757 {
758 if ((dst->r_xbot > dst->r_xtop) || (dst->r_ybot > dst->r_ytop))
759 {
760 dst->r_ll = *src;
761 dst->r_ur = *src;
762 }
763 else
764 {
765 if (dst->r_xbot > src->p_x)
766 dst->r_xbot = src->p_x;
767 if (dst->r_ybot > src->p_y)
768 dst->r_ybot = src->p_y;
769 if (dst->r_xtop < src->p_x)
770 dst->r_xtop = src->p_x;
771 if (dst->r_ytop < src->p_y)
772 dst->r_ytop = src->p_y;
773 }
774 }
775
776 /*-------------------------------------------------------------------
777 * GeoIncludeRectInBBox() --
778 *
779 * Expand bounding box to include rectangle r
780 *
781 *-------------------------------------------------------------------
782 */
783 void
GeoIncludeRectInBBox(r,bbox)784 GeoIncludeRectInBBox(r, bbox)
785 Rect *r;
786 Rect *bbox;
787 {
788 bbox->r_xbot = MIN(bbox->r_xbot,r->r_xbot);
789 bbox->r_ybot = MIN(bbox->r_ybot,r->r_ybot);
790 bbox->r_xtop = MAX(bbox->r_xtop,r->r_xtop);
791 bbox->r_ytop = MAX(bbox->r_ytop,r->r_ytop);
792 }
793
794
795 /*-------------------------------------------------------------------
796 * GeoClip --
797 * clips one rectangle against another.
798 *
799 * Results: None.
800 *
801 * Side Effects:
802 * Rectangle r is clipped so that it includes only the
803 * intersection area between r and area. The rectangle
804 * may end up being turned inside out (xbot>xtop) if
805 * there was absolutely no intersection between the two
806 * boxes.
807 *-------------------------------------------------------------------
808 */
809
810 void
GeoClip(r,area)811 GeoClip(r, area)
812 Rect *r; /* Rectangle to be clipped. */
813 Rect *area; /* Area against which to be clipped. */
814
815 {
816 if (r->r_xbot < area->r_xbot) r->r_xbot = area->r_xbot;
817 if (r->r_ybot < area->r_ybot) r->r_ybot = area->r_ybot;
818 if (r->r_xtop > area->r_xtop) r->r_xtop = area->r_xtop;
819 if (r->r_ytop > area->r_ytop) r->r_ytop = area->r_ytop;
820 }
821
822 /*-------------------------------------------------------------------
823 * GeoClipPoint --
824 * Clips one point against a rectangle, moving the point into
825 * the rectangle if needed.
826 *
827 * Results: None.
828 *
829 * Side Effects:
830 * Point p is clipped so that it lies within or on the rectangle.
831 *-------------------------------------------------------------------
832 */
833
834 void
GeoClipPoint(p,area)835 GeoClipPoint(p, area)
836 Point *p; /* Point to be clipped. */
837 Rect *area; /* Area against which to be clipped. */
838 {
839 if (p->p_x < area->r_xbot) p->p_x = area->r_xbot;
840 if (p->p_y < area->r_ybot) p->p_y = area->r_ybot;
841 if (p->p_x > area->r_xtop) p->p_x = area->r_xtop;
842 if (p->p_y > area->r_ytop) p->p_y = area->r_ytop;
843 }
844
845 /*
846 * ----------------------------------------------------------------------------
847 * GeoDisjoint --
848 *
849 * Clip a rectanglular area against a clipping box, applying the
850 * supplied procedure to each rectangular region in "area" which
851 * falls outside "clipbox". This works in tile space, where a
852 * rectangle is assumed to contain its lower x- and y-coordinates
853 * but not its upper coordinates. It does NOT work in pixel space
854 * (think about this carefully before using it for pixels!).
855 *
856 * The procedure should be of the form:
857 * bool func(box, cdarg)
858 * Rect * box;
859 * ClientData cdarg;
860 *
861 * Results:
862 * Return TRUE unless the supplied function returns FALSE.
863 *
864 * Side effects:
865 * The side effects of the invoked procedure.
866 * ----------------------------------------------------------------------------
867 */
868
869 bool
GeoDisjoint(area,clipBox,func,cdarg)870 GeoDisjoint(area, clipBox, func, cdarg)
871 Rect * area;
872 Rect * clipBox;
873 bool (*func) ();
874 ClientData cdarg;
875 {
876 Rect ok, rArea;
877 bool result;
878
879 #define NULLBOX(R) ((R.r_xbot>R.r_xtop)||(R.r_ybot>R.r_ytop))
880
881 ASSERT((area!=(Rect *) NULL), "GeoDisjoint");
882 if((clipBox==(Rect *) NULL)||(!GEO_OVERLAP(area, clipBox)))
883 {
884 /* Since there is no overlap, all of "area" may be processed. */
885
886 result= (*func)(area, cdarg);
887 return(result);
888 }
889
890 /* Do the disjoint operation in four steps, one for each side
891 * of clipBox. In each step, divide the area being clipped
892 * into one piece that is DEFINITELY outside clipBox, and one
893 * piece left to check some more.
894 */
895
896 /* Top edge of clipBox: */
897
898 rArea = *area;
899 result = TRUE;
900 if (clipBox->r_ytop < rArea.r_ytop)
901 {
902 ok = rArea;
903 rArea.r_ytop = ok.r_ybot = clipBox->r_ytop;
904 if (!(*func)(&ok, cdarg)) result = FALSE;
905 }
906
907 /* Bottom edge of clipBox: */
908
909 if (clipBox->r_ybot > rArea.r_ybot)
910 {
911 ok = rArea;
912 rArea.r_ybot = ok.r_ytop = clipBox->r_ybot;
913 if (!(*func)(&ok, cdarg)) result = FALSE;
914 }
915
916 /* Right edge of clipBox: */
917
918 if (clipBox->r_xtop < rArea.r_xtop)
919 {
920 ok = rArea;
921 rArea.r_xtop = ok.r_xbot = clipBox->r_xtop;
922 if (!(*func)(&ok, cdarg)) result = FALSE;
923 }
924
925 /* Left edge of clipBox: */
926
927 if (clipBox->r_xbot > rArea.r_xbot)
928 {
929 ok = rArea;
930 rArea.r_xbot = ok.r_xtop = clipBox->r_xbot;
931 if (!(*func)(&ok, cdarg)) result = FALSE;
932 }
933
934 /* Just throw away what's left of the area being clipped, since
935 * it overlaps the clipBox.
936 */
937
938 return result;
939 } /*GeoDisjoint*/
940
941
942 bool
GeoDummyFunc(box,cdarg)943 GeoDummyFunc(box, cdarg)
944 Rect * box;
945 ClientData cdarg;
946 {
947 return TRUE;
948 }
949
950
951 /*-------------------------------------------------------------------
952 * GeoCanonicalRect --
953 * Turns a rectangle into a canonical form in which the
954 * lower left is really below and to the left of the upper right.
955 *
956 * Results: None.
957 *
958 * Side Effects:
959 * Rectangle rnew is set to the canonical form of rectangle r.
960 *-------------------------------------------------------------------
961 */
962
963 void
GeoCanonicalRect(r,rnew)964 GeoCanonicalRect(r, rnew)
965 Rect *r;
966 Rect *rnew;
967 {
968 if (r->r_xbot > r->r_xtop)
969 {
970 rnew->r_xbot = r->r_xtop;
971 rnew->r_xtop = r->r_xbot;
972 }
973 else
974 {
975 rnew->r_xbot = r->r_xbot;
976 rnew->r_xtop = r->r_xtop;
977 }
978
979 if (r->r_ybot > r->r_ytop)
980 {
981 rnew->r_ybot = r->r_ytop;
982 rnew->r_ytop = r->r_ybot;
983 }
984 else
985 {
986 rnew->r_ybot = r->r_ybot;
987 rnew->r_ytop = r->r_ytop;
988 }
989 }
990
991 /*-------------------------------------------------------------------
992 * GeoScale --
993 *
994 * Returns the scale factor associated with a transform.
995 *
996 * Results:
997 * Scale factor.
998 *
999 * Side Effects:
1000 * None.
1001 *-------------------------------------------------------------------
1002 */
1003
1004 int
GeoScale(t)1005 GeoScale(t)
1006 Transform *t;
1007 {
1008 int scale;
1009
1010 scale = t->t_a;
1011 if (scale == 0)
1012 scale = t->t_b;
1013
1014 if (scale < 0)
1015 scale = (-scale);
1016
1017 return (scale);
1018 }
1019
1020 /*-------------------------------------------------------------------
1021 * GeoScaleTrans --
1022 * Scale a transform by the indicated magnification.
1023 *
1024 * Results: None.
1025 *
1026 * Side Effects:
1027 * Trans2 is set to the result of scaling trans1 by (integer)
1028 * magnification m. Non-integer magnifications are not
1029 * handled.
1030 *-------------------------------------------------------------------
1031 */
1032
1033 void
GeoScaleTrans(trans1,m,trans2)1034 GeoScaleTrans(trans1, m, trans2)
1035 Transform *trans1; /* Transform to be scaled */
1036 int m; /* Amount by which to scale */
1037 Transform *trans2; /* Result transform */
1038 {
1039 trans2->t_a = trans1->t_a * m;
1040 trans2->t_b = trans1->t_b * m;
1041 trans2->t_c = trans1->t_c * m;
1042 trans2->t_d = trans1->t_d * m;
1043 trans2->t_e = trans1->t_e * m;
1044 trans2->t_f = trans1->t_f * m;
1045 }
1046
1047
1048 /*-------------------------------------------------------------------
1049 * GeoRectPointSide --
1050 *
1051 * Returns the side of the rect on which a point lies.
1052 *
1053 * Results:
1054 * A direction, or GEO_CENTER if the point is off the boundary.
1055 *
1056 * Side Effects:
1057 * None.
1058 *-------------------------------------------------------------------
1059 */
1060
1061 int
GeoRectPointSide(r,p)1062 GeoRectPointSide(r, p)
1063 Rect * r;
1064 Point * p;
1065 {
1066 if(r->r_xbot == p->p_x) return GEO_WEST;
1067 else
1068 if(r->r_xtop == p->p_x) return GEO_EAST;
1069 else
1070 if(r->r_ybot == p->p_y) return GEO_SOUTH;
1071 else
1072 if(r->r_ytop == p->p_y) return GEO_NORTH;
1073 else
1074 return(GEO_CENTER);
1075 }
1076
1077 /*-------------------------------------------------------------------
1078 * GeoRectRectSide --
1079 *
1080 * Returns the side of the first rect on which the second one
1081 * lies.
1082 *
1083 * Results:
1084 * A direction, or GEO_CENTER if the rects don't share some
1085 * coordinate. Note, this won't detect the case where the
1086 * rectangles don't touch but do share some coordinate.
1087 *
1088 * Side Effects:
1089 * None.
1090 *-------------------------------------------------------------------
1091 */
1092
1093 int
GeoRectRectSide(r0,r1)1094 GeoRectRectSide(r0, r1)
1095 Rect * r0;
1096 Rect * r1;
1097 {
1098 if(r0->r_xbot == r1->r_xtop) return GEO_WEST;
1099 else
1100 if(r0->r_xtop == r1->r_xbot) return GEO_EAST;
1101 else
1102 if(r0->r_ybot == r1->r_ytop) return GEO_SOUTH;
1103 else
1104 if(r0->r_ytop == r1->r_ybot) return GEO_NORTH;
1105 else
1106 return(GEO_CENTER);
1107 }
1108
1109 /* ----------------------------------------------------------------------------
1110 *
1111 * GeoDecomposeTransform --
1112 *
1113 * Break a transform up into an optional mirror followed by an optional
1114 * rotation. Translation is ignored. Maybe someone will add this at
1115 * a later date.
1116 *
1117 * Results:
1118 * None.
1119 *
1120 * Side Effects:
1121 * Modifies 'angle' and 'upsidedown' parameters.
1122 *
1123 * ----------------------------------------------------------------------------
1124 */
1125
1126 void
GeoDecomposeTransform(t,upsidedown,angle)1127 GeoDecomposeTransform(t, upsidedown, angle)
1128 Transform *t;
1129 bool *upsidedown; /* Set to TRUE iff we should flip upsidedown
1130 * before rotating.
1131 */
1132 int *angle; /* Amount to rotate.
1133 * Will be 0, 90, 180, or 270.
1134 */
1135 {
1136 Transform notrans; /* Transform without any translation -- includes
1137 * both rotation and mirroring.
1138 */
1139 Transform rotonly; /* Version of above with only rotation. */
1140
1141 notrans = *t;
1142 notrans.t_c = 0;
1143 notrans.t_f = 0;
1144
1145 /* Compute rotations and flips. */
1146 *upsidedown = ((notrans.t_a == 0) ^
1147 (notrans.t_b == notrans.t_d) ^ (notrans.t_a == notrans.t_e));
1148 if (*upsidedown)
1149 GeoTransTrans(¬rans, &GeoUpsideDownTransform, &rotonly);
1150 else
1151 rotonly = notrans;
1152 /* Verify no flipping. */
1153 ASSERT(rotonly.t_a == rotonly.t_e, "GeoDecomposeTransform");
1154
1155 *angle = 0;
1156 if (rotonly.t_b != 0)
1157 {
1158 *angle += 90;
1159 if (*upsidedown) *angle += 180;
1160 }
1161 if ((rotonly.t_a < 0) || (rotonly.t_b < 0)) *angle += 180;
1162 if (*angle > 270) *angle -= 360;
1163 }
1164