src/box.h

   1 /*
   2  *                            COPYRIGHT
   3  *
   4  *  PCB, interactive printed circuit board design
   5  *  Copyright (C) 1994,1995,1996 Thomas Nau
   6  *  Copyright (C) 1998,1999,2000,2001 harry eaton
   7  *
   8  *  This program is free software; you can redistribute it and/or modify
   9  *  it under the terms of the GNU General Public License as published by
  10  *  the Free Software Foundation; either version 2 of the License, or
  11  *  (at your option) any later version.
  12  *
  13  *  This program is distributed in the hope that it will be useful,
  14  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16  *  GNU General Public License for more details.
  17  *
  18  *  You should have received a copy of the GNU General Public License
  19  *  along with this program; if not, write to the Free Software
  20  *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  21  *
  22  *  Contact addresses for paper mail and Email:
  23  *  harry eaton, 6697 Buttonhole Ct, Columbia, MD 21044 USA
  24  *  haceaton@aplcomm.jhuapl.edu
  25  *
  26  */
  27
  28 /* this file, box.h, was written and is
  29  * Copyright (c) 2001 C. Scott Ananian.
  30  */
  31
  32 /* random box-related utilities.
  33  */
  34
  35 #ifndef PCB_BOX_H
  36 #define PCB_BOX_H
  37
  38 #include <assert.h>
  39 #include "global.h"
  40
  41 #include "misc.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) { Coord 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 { Coord 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 { Coord 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   Coord 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, Coord X, Coord 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, Coord X, Coord 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, Coord 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, Coord 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 (Coord X, Coord 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 double
 224 dist2_to_box (const CheapPointType * p, const BoxType * b)
 225 {
 226   CheapPointType r = closest_point_in_box (p, b);
 227   return Distance (r.X, r.Y, p->X, p->Y);
 228 }
 229
 230 #endif /* __BOX_H_INCLUDED__ */