alpar@2658
|
1 |
/* -*- C++ -*-
|
alpar@2658
|
2 |
*
|
alpar@2658
|
3 |
* This file is a part of LEMON, a generic C++ optimization library
|
alpar@2658
|
4 |
*
|
alpar@2658
|
5 |
* Copyright (C) 2003-2006
|
alpar@2658
|
6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
|
alpar@2658
|
7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES).
|
alpar@2658
|
8 |
*
|
alpar@2658
|
9 |
* Permission to use, modify and distribute this software is granted
|
alpar@2658
|
10 |
* provided that this copyright notice appears in all copies. For
|
alpar@2658
|
11 |
* precise terms see the accompanying LICENSE file.
|
alpar@2658
|
12 |
*
|
alpar@2658
|
13 |
* This software is provided "AS IS" with no warranty of any kind,
|
alpar@2658
|
14 |
* express or implied, and with no claim as to its suitability for any
|
alpar@2658
|
15 |
* purpose.
|
alpar@2658
|
16 |
*
|
alpar@2658
|
17 |
*/
|
alpar@2658
|
18 |
|
alpar@2658
|
19 |
#ifndef LEMON_DIM2_H
|
alpar@2658
|
20 |
#define LEMON_DIM2_H
|
alpar@2658
|
21 |
|
alpar@2658
|
22 |
#include <iostream>
|
alpar@2658
|
23 |
#include <lemon/bits/utility.h>
|
alpar@2658
|
24 |
|
alpar@2658
|
25 |
///\ingroup misc
|
alpar@2658
|
26 |
///\file
|
alpar@2658
|
27 |
///\brief A simple two dimensional vector and a bounding box implementation
|
alpar@2658
|
28 |
///
|
alpar@2658
|
29 |
/// The class \ref lemon::dim2::Point "dim2::Point" implements
|
alpar@2658
|
30 |
///a two dimensional vector with the usual
|
alpar@2658
|
31 |
/// operations.
|
alpar@2658
|
32 |
///
|
alpar@2658
|
33 |
/// The class \ref lemon::dim2::BoundingBox "dim2::BoundingBox"
|
alpar@2658
|
34 |
/// can be used to determine
|
alpar@2658
|
35 |
/// the rectangular bounding box of a set of
|
alpar@2658
|
36 |
/// \ref lemon::dim2::Point "dim2::Point"'s.
|
alpar@2658
|
37 |
///
|
alpar@2658
|
38 |
///\author Attila Bernath
|
alpar@2658
|
39 |
|
alpar@2658
|
40 |
|
alpar@2658
|
41 |
namespace lemon {
|
alpar@2658
|
42 |
|
alpar@2658
|
43 |
///Tools for handling two dimensional coordinates
|
alpar@2658
|
44 |
|
alpar@2658
|
45 |
///This namespace is a storage of several
|
alpar@2658
|
46 |
///tools for handling two dimensional coordinates
|
alpar@2658
|
47 |
namespace dim2 {
|
alpar@2658
|
48 |
|
alpar@2658
|
49 |
/// \addtogroup misc
|
alpar@2658
|
50 |
/// @{
|
alpar@2658
|
51 |
|
alpar@2658
|
52 |
/// A simple two dimensional vector (plainvector) implementation
|
alpar@2658
|
53 |
|
alpar@2658
|
54 |
/// A simple two dimensional vector (plainvector) implementation
|
alpar@2658
|
55 |
///with the usual vector
|
alpar@2658
|
56 |
/// operators.
|
alpar@2658
|
57 |
///
|
alpar@2658
|
58 |
template<typename T>
|
alpar@2658
|
59 |
class Point {
|
alpar@2658
|
60 |
|
alpar@2658
|
61 |
public:
|
alpar@2658
|
62 |
|
alpar@2658
|
63 |
typedef T Value;
|
alpar@2658
|
64 |
|
alpar@2658
|
65 |
///First co-ordinate
|
alpar@2658
|
66 |
T x;
|
alpar@2658
|
67 |
///Second co-ordinate
|
alpar@2658
|
68 |
T y;
|
alpar@2658
|
69 |
|
alpar@2658
|
70 |
///Default constructor
|
alpar@2658
|
71 |
Point() {}
|
alpar@2658
|
72 |
|
alpar@2658
|
73 |
///Construct an instance from coordinates
|
alpar@2658
|
74 |
Point(T a, T b) : x(a), y(b) { }
|
alpar@2658
|
75 |
|
alpar@2658
|
76 |
///The dimension of the vector.
|
alpar@2658
|
77 |
|
alpar@2658
|
78 |
///This class give back always 2.
|
alpar@2658
|
79 |
///
|
alpar@2658
|
80 |
int size() const { return 2; }
|
alpar@2658
|
81 |
|
alpar@2658
|
82 |
///Subscripting operator
|
alpar@2658
|
83 |
|
alpar@2658
|
84 |
///\c p[0] is \c p.x and \c p[1] is \c p.y
|
alpar@2658
|
85 |
///
|
alpar@2658
|
86 |
T& operator[](int idx) { return idx == 0 ? x : y; }
|
alpar@2658
|
87 |
|
alpar@2658
|
88 |
///Const subscripting operator
|
alpar@2658
|
89 |
|
alpar@2658
|
90 |
///\c p[0] is \c p.x and \c p[1] is \c p.y
|
alpar@2658
|
91 |
///
|
alpar@2658
|
92 |
const T& operator[](int idx) const { return idx == 0 ? x : y; }
|
alpar@2658
|
93 |
|
alpar@2658
|
94 |
///Conversion constructor
|
alpar@2658
|
95 |
template<class TT> Point(const Point<TT> &p) : x(p.x), y(p.y) {}
|
alpar@2658
|
96 |
|
alpar@2658
|
97 |
///Give back the square of the norm of the vector
|
alpar@2658
|
98 |
T normSquare() const {
|
alpar@2658
|
99 |
return x*x+y*y;
|
alpar@2658
|
100 |
}
|
alpar@2658
|
101 |
|
alpar@2658
|
102 |
///Increment the left hand side by u
|
alpar@2658
|
103 |
Point<T>& operator +=(const Point<T>& u) {
|
alpar@2658
|
104 |
x += u.x;
|
alpar@2658
|
105 |
y += u.y;
|
alpar@2658
|
106 |
return *this;
|
alpar@2658
|
107 |
}
|
alpar@2658
|
108 |
|
alpar@2658
|
109 |
///Decrement the left hand side by u
|
alpar@2658
|
110 |
Point<T>& operator -=(const Point<T>& u) {
|
alpar@2658
|
111 |
x -= u.x;
|
alpar@2658
|
112 |
y -= u.y;
|
alpar@2658
|
113 |
return *this;
|
alpar@2658
|
114 |
}
|
alpar@2658
|
115 |
|
alpar@2658
|
116 |
///Multiply the left hand side with a scalar
|
alpar@2658
|
117 |
Point<T>& operator *=(const T &u) {
|
alpar@2658
|
118 |
x *= u;
|
alpar@2658
|
119 |
y *= u;
|
alpar@2658
|
120 |
return *this;
|
alpar@2658
|
121 |
}
|
alpar@2658
|
122 |
|
alpar@2658
|
123 |
///Divide the left hand side by a scalar
|
alpar@2658
|
124 |
Point<T>& operator /=(const T &u) {
|
alpar@2658
|
125 |
x /= u;
|
alpar@2658
|
126 |
y /= u;
|
alpar@2658
|
127 |
return *this;
|
alpar@2658
|
128 |
}
|
alpar@2658
|
129 |
|
alpar@2658
|
130 |
///Return the scalar product of two vectors
|
alpar@2658
|
131 |
T operator *(const Point<T>& u) const {
|
alpar@2658
|
132 |
return x*u.x+y*u.y;
|
alpar@2658
|
133 |
}
|
alpar@2658
|
134 |
|
alpar@2658
|
135 |
///Return the sum of two vectors
|
alpar@2658
|
136 |
Point<T> operator+(const Point<T> &u) const {
|
alpar@2658
|
137 |
Point<T> b=*this;
|
alpar@2658
|
138 |
return b+=u;
|
alpar@2658
|
139 |
}
|
alpar@2658
|
140 |
|
alpar@2658
|
141 |
///Return the neg of the vectors
|
alpar@2658
|
142 |
Point<T> operator-() const {
|
alpar@2658
|
143 |
Point<T> b=*this;
|
alpar@2658
|
144 |
b.x=-b.x; b.y=-b.y;
|
alpar@2658
|
145 |
return b;
|
alpar@2658
|
146 |
}
|
alpar@2658
|
147 |
|
alpar@2658
|
148 |
///Return the difference of two vectors
|
alpar@2658
|
149 |
Point<T> operator-(const Point<T> &u) const {
|
alpar@2658
|
150 |
Point<T> b=*this;
|
alpar@2658
|
151 |
return b-=u;
|
alpar@2658
|
152 |
}
|
alpar@2658
|
153 |
|
alpar@2658
|
154 |
///Return a vector multiplied by a scalar
|
alpar@2658
|
155 |
Point<T> operator*(const T &u) const {
|
alpar@2658
|
156 |
Point<T> b=*this;
|
alpar@2658
|
157 |
return b*=u;
|
alpar@2658
|
158 |
}
|
alpar@2658
|
159 |
|
alpar@2658
|
160 |
///Return a vector divided by a scalar
|
alpar@2658
|
161 |
Point<T> operator/(const T &u) const {
|
alpar@2658
|
162 |
Point<T> b=*this;
|
alpar@2658
|
163 |
return b/=u;
|
alpar@2658
|
164 |
}
|
alpar@2658
|
165 |
|
alpar@2658
|
166 |
///Test equality
|
alpar@2658
|
167 |
bool operator==(const Point<T> &u) const {
|
alpar@2658
|
168 |
return (x==u.x) && (y==u.y);
|
alpar@2658
|
169 |
}
|
alpar@2658
|
170 |
|
alpar@2658
|
171 |
///Test inequality
|
alpar@2658
|
172 |
bool operator!=(Point u) const {
|
alpar@2658
|
173 |
return (x!=u.x) || (y!=u.y);
|
alpar@2658
|
174 |
}
|
alpar@2658
|
175 |
|
alpar@2658
|
176 |
};
|
alpar@2658
|
177 |
|
alpar@2658
|
178 |
///Return an Point
|
alpar@2658
|
179 |
|
alpar@2658
|
180 |
///Return an Point
|
alpar@2658
|
181 |
///\relates Point
|
alpar@2658
|
182 |
template <typename T>
|
alpar@2658
|
183 |
inline Point<T> makePoint(const T& x, const T& y) {
|
alpar@2658
|
184 |
return Point<T>(x, y);
|
alpar@2658
|
185 |
}
|
alpar@2658
|
186 |
|
alpar@2658
|
187 |
///Return a vector multiplied by a scalar
|
alpar@2658
|
188 |
|
alpar@2658
|
189 |
///Return a vector multiplied by a scalar
|
alpar@2658
|
190 |
///\relates Point
|
alpar@2658
|
191 |
template<typename T> Point<T> operator*(const T &u,const Point<T> &x) {
|
alpar@2658
|
192 |
return x*u;
|
alpar@2658
|
193 |
}
|
alpar@2658
|
194 |
|
alpar@2658
|
195 |
///Read a plainvector from a stream
|
alpar@2658
|
196 |
|
alpar@2658
|
197 |
///Read a plainvector from a stream
|
alpar@2658
|
198 |
///\relates Point
|
alpar@2658
|
199 |
///
|
alpar@2658
|
200 |
template<typename T>
|
alpar@2658
|
201 |
inline std::istream& operator>>(std::istream &is, Point<T> &z) {
|
alpar@2658
|
202 |
char c;
|
alpar@2658
|
203 |
if (is >> c) {
|
alpar@2658
|
204 |
if (c != '(') is.putback(c);
|
alpar@2658
|
205 |
} else {
|
alpar@2658
|
206 |
is.clear();
|
alpar@2658
|
207 |
}
|
alpar@2658
|
208 |
if (!(is >> z.x)) return is;
|
alpar@2658
|
209 |
if (is >> c) {
|
alpar@2658
|
210 |
if (c != ',') is.putback(c);
|
alpar@2658
|
211 |
} else {
|
alpar@2658
|
212 |
is.clear();
|
alpar@2658
|
213 |
}
|
alpar@2658
|
214 |
if (!(is >> z.y)) return is;
|
alpar@2658
|
215 |
if (is >> c) {
|
alpar@2658
|
216 |
if (c != ')') is.putback(c);
|
alpar@2658
|
217 |
} else {
|
alpar@2658
|
218 |
is.clear();
|
alpar@2658
|
219 |
}
|
alpar@2658
|
220 |
return is;
|
alpar@2658
|
221 |
}
|
alpar@2658
|
222 |
|
alpar@2658
|
223 |
///Write a plainvector to a stream
|
alpar@2658
|
224 |
|
alpar@2658
|
225 |
///Write a plainvector to a stream
|
alpar@2658
|
226 |
///\relates Point
|
alpar@2658
|
227 |
///
|
alpar@2658
|
228 |
template<typename T>
|
alpar@2658
|
229 |
inline std::ostream& operator<<(std::ostream &os, const Point<T>& z)
|
alpar@2658
|
230 |
{
|
alpar@2658
|
231 |
os << "(" << z.x << ", " << z.y << ")";
|
alpar@2658
|
232 |
return os;
|
alpar@2658
|
233 |
}
|
alpar@2658
|
234 |
|
alpar@2658
|
235 |
///Rotate by 90 degrees
|
alpar@2658
|
236 |
|
alpar@2658
|
237 |
///Returns its parameter rotated by 90 degrees in positive direction.
|
alpar@2658
|
238 |
///\relates Point
|
alpar@2658
|
239 |
///
|
alpar@2658
|
240 |
template<typename T>
|
alpar@2658
|
241 |
inline Point<T> rot90(const Point<T> &z)
|
alpar@2658
|
242 |
{
|
alpar@2658
|
243 |
return Point<T>(-z.y,z.x);
|
alpar@2658
|
244 |
}
|
alpar@2658
|
245 |
|
alpar@2658
|
246 |
///Rotate by 180 degrees
|
alpar@2658
|
247 |
|
alpar@2658
|
248 |
///Returns its parameter rotated by 180 degrees.
|
alpar@2658
|
249 |
///\relates Point
|
alpar@2658
|
250 |
///
|
alpar@2658
|
251 |
template<typename T>
|
alpar@2658
|
252 |
inline Point<T> rot180(const Point<T> &z)
|
alpar@2658
|
253 |
{
|
alpar@2658
|
254 |
return Point<T>(-z.x,-z.y);
|
alpar@2658
|
255 |
}
|
alpar@2658
|
256 |
|
alpar@2658
|
257 |
///Rotate by 270 degrees
|
alpar@2658
|
258 |
|
alpar@2658
|
259 |
///Returns its parameter rotated by 90 degrees in negative direction.
|
alpar@2658
|
260 |
///\relates Point
|
alpar@2658
|
261 |
///
|
alpar@2658
|
262 |
template<typename T>
|
alpar@2658
|
263 |
inline Point<T> rot270(const Point<T> &z)
|
alpar@2658
|
264 |
{
|
alpar@2658
|
265 |
return Point<T>(z.y,-z.x);
|
alpar@2658
|
266 |
}
|
alpar@2658
|
267 |
|
alpar@2658
|
268 |
|
alpar@2658
|
269 |
|
alpar@2658
|
270 |
/// A class to calculate or store the bounding box of plainvectors.
|
alpar@2658
|
271 |
|
alpar@2658
|
272 |
/// A class to calculate or store the bounding box of plainvectors.
|
alpar@2658
|
273 |
///
|
alpar@2658
|
274 |
///\author Attila Bernath
|
alpar@2658
|
275 |
template<typename T>
|
alpar@2658
|
276 |
class BoundingBox {
|
alpar@2658
|
277 |
Point<T> bottom_left, top_right;
|
alpar@2658
|
278 |
bool _empty;
|
alpar@2658
|
279 |
public:
|
alpar@2658
|
280 |
|
alpar@2658
|
281 |
///Default constructor: creates an empty bounding box
|
alpar@2658
|
282 |
BoundingBox() { _empty = true; }
|
alpar@2658
|
283 |
|
alpar@2658
|
284 |
///Construct an instance from one point
|
alpar@2658
|
285 |
BoundingBox(Point<T> a) { bottom_left=top_right=a; _empty = false; }
|
alpar@2658
|
286 |
|
alpar@2658
|
287 |
///Were any points added?
|
alpar@2658
|
288 |
bool empty() const {
|
alpar@2658
|
289 |
return _empty;
|
alpar@2658
|
290 |
}
|
alpar@2658
|
291 |
|
alpar@2658
|
292 |
///Make the BoundingBox empty
|
alpar@2658
|
293 |
void clear() {
|
alpar@2658
|
294 |
_empty=1;
|
alpar@2658
|
295 |
}
|
alpar@2658
|
296 |
|
alpar@2658
|
297 |
///Give back the bottom left corner
|
alpar@2658
|
298 |
|
alpar@2658
|
299 |
///Give back the bottom left corner.
|
alpar@2658
|
300 |
///If the bounding box is empty, then the return value is not defined.
|
alpar@2658
|
301 |
Point<T> bottomLeft() const {
|
alpar@2658
|
302 |
return bottom_left;
|
alpar@2658
|
303 |
}
|
alpar@2658
|
304 |
|
alpar@2658
|
305 |
///Set the bottom left corner
|
alpar@2658
|
306 |
|
alpar@2658
|
307 |
///Set the bottom left corner.
|
alpar@2658
|
308 |
///It should only bee used for non-empty box.
|
alpar@2658
|
309 |
void bottomLeft(Point<T> p) {
|
alpar@2658
|
310 |
bottom_left = p;
|
alpar@2658
|
311 |
}
|
alpar@2658
|
312 |
|
alpar@2658
|
313 |
///Give back the top right corner
|
alpar@2658
|
314 |
|
alpar@2658
|
315 |
///Give back the top right corner.
|
alpar@2658
|
316 |
///If the bounding box is empty, then the return value is not defined.
|
alpar@2658
|
317 |
Point<T> topRight() const {
|
alpar@2658
|
318 |
return top_right;
|
alpar@2658
|
319 |
}
|
alpar@2658
|
320 |
|
alpar@2658
|
321 |
///Set the top right corner
|
alpar@2658
|
322 |
|
alpar@2658
|
323 |
///Set the top right corner.
|
alpar@2658
|
324 |
///It should only bee used for non-empty box.
|
alpar@2658
|
325 |
void topRight(Point<T> p) {
|
alpar@2658
|
326 |
top_right = p;
|
alpar@2658
|
327 |
}
|
alpar@2658
|
328 |
|
alpar@2658
|
329 |
///Give back the bottom right corner
|
alpar@2658
|
330 |
|
alpar@2658
|
331 |
///Give back the bottom right corner.
|
alpar@2658
|
332 |
///If the bounding box is empty, then the return value is not defined.
|
alpar@2658
|
333 |
Point<T> bottomRight() const {
|
alpar@2658
|
334 |
return Point<T>(top_right.x,bottom_left.y);
|
alpar@2658
|
335 |
}
|
alpar@2658
|
336 |
|
alpar@2658
|
337 |
///Set the bottom right corner
|
alpar@2658
|
338 |
|
alpar@2658
|
339 |
///Set the bottom right corner.
|
alpar@2658
|
340 |
///It should only bee used for non-empty box.
|
alpar@2658
|
341 |
void bottomRight(Point<T> p) {
|
alpar@2658
|
342 |
top_right.x = p.x;
|
alpar@2658
|
343 |
bottom_left.y = p.y;
|
alpar@2658
|
344 |
}
|
alpar@2658
|
345 |
|
alpar@2658
|
346 |
///Give back the top left corner
|
alpar@2658
|
347 |
|
alpar@2658
|
348 |
///Give back the top left corner.
|
alpar@2658
|
349 |
///If the bounding box is empty, then the return value is not defined.
|
alpar@2658
|
350 |
Point<T> topLeft() const {
|
alpar@2658
|
351 |
return Point<T>(bottom_left.x,top_right.y);
|
alpar@2658
|
352 |
}
|
alpar@2658
|
353 |
|
alpar@2658
|
354 |
///Set the top left corner
|
alpar@2658
|
355 |
|
alpar@2658
|
356 |
///Set the top left corner.
|
alpar@2658
|
357 |
///It should only bee used for non-empty box.
|
alpar@2658
|
358 |
void topLeft(Point<T> p) {
|
alpar@2658
|
359 |
top_right.y = p.y;
|
alpar@2658
|
360 |
bottom_left.x = p.x;
|
alpar@2658
|
361 |
}
|
alpar@2658
|
362 |
|
alpar@2658
|
363 |
///Give back the bottom of the box
|
alpar@2658
|
364 |
|
alpar@2658
|
365 |
///Give back the bottom of the box.
|
alpar@2658
|
366 |
///If the bounding box is empty, then the return value is not defined.
|
alpar@2658
|
367 |
T bottom() const {
|
alpar@2658
|
368 |
return bottom_left.y;
|
alpar@2658
|
369 |
}
|
alpar@2658
|
370 |
|
alpar@2658
|
371 |
///Set the bottom of the box
|
alpar@2658
|
372 |
|
alpar@2658
|
373 |
///Set the bottom of the box.
|
alpar@2658
|
374 |
///It should only bee used for non-empty box.
|
alpar@2658
|
375 |
void bottom(T t) {
|
alpar@2658
|
376 |
bottom_left.y = t;
|
alpar@2658
|
377 |
}
|
alpar@2658
|
378 |
|
alpar@2658
|
379 |
///Give back the top of the box
|
alpar@2658
|
380 |
|
alpar@2658
|
381 |
///Give back the top of the box.
|
alpar@2658
|
382 |
///If the bounding box is empty, then the return value is not defined.
|
alpar@2658
|
383 |
T top() const {
|
alpar@2658
|
384 |
return top_right.y;
|
alpar@2658
|
385 |
}
|
alpar@2658
|
386 |
|
alpar@2658
|
387 |
///Set the top of the box
|
alpar@2658
|
388 |
|
alpar@2658
|
389 |
///Set the top of the box.
|
alpar@2658
|
390 |
///It should only bee used for non-empty box.
|
alpar@2658
|
391 |
void top(T t) {
|
alpar@2658
|
392 |
top_right.y = t;
|
alpar@2658
|
393 |
}
|
alpar@2658
|
394 |
|
alpar@2658
|
395 |
///Give back the left side of the box
|
alpar@2658
|
396 |
|
alpar@2658
|
397 |
///Give back the left side of the box.
|
alpar@2658
|
398 |
///If the bounding box is empty, then the return value is not defined.
|
alpar@2658
|
399 |
T left() const {
|
alpar@2658
|
400 |
return bottom_left.x;
|
alpar@2658
|
401 |
}
|
alpar@2658
|
402 |
|
alpar@2658
|
403 |
///Set the left side of the box
|
alpar@2658
|
404 |
|
alpar@2658
|
405 |
///Set the left side of the box.
|
alpar@2658
|
406 |
///It should only bee used for non-empty box
|
alpar@2658
|
407 |
void left(T t) {
|
alpar@2658
|
408 |
bottom_left.x = t;
|
alpar@2658
|
409 |
}
|
alpar@2658
|
410 |
|
alpar@2658
|
411 |
/// Give back the right side of the box
|
alpar@2658
|
412 |
|
alpar@2658
|
413 |
/// Give back the right side of the box.
|
alpar@2658
|
414 |
///If the bounding box is empty, then the return value is not defined.
|
alpar@2658
|
415 |
T right() const {
|
alpar@2658
|
416 |
return top_right.x;
|
alpar@2658
|
417 |
}
|
alpar@2658
|
418 |
|
alpar@2658
|
419 |
///Set the right side of the box
|
alpar@2658
|
420 |
|
alpar@2658
|
421 |
///Set the right side of the box.
|
alpar@2658
|
422 |
///It should only bee used for non-empty box
|
alpar@2658
|
423 |
void right(T t) {
|
alpar@2658
|
424 |
top_right.x = t;
|
alpar@2658
|
425 |
}
|
alpar@2658
|
426 |
|
alpar@2658
|
427 |
///Give back the height of the box
|
alpar@2658
|
428 |
|
alpar@2658
|
429 |
///Give back the height of the box.
|
alpar@2658
|
430 |
///If the bounding box is empty, then the return value is not defined.
|
alpar@2658
|
431 |
T height() const {
|
alpar@2658
|
432 |
return top_right.y-bottom_left.y;
|
alpar@2658
|
433 |
}
|
alpar@2658
|
434 |
|
alpar@2658
|
435 |
///Give back the width of the box
|
alpar@2658
|
436 |
|
alpar@2658
|
437 |
///Give back the width of the box.
|
alpar@2658
|
438 |
///If the bounding box is empty, then the return value is not defined.
|
alpar@2658
|
439 |
T width() const {
|
alpar@2658
|
440 |
return top_right.x-bottom_left.x;
|
alpar@2658
|
441 |
}
|
alpar@2658
|
442 |
|
alpar@2658
|
443 |
///Checks whether a point is inside a bounding box
|
alpar@2658
|
444 |
bool inside(const Point<T>& u){
|
alpar@2658
|
445 |
if (_empty)
|
alpar@2658
|
446 |
return false;
|
alpar@2658
|
447 |
else{
|
alpar@2658
|
448 |
return ((u.x-bottom_left.x)*(top_right.x-u.x) >= 0 &&
|
alpar@2658
|
449 |
(u.y-bottom_left.y)*(top_right.y-u.y) >= 0 );
|
alpar@2658
|
450 |
}
|
alpar@2658
|
451 |
}
|
alpar@2658
|
452 |
|
alpar@2658
|
453 |
///Increments a bounding box with a point
|
alpar@2658
|
454 |
BoundingBox& add(const Point<T>& u){
|
alpar@2658
|
455 |
if (_empty){
|
alpar@2658
|
456 |
bottom_left=top_right=u;
|
alpar@2658
|
457 |
_empty = false;
|
alpar@2658
|
458 |
}
|
alpar@2658
|
459 |
else{
|
alpar@2658
|
460 |
if (bottom_left.x > u.x) bottom_left.x = u.x;
|
alpar@2658
|
461 |
if (bottom_left.y > u.y) bottom_left.y = u.y;
|
alpar@2658
|
462 |
if (top_right.x < u.x) top_right.x = u.x;
|
alpar@2658
|
463 |
if (top_right.y < u.y) top_right.y = u.y;
|
alpar@2658
|
464 |
}
|
alpar@2658
|
465 |
return *this;
|
alpar@2658
|
466 |
}
|
alpar@2658
|
467 |
|
alpar@2658
|
468 |
///Increments a bounding to contain another bounding box
|
alpar@2658
|
469 |
BoundingBox& add(const BoundingBox &u){
|
alpar@2658
|
470 |
if ( !u.empty() ){
|
alpar@2658
|
471 |
this->add(u.bottomLeft());
|
alpar@2658
|
472 |
this->add(u.topRight());
|
alpar@2658
|
473 |
}
|
alpar@2658
|
474 |
return *this;
|
alpar@2658
|
475 |
}
|
alpar@2658
|
476 |
|
alpar@2658
|
477 |
///Intersection of two bounding boxes
|
alpar@2658
|
478 |
BoundingBox operator &(const BoundingBox& u){
|
alpar@2658
|
479 |
BoundingBox b;
|
alpar@2658
|
480 |
b.bottom_left.x=std::max(this->bottom_left.x,u.bottom_left.x);
|
alpar@2658
|
481 |
b.bottom_left.y=std::max(this->bottom_left.y,u.bottom_left.y);
|
alpar@2658
|
482 |
b.top_right.x=std::min(this->top_right.x,u.top_right.x);
|
alpar@2658
|
483 |
b.top_right.y=std::min(this->top_right.y,u.top_right.y);
|
alpar@2658
|
484 |
b._empty = this->_empty || u._empty ||
|
alpar@2658
|
485 |
b.bottom_left.x>top_right.x && b.bottom_left.y>top_right.y;
|
alpar@2658
|
486 |
return b;
|
alpar@2658
|
487 |
}
|
alpar@2658
|
488 |
|
alpar@2658
|
489 |
};//class Boundingbox
|
alpar@2658
|
490 |
|
alpar@2658
|
491 |
|
alpar@2658
|
492 |
///Map of x-coordinates of a dim2::Point<>-map
|
alpar@2658
|
493 |
|
alpar@2658
|
494 |
///\ingroup maps
|
alpar@2658
|
495 |
///Map of x-coordinates of a dim2::Point<>-map
|
alpar@2658
|
496 |
///
|
alpar@2658
|
497 |
template<class M>
|
alpar@2658
|
498 |
class XMap
|
alpar@2658
|
499 |
{
|
alpar@2658
|
500 |
M& _map;
|
alpar@2658
|
501 |
public:
|
alpar@2658
|
502 |
|
alpar@2658
|
503 |
typedef typename M::Value::Value Value;
|
alpar@2658
|
504 |
typedef typename M::Key Key;
|
alpar@2658
|
505 |
///\e
|
alpar@2658
|
506 |
XMap(M& map) : _map(map) {}
|
alpar@2658
|
507 |
Value operator[](Key k) const {return _map[k].x;}
|
alpar@2658
|
508 |
void set(Key k,Value v) {_map.set(k,typename M::Value(v,_map[k].y));}
|
alpar@2658
|
509 |
};
|
alpar@2658
|
510 |
|
alpar@2658
|
511 |
///Returns an \ref XMap class
|
alpar@2658
|
512 |
|
alpar@2658
|
513 |
///This function just returns an \ref XMap class.
|
alpar@2658
|
514 |
///
|
alpar@2658
|
515 |
///\ingroup maps
|
alpar@2658
|
516 |
///\relates XMap
|
alpar@2658
|
517 |
template<class M>
|
alpar@2658
|
518 |
inline XMap<M> xMap(M &m)
|
alpar@2658
|
519 |
{
|
alpar@2658
|
520 |
return XMap<M>(m);
|
alpar@2658
|
521 |
}
|
alpar@2658
|
522 |
|
alpar@2658
|
523 |
template<class M>
|
alpar@2658
|
524 |
inline XMap<M> xMap(const M &m)
|
alpar@2658
|
525 |
{
|
alpar@2658
|
526 |
return XMap<M>(m);
|
alpar@2658
|
527 |
}
|
alpar@2658
|
528 |
|
alpar@2658
|
529 |
///Constant (read only) version of \ref XMap
|
alpar@2658
|
530 |
|
alpar@2658
|
531 |
///\ingroup maps
|
alpar@2658
|
532 |
///Constant (read only) version of \ref XMap
|
alpar@2658
|
533 |
///
|
alpar@2658
|
534 |
template<class M>
|
alpar@2658
|
535 |
class ConstXMap
|
alpar@2658
|
536 |
{
|
alpar@2658
|
537 |
const M& _map;
|
alpar@2658
|
538 |
public:
|
alpar@2658
|
539 |
|
alpar@2658
|
540 |
typedef typename M::Value::Value Value;
|
alpar@2658
|
541 |
typedef typename M::Key Key;
|
alpar@2658
|
542 |
///\e
|
alpar@2658
|
543 |
ConstXMap(const M &map) : _map(map) {}
|
alpar@2658
|
544 |
Value operator[](Key k) const {return _map[k].x;}
|
alpar@2658
|
545 |
};
|
alpar@2658
|
546 |
|
alpar@2658
|
547 |
///Returns a \ref ConstXMap class
|
alpar@2658
|
548 |
|
alpar@2658
|
549 |
///This function just returns an \ref ConstXMap class.
|
alpar@2658
|
550 |
///
|
alpar@2658
|
551 |
///\ingroup maps
|
alpar@2658
|
552 |
///\relates ConstXMap
|
alpar@2658
|
553 |
template<class M>
|
alpar@2658
|
554 |
inline ConstXMap<M> xMap(const M &m)
|
alpar@2658
|
555 |
{
|
alpar@2658
|
556 |
return ConstXMap<M>(m);
|
alpar@2658
|
557 |
}
|
alpar@2658
|
558 |
|
alpar@2658
|
559 |
///Map of y-coordinates of a dim2::Point<>-map
|
alpar@2658
|
560 |
|
alpar@2658
|
561 |
///\ingroup maps
|
alpar@2658
|
562 |
///Map of y-coordinates of a dim2::Point<>-map
|
alpar@2658
|
563 |
///
|
alpar@2658
|
564 |
template<class M>
|
alpar@2658
|
565 |
class YMap
|
alpar@2658
|
566 |
{
|
alpar@2658
|
567 |
M& _map;
|
alpar@2658
|
568 |
public:
|
alpar@2658
|
569 |
|
alpar@2658
|
570 |
typedef typename M::Value::Value Value;
|
alpar@2658
|
571 |
typedef typename M::Key Key;
|
alpar@2658
|
572 |
///\e
|
alpar@2658
|
573 |
YMap(M& map) : _map(map) {}
|
alpar@2658
|
574 |
Value operator[](Key k) const {return _map[k].y;}
|
alpar@2658
|
575 |
void set(Key k,Value v) {_map.set(k,typename M::Value(_map[k].x,v));}
|
alpar@2658
|
576 |
};
|
alpar@2658
|
577 |
|
alpar@2658
|
578 |
///Returns an \ref YMap class
|
alpar@2658
|
579 |
|
alpar@2658
|
580 |
///This function just returns an \ref YMap class.
|
alpar@2658
|
581 |
///
|
alpar@2658
|
582 |
///\ingroup maps
|
alpar@2658
|
583 |
///\relates YMap
|
alpar@2658
|
584 |
template<class M>
|
alpar@2658
|
585 |
inline YMap<M> yMap(M &m)
|
alpar@2658
|
586 |
{
|
alpar@2658
|
587 |
return YMap<M>(m);
|
alpar@2658
|
588 |
}
|
alpar@2658
|
589 |
|
alpar@2658
|
590 |
template<class M>
|
alpar@2658
|
591 |
inline YMap<M> yMap(const M &m)
|
alpar@2658
|
592 |
{
|
alpar@2658
|
593 |
return YMap<M>(m);
|
alpar@2658
|
594 |
}
|
alpar@2658
|
595 |
|
alpar@2658
|
596 |
///Constant (read only) version of \ref YMap
|
alpar@2658
|
597 |
|
alpar@2658
|
598 |
///\ingroup maps
|
alpar@2658
|
599 |
///Constant (read only) version of \ref YMap
|
alpar@2658
|
600 |
///
|
alpar@2658
|
601 |
template<class M>
|
alpar@2658
|
602 |
class ConstYMap
|
alpar@2658
|
603 |
{
|
alpar@2658
|
604 |
const M& _map;
|
alpar@2658
|
605 |
public:
|
alpar@2658
|
606 |
|
alpar@2658
|
607 |
typedef typename M::Value::Value Value;
|
alpar@2658
|
608 |
typedef typename M::Key Key;
|
alpar@2658
|
609 |
///\e
|
alpar@2658
|
610 |
ConstYMap(const M &map) : _map(map) {}
|
alpar@2658
|
611 |
Value operator[](Key k) const {return _map[k].y;}
|
alpar@2658
|
612 |
};
|
alpar@2658
|
613 |
|
alpar@2658
|
614 |
///Returns a \ref ConstYMap class
|
alpar@2658
|
615 |
|
alpar@2658
|
616 |
///This function just returns an \ref ConstYMap class.
|
alpar@2658
|
617 |
///
|
alpar@2658
|
618 |
///\ingroup maps
|
alpar@2658
|
619 |
///\relates ConstYMap
|
alpar@2658
|
620 |
template<class M>
|
alpar@2658
|
621 |
inline ConstYMap<M> yMap(const M &m)
|
alpar@2658
|
622 |
{
|
alpar@2658
|
623 |
return ConstYMap<M>(m);
|
alpar@2658
|
624 |
}
|
alpar@2658
|
625 |
|
alpar@2658
|
626 |
|
alpar@2658
|
627 |
///\brief Map of the \ref Point::normSquare() "normSquare()"
|
alpar@2658
|
628 |
///of an \ref Point "Point"-map
|
alpar@2658
|
629 |
///
|
alpar@2658
|
630 |
///Map of the \ref Point::normSquare() "normSquare()"
|
alpar@2658
|
631 |
///of an \ref Point "Point"-map
|
alpar@2658
|
632 |
///\ingroup maps
|
alpar@2658
|
633 |
///
|
alpar@2658
|
634 |
template<class M>
|
alpar@2658
|
635 |
class NormSquareMap
|
alpar@2658
|
636 |
{
|
alpar@2658
|
637 |
const M& _map;
|
alpar@2658
|
638 |
public:
|
alpar@2658
|
639 |
|
alpar@2658
|
640 |
typedef typename M::Value::Value Value;
|
alpar@2658
|
641 |
typedef typename M::Key Key;
|
alpar@2658
|
642 |
///\e
|
alpar@2658
|
643 |
NormSquareMap(const M &map) : _map(map) {}
|
alpar@2658
|
644 |
Value operator[](Key k) const {return _map[k].normSquare();}
|
alpar@2658
|
645 |
};
|
alpar@2658
|
646 |
|
alpar@2658
|
647 |
///Returns a \ref NormSquareMap class
|
alpar@2658
|
648 |
|
alpar@2658
|
649 |
///This function just returns an \ref NormSquareMap class.
|
alpar@2658
|
650 |
///
|
alpar@2658
|
651 |
///\ingroup maps
|
alpar@2658
|
652 |
///\relates NormSquareMap
|
alpar@2658
|
653 |
template<class M>
|
alpar@2658
|
654 |
inline NormSquareMap<M> normSquareMap(const M &m)
|
alpar@2658
|
655 |
{
|
alpar@2658
|
656 |
return NormSquareMap<M>(m);
|
alpar@2658
|
657 |
}
|
alpar@2658
|
658 |
|
alpar@2658
|
659 |
/// @}
|
alpar@2658
|
660 |
|
alpar@2658
|
661 |
} //namespce dim2
|
alpar@2658
|
662 |
|
alpar@2658
|
663 |
} //namespace lemon
|
alpar@2658
|
664 |
|
alpar@2658
|
665 |
#endif //LEMON_DIM2_H
|