src/box.h

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