1 /* 2 * Copyright (C) 2010-2011 Dmitry Marakasov 3 * 4 * This file is part of glosm. 5 * 6 * glosm is free software: you can redistribute it and/or modify 7 * it under the terms of the GNU General Public License as published by 8 * the Free Software Foundation, either version 3 of the License, or 9 * (at your option) any later version. 10 * 11 * glosm is distributed in the hope that it will be useful, 12 * but WITHOUT ANY WARRANTY; without even the implied warranty of 13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 * GNU General Public License for more details. 15 * 16 * You should have received a copy of the GNU General Public License 17 * along with glosm. If not, see <http://www.gnu.org/licenses/>. 18 */ 19 20 #ifndef BBOX_HH 21 #define BBOX_HH 22 23 #include <glosm/Math.hh> 24 25 /** 26 * Template axis-aligned bounding box class 27 */ 28 template <typename T> 29 struct BBox { 30 public: 31 /** 32 * Sides of boundng box 33 */ 34 enum Side { 35 NONE = 0, 36 LEFT = 1, 37 BOTTOM = 2, 38 RIGHT = 3, 39 TOP = 4 40 }; 41 42 public: 43 typedef typename LongType<T>::type LT; 44 45 public: 46 /* CTORS */ 47 48 /** 49 * Constructs empty bounding box 50 */ BBoxBBox51 BBox(): left(std::numeric_limits<T>::max()), bottom(std::numeric_limits<T>::max()), right(std::numeric_limits<T>::min()), top(std::numeric_limits<T>::min()) { 52 } 53 54 /** 55 * Constructs bbox by two corners 56 * 57 * @param one one corner 58 * @param two another corner 59 */ BBoxBBox60 BBox(const Vector2<T>& one, const Vector2<T>& two) { 61 if (one.x < two.x) { 62 left = one.x; 63 right = two.x; 64 } else { 65 left = two.x; 66 right = one.x; 67 } 68 69 if (one.y < two.y) { 70 bottom = one.y; 71 top = two.y; 72 } else { 73 bottom = two.y; 74 top = one.y; 75 } 76 } 77 78 /** 79 * Constructs bbox by its sides 80 * 81 * @param l left side 82 * @param b bottom side 83 * @param r right side 84 * @param t top side 85 */ BBoxBBox86 BBox(T l, T b, T r, T t): left(l), bottom(b), right(r), top(t) { 87 } 88 89 /** 90 * Constructs copy of other 91 */ BBoxBBox92 BBox(const BBox<T>& other): left(other.left), bottom(other.bottom), right(other.right), top(other.top) { 93 } 94 95 /* STATIC CTORS */ 96 97 /** 98 * Creates bbox that contains all possible points 99 */ FullBBox100 static BBox<T> Full() { 101 return BBox<T>(std::numeric_limits<T>::min(), std::numeric_limits<T>::min(), std::numeric_limits<T>::max(), std::numeric_limits<T>::max()); 102 } 103 104 /** 105 * Creates bbox that contains no points 106 */ EmptyBBox107 static BBox<T> Empty() { 108 return BBox<T>(std::numeric_limits<T>::max(), std::numeric_limits<T>::max(), std::numeric_limits<T>::min(), std::numeric_limits<T>::min()); 109 } 110 111 /* following are specialized only for <osmint_t>, see BBox.cc */ 112 113 /** 114 * Creates bbox that covers earth surface 115 * 116 * @note only specialized for <osmint_t>, see BBox.cc 117 */ 118 static BBox<T> ForEarth(); 119 120 /** 121 * Creates bbox for specified mercator tile 122 * 123 * @param zoom zoom 124 * @param x x-coordinate (longitued) 125 * @param y t-coordinate (latitude) 126 * 127 * Mercator tile numbering is similar with those used in mapnik 128 * 129 * @note only specialized for <osmint_t>, see BBox.cc 130 */ 131 static BBox<T> ForMercatorTile(int zoom, int x, int y); 132 133 /** 134 * Creates bbox for specified geo tile 135 * 136 * @param zoom zoom 137 * @param x x-coordinate (longitued) 138 * @param y t-coordinate (latitude) 139 * 140 * Geo tiles uniformly split earth rectangle and are numbered from topleft 141 * 142 * @note only specialized for <osmint_t>, see BBox.cc 143 */ 144 static BBox<T> ForGeoTile(int zoom, int x, int y); 145 146 /* MUTATORS */ 147 148 /** 149 * Includes a single point into bbox, expanding it if necessary 150 */ IncludeBBox151 void Include(const Vector2<T>& point) { 152 if (point.x < left) 153 left = point.x; 154 if (point.x > right) 155 right = point.x; 156 if (point.y < bottom) 157 bottom = point.y; 158 if (point.y > top) 159 top = point.y; 160 } 161 162 /** 163 * Includes another bbox into bbox, expanding it if necessary 164 */ IncludeBBox165 void Include(const BBox<T>& bbox) { 166 if (bbox.left < left) 167 left = bbox.left; 168 if (bbox.right > right) 169 right = bbox.right; 170 if (bbox.bottom < bottom) 171 bottom = bbox.bottom; 172 if (bbox.top > top) 173 top = bbox.top; 174 } 175 176 /** 177 * Returns geometrical center of a bbox 178 */ GetCenterBBox179 inline Vector2<T> GetCenter() const { 180 return Vector2<T>(((LT)left + (LT)right)/2, ((LT)top + (LT)bottom)/2); 181 } 182 183 /** 184 * Returns bottom left corner of a bbox 185 */ GetBottomLeftBBox186 inline Vector2<T> GetBottomLeft() const { 187 return Vector2<T>(left, bottom); 188 } 189 190 /** 191 * Returns bottom right corner of a bbox 192 */ GetBottomRightBBox193 inline Vector2<T> GetBottomRight() const { 194 return Vector2<T>(right, bottom); 195 } 196 197 /** 198 * Returns top left corner of a bbox 199 */ GetTopLeftBBox200 inline Vector2<T> GetTopLeft() const { 201 return Vector2<T>(left, top); 202 } 203 204 /** 205 * Returns top right corner of a bbox 206 */ GetTopRightBBox207 inline Vector2<T> GetTopRight() const { 208 return Vector2<T>(right, top); 209 } 210 211 /* CHECKS */ 212 213 /** 214 * Checks whether bbox is empty 215 * 216 * @return true if bbox is empty, false otherwise 217 */ IsEmptyBBox218 inline bool IsEmpty() const { 219 return left > right || bottom > top; 220 } 221 222 /** 223 * Checks whether bbox contains specific point 224 * 225 * @return true if bbox contains point, false otherwise 226 */ ContainsBBox227 inline bool Contains(const Vector2<T>& point) const { 228 return point.x >= left && point.x <= right && point.y >= bottom && point.y <= top; 229 } 230 231 /** 232 * Checks whether bbox intersects with another bbox 233 * 234 * @return true if bbox contains another bbox, false otherwise 235 */ IntersectsBBox236 inline bool Intersects(const BBox<T>& other) const { 237 return !(other.right < left || other.left > right || other.top < bottom || other.bottom > top); 238 } 239 240 /** 241 * Checks whether point is located to the specific side from bbox 242 */ IsPointOutAtSideBBox243 inline bool IsPointOutAtSide(const Vector2i& point, Side side) const { 244 switch (side) { 245 case LEFT: return point.x < left; 246 case RIGHT: return point.x > right; 247 case TOP: return point.y > top; 248 case BOTTOM: return point.y < bottom; 249 default: return false; 250 } 251 } 252 253 /** 254 * Returns point of bbox nearest to specific point 255 */ 256 template<class V> NearestPointBBox257 inline Vector2<T> NearestPoint(const V& vec) const { 258 if (vec.x < left) { 259 /* to the left */ 260 if (vec.y < bottom) 261 return GetBottomLeft(); 262 else if (vec.y > top) 263 return GetTopLeft(); 264 else 265 return Vector2<T>(left, vec.y); 266 } else if (vec.x > right) { 267 /* to the right */ 268 if (vec.y < bottom) 269 return GetBottomRight(); 270 else if (vec.y > top) 271 return GetTopRight(); 272 else 273 return Vector2<T>(right, vec.y); 274 } else { 275 if (vec.y < bottom) 276 return Vector2<T>(vec.x, bottom); 277 else if (vec.y > top) 278 return Vector2<T>(vec.x, top); 279 else 280 return vec; /* inside bbox */ 281 } 282 } 283 284 /** 285 * Returns point of bbox farthest from specific point 286 */ 287 template<class V> FarthestPointBBox288 inline Vector2<T> FarthestPoint(const V& vec) const { 289 Vector2<T> center = GetCenter(); 290 if (vec.x < center.x) { 291 if (vec.y < center.y) 292 return GetTopRight(); 293 else 294 return GetBottomRight(); 295 } else { 296 if (vec.y < center.y) 297 return GetTopLeft(); 298 else 299 return GetBottomLeft(); 300 } 301 } 302 303 /* data */ 304 T left, bottom, right, top; 305 }; 306 307 typedef BBox<osmint_t> BBoxi; 308 typedef BBox<osmlong_t> BBoxl; 309 typedef BBox<float> BBoxf; 310 typedef BBox<double> BBoxd; 311 312 #endif 313