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