src/box.h

   1 /* $Id$ */
   2
   3 /*
   4  *                            COPYRIGHT
   5  *
   6  *  PCB, interactive printed circuit board design
   7  *  Copyright (C) 1994,1995,1996 Thomas Nau
   8  *  Copyright (C) 1998,1999,2000,2001 harry eaton
   9  *
  10  *  This program is free software; you can redistribute it and/or modify
  11  *  it under the terms of the GNU General Public License as published by
  12  *  the Free Software Foundation; either version 2 of the License, or
  13  *  (at your option) any later version.
  14  *
  15  *  This program is distributed in the hope that it will be useful,
  16  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  17  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18  *  GNU General Public License for more details.
  19  *
  20  *  You should have received a copy of the GNU General Public License
  21  *  along with this program; if not, write to the Free Software
  22  *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  23  *
  24  *  Contact addresses for paper mail and Email:
  25  *  harry eaton, 6697 Buttonhole Ct, Columbia, MD 21044 USA
  26  *  haceaton@aplcomm.jhuapl.edu
  27  *
  28  */
  29
  30 /* this file, box.h, was written and is
  31  * Copyright (c) 2001 C. Scott Ananian.
  32  */
  33
  34 /* random box-related utilities.
  35  */
  36
  37 #ifndef __BOX_H_INCLUDED__
  38 #define __BOX_H_INCLUDED__
  39
  40 #include <assert.h>
  41 #include "global.h"
  42
  43 typedef enum
  44 { NORTH = 0, EAST = 1, SOUTH = 2, WEST = 3, NE = 4, SE = 5, SW = 6, NW =
  45     7, ALL = 8 } direction_t;
  46
  47 /* rotates box 90-degrees cw */
  48 /* that's a strange rotation! */
  49 #define ROTATEBOX_CW(box) { LocationType t;\
  50     t = (box).X1; (box).X1 = -(box).Y2; (box).Y2 = (box).X2;\
  51     (box).X2 = -(box).Y1; (box).Y1 = t;\
  52 }
  53 #define ROTATEBOX_TO_NORTH(box, dir) do { LocationType t;\
  54   switch(dir) {\
  55   case EAST: \
  56    t = (box).X1; (box).X1 = (box).Y1; (box).Y1 = -(box).X2;\
  57    (box).X2 = (box).Y2; (box).Y2 = -t; break;\
  58   case SOUTH: \
  59    t = (box).X1; (box).X1 = -(box).X2; (box).X2 = -t;\
  60    t = (box).Y1; (box).Y1 = -(box).Y2; (box).Y2 = -t; break;\
  61   case WEST: \
  62    t = (box).X1; (box).X1 = -(box).Y2; (box).Y2 = (box).X2;\
  63    (box).X2 = -(box).Y1; (box).Y1 = t; break;\
  64   case NORTH: break;\
  65   default: assert(0);\
  66   }\
  67   } while (0)
  68 #define ROTATEBOX_FROM_NORTH(box, dir) do { LocationType t;\
  69   switch(dir) {\
  70   case WEST: \
  71    t = (box).X1; (box).X1 = (box).Y1; (box).Y1 = -(box).X2;\
  72    (box).X2 = (box).Y2; (box).Y2 = -t; break;\
  73   case SOUTH: \
  74    t = (box).X1; (box).X1 = -(box).X2; (box).X2 = -t;\
  75    t = (box).Y1; (box).Y1 = -(box).Y2; (box).Y2 = -t; break;\
  76   case EAST: \
  77    t = (box).X1; (box).X1 = -(box).Y2; (box).Y2 = (box).X2;\
  78    (box).X2 = -(box).Y1; (box).Y1 = t; break;\
  79   case NORTH: break;\
  80   default: assert(0);\
  81   }\
  82   } while (0)
  83
  84 /* to avoid overflow, we calculate centers this way */
  85 #define CENTER_X(b) ((b).X1 + ((b).X2 - (b).X1)/2)
  86 #define CENTER_Y(b) ((b).Y1 + ((b).Y2 - (b).Y1)/2)
  87 /* some useful box utilities. */
  88
  89 typedef struct cheap_point
  90 {
  91   LocationType X, Y;
  92 } CheapPointType;
  93
  94
  95 /* note that boxes are closed on top and left and open on bottom and right. */
  96 /* this means that top-left corner is in box, *but bottom-right corner is
  97  * not*.  */
  98 static inline bool
  99 point_in_box (const BoxType * box, LocationType X, LocationType Y)
 100 {
 101   return (X >= box->X1) && (Y >= box->Y1) && (X < box->X2) && (Y < box->Y2);
 102 }
 103
 104 static inline bool
 105 point_in_closed_box (const BoxType * box, LocationType X, LocationType Y)
 106 {
 107   return (X >= box->X1) && (Y >= box->Y1) && (X <= box->X2) && (Y <= box->Y2);
 108 }
 109
 110 static inline bool
 111 box_is_good (const BoxType * b)
 112 {
 113   return (b->X1 < b->X2) && (b->Y1 < b->Y2);
 114 }
 115
 116 static inline bool
 117 box_intersect (const BoxType * a, const BoxType * b)
 118 {
 119   return
 120     (a->X1 < b->X2) && (b->X1 < a->X2) && (a->Y1 < b->Y2) && (b->Y1 < a->Y2);
 121 }
 122
 123 static inline CheapPointType
 124 closest_point_in_box (const CheapPointType * from, const BoxType * box)
 125 {
 126   CheapPointType r;
 127   assert (box->X1 < box->X2 && box->Y1 < box->Y2);
 128   r.X =
 129     (from->X < box->X1) ? box->X1 : (from->X >
 130                                      box->X2 - 1) ? box->X2 - 1 : from->X;
 131   r.Y =
 132     (from->Y < box->Y1) ? box->Y1 : (from->Y >
 133                                      box->Y2 - 1) ? box->Y2 - 1 : from->Y;
 134   assert (point_in_box (box, r.X, r.Y));
 135   return r;
 136 }
 137
 138 static inline bool
 139 box_in_box (const BoxType * outer, const BoxType * inner)
 140 {
 141   return
 142     (outer->X1 <= inner->X1) && (inner->X2 <= outer->X2) &&
 143     (outer->Y1 <= inner->Y1) && (inner->Y2 <= outer->Y2);
 144 }
 145
 146 static inline BoxType
 147 clip_box (const BoxType * box, const BoxType * clipbox)
 148 {
 149   BoxType r;
 150   assert (box_intersect (box, clipbox));
 151   r.X1 = MAX (box->X1, clipbox->X1);
 152   r.X2 = MIN (box->X2, clipbox->X2);
 153   r.Y1 = MAX (box->Y1, clipbox->Y1);
 154   r.Y2 = MIN (box->Y2, clipbox->Y2);
 155   assert (box_in_box (clipbox, &r));
 156   return r;
 157 }
 158
 159 static inline BoxType
 160 shrink_box (const BoxType * box, LocationType amount)
 161 {
 162   BoxType r = *box;
 163   r.X1 += amount;
 164   r.Y1 += amount;
 165   r.X2 -= amount;
 166   r.Y2 -= amount;
 167   return r;
 168 }
 169
 170 static inline BoxType
 171 bloat_box (const BoxType * box, LocationType amount)
 172 {
 173   return shrink_box (box, -amount);
 174 }
 175
 176 /* construct a minimum box that touches the input box at the center */
 177 static inline BoxType
 178 box_center (const BoxType * box)
 179 {
 180   BoxType r;
 181   r.X1 = box->X1 + (box->X2 - box->X1)/2;
 182   r.X2 = r.X1 + 1;
 183   r.Y1 = box->Y1 + (box->Y2 - box->Y1)/2;
 184   r.Y2 = r.Y1 + 1;
 185   return r;
 186 }
 187
 188 /* construct a minimum box that touches the input box at the corner */
 189 static inline BoxType
 190 box_corner (const BoxType * box)
 191 {
 192   BoxType r;
 193   r.X1 = box->X1;
 194   r.X2 = r.X1 + 1;
 195   r.Y1 = box->Y1;
 196   r.Y2 = r.Y1 + 1;
 197   return r;
 198 }
 199
 200 /* construct a box that holds a single point */
 201 static inline BoxType
 202 point_box (LocationType X, LocationType Y)
 203 {
 204   BoxType r;
 205   r.X1 = X;
 206   r.X2 = X + 1;
 207   r.Y1 = Y;
 208   r.Y2 = Y + 1;
 209   return r;
 210 }
 211
 212 /* close a bounding box by pushing its upper right corner */
 213 static inline void
 214 close_box (BoxType * r)
 215 {
 216   r->X2++;
 217   r->Y2++;
 218 }
 219
 220 /* return the square of the minimum distance from a point to some point
 221  * inside a box.  The box is half-closed!  That is, the top-left corner
 222  * is considered in the box, but the bottom-right corner is not. */
 223 static inline float
 224 dist2_to_box (const CheapPointType * p, const BoxType * b)
 225 {
 226   CheapPointType r = closest_point_in_box (p, b);
 227   float x_dist = (r.X - p->X);
 228   float y_dist = (r.Y - p->Y);
 229   return (x_dist * x_dist) + (y_dist * y_dist);
 230 }
 231
 232 #endif /* __BOX_H_INCLUDED__ */