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