0
3
0
| 1 | 1 |
/* -*- mode: C++; indent-tabs-mode: nil; -*- |
| 2 | 2 |
* |
| 3 | 3 |
* This file is a part of LEMON, a generic C++ optimization library. |
| 4 | 4 |
* |
| 5 | 5 |
* Copyright (C) 2003-2008 |
| 6 | 6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
| 7 | 7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES). |
| 8 | 8 |
* |
| 9 | 9 |
* Permission to use, modify and distribute this software is granted |
| 10 | 10 |
* provided that this copyright notice appears in all copies. For |
| 11 | 11 |
* precise terms see the accompanying LICENSE file. |
| 12 | 12 |
* |
| 13 | 13 |
* This software is provided "AS IS" with no warranty of any kind, |
| 14 | 14 |
* express or implied, and with no claim as to its suitability for any |
| 15 | 15 |
* purpose. |
| 16 | 16 |
* |
| 17 | 17 |
*/ |
| 18 | 18 |
|
| 19 | 19 |
#ifndef LEMON_DIM2_H |
| 20 | 20 |
#define LEMON_DIM2_H |
| 21 | 21 |
|
| 22 | 22 |
#include <iostream> |
| 23 | 23 |
|
| 24 | 24 |
///\ingroup misc |
| 25 | 25 |
///\file |
| 26 | 26 |
///\brief A simple two dimensional vector and a bounding box implementation |
| 27 | 27 |
/// |
| 28 | 28 |
/// The class \ref lemon::dim2::Point "dim2::Point" implements |
| 29 | 29 |
/// a two dimensional vector with the usual operations. |
| 30 | 30 |
/// |
| 31 |
/// The class \ref lemon::dim2::BoundingBox "dim2::BoundingBox" |
|
| 32 |
/// can be used to determine |
|
| 31 |
/// The class \ref lemon::dim2::Box "dim2::Box" can be used to determine |
|
| 33 | 32 |
/// the rectangular bounding box of a set of |
| 34 | 33 |
/// \ref lemon::dim2::Point "dim2::Point"'s. |
| 35 | 34 |
|
| 36 | 35 |
namespace lemon {
|
| 37 | 36 |
|
| 38 | 37 |
///Tools for handling two dimensional coordinates |
| 39 | 38 |
|
| 40 | 39 |
///This namespace is a storage of several |
| 41 | 40 |
///tools for handling two dimensional coordinates |
| 42 | 41 |
namespace dim2 {
|
| 43 | 42 |
|
| 44 | 43 |
/// \addtogroup misc |
| 45 | 44 |
/// @{
|
| 46 | 45 |
|
| 47 |
/// |
|
| 46 |
/// Two dimensional vector (plain vector) |
|
| 48 | 47 |
|
| 49 | 48 |
/// A simple two dimensional vector (plain vector) implementation |
| 50 | 49 |
/// with the usual vector operations. |
| 51 | 50 |
template<typename T> |
| 52 | 51 |
class Point {
|
| 53 | 52 |
|
| 54 | 53 |
public: |
| 55 | 54 |
|
| 56 | 55 |
typedef T Value; |
| 57 | 56 |
|
| 58 | 57 |
///First coordinate |
| 59 | 58 |
T x; |
| 60 | 59 |
///Second coordinate |
| 61 | 60 |
T y; |
| 62 | 61 |
|
| 63 | 62 |
///Default constructor |
| 64 | 63 |
Point() {}
|
| 65 | 64 |
|
| 66 | 65 |
///Construct an instance from coordinates |
| 67 | 66 |
Point(T a, T b) : x(a), y(b) { }
|
| 68 | 67 |
|
| 69 | 68 |
///Returns the dimension of the vector (i.e. returns 2). |
| 70 | 69 |
|
| 71 | 70 |
///The dimension of the vector. |
| 72 | 71 |
///This function always returns 2. |
| 73 | 72 |
int size() const { return 2; }
|
| 74 | 73 |
|
| 75 | 74 |
///Subscripting operator |
| 76 | 75 |
|
| 77 | 76 |
///\c p[0] is \c p.x and \c p[1] is \c p.y |
| 78 | 77 |
/// |
| 79 | 78 |
T& operator[](int idx) { return idx == 0 ? x : y; }
|
| 80 | 79 |
|
| 81 | 80 |
///Const subscripting operator |
| 82 | 81 |
|
| 83 | 82 |
///\c p[0] is \c p.x and \c p[1] is \c p.y |
| 84 | 83 |
/// |
| 85 | 84 |
const T& operator[](int idx) const { return idx == 0 ? x : y; }
|
| 86 | 85 |
|
| 87 | 86 |
///Conversion constructor |
| 88 | 87 |
template<class TT> Point(const Point<TT> &p) : x(p.x), y(p.y) {}
|
| 89 | 88 |
|
| 90 | 89 |
///Give back the square of the norm of the vector |
| 91 | 90 |
T normSquare() const {
|
| 92 | 91 |
return x*x+y*y; |
| 93 | 92 |
} |
| 94 | 93 |
|
| 95 | 94 |
///Increment the left hand side by \c u |
| 96 | 95 |
Point<T>& operator +=(const Point<T>& u) {
|
| 97 | 96 |
x += u.x; |
| 98 | 97 |
y += u.y; |
| 99 | 98 |
return *this; |
| 100 | 99 |
} |
| 101 | 100 |
|
| 102 | 101 |
///Decrement the left hand side by \c u |
| 103 | 102 |
Point<T>& operator -=(const Point<T>& u) {
|
| 104 | 103 |
x -= u.x; |
| 105 | 104 |
y -= u.y; |
| 106 | 105 |
return *this; |
| 107 | 106 |
} |
| 108 | 107 |
|
| 109 | 108 |
///Multiply the left hand side with a scalar |
| 110 | 109 |
Point<T>& operator *=(const T &u) {
|
| 111 | 110 |
x *= u; |
| 112 | 111 |
y *= u; |
| 113 | 112 |
return *this; |
| 114 | 113 |
} |
| 115 | 114 |
|
| 116 | 115 |
///Divide the left hand side by a scalar |
| 117 | 116 |
Point<T>& operator /=(const T &u) {
|
| 118 | 117 |
x /= u; |
| 119 | 118 |
y /= u; |
| 120 | 119 |
return *this; |
| 121 | 120 |
} |
| 122 | 121 |
|
| 123 | 122 |
///Return the scalar product of two vectors |
| 124 | 123 |
T operator *(const Point<T>& u) const {
|
| 125 | 124 |
return x*u.x+y*u.y; |
| 126 | 125 |
} |
| 127 | 126 |
|
| 128 | 127 |
///Return the sum of two vectors |
| 129 | 128 |
Point<T> operator+(const Point<T> &u) const {
|
| 130 | 129 |
Point<T> b=*this; |
| 131 | 130 |
return b+=u; |
| 132 | 131 |
} |
| 133 | 132 |
|
| 134 | 133 |
///Return the negative of the vector |
| 135 | 134 |
Point<T> operator-() const {
|
| 136 | 135 |
Point<T> b=*this; |
| 137 | 136 |
b.x=-b.x; b.y=-b.y; |
| 138 | 137 |
return b; |
| 139 | 138 |
} |
| 140 | 139 |
|
| 141 | 140 |
///Return the difference of two vectors |
| 142 | 141 |
Point<T> operator-(const Point<T> &u) const {
|
| 143 | 142 |
Point<T> b=*this; |
| 144 | 143 |
return b-=u; |
| 145 | 144 |
} |
| 146 | 145 |
|
| 147 | 146 |
///Return a vector multiplied by a scalar |
| 148 | 147 |
Point<T> operator*(const T &u) const {
|
| 149 | 148 |
Point<T> b=*this; |
| 150 | 149 |
return b*=u; |
| 151 | 150 |
} |
| 152 | 151 |
|
| 153 | 152 |
///Return a vector divided by a scalar |
| 154 | 153 |
Point<T> operator/(const T &u) const {
|
| 155 | 154 |
Point<T> b=*this; |
| 156 | 155 |
return b/=u; |
| 157 | 156 |
} |
| 158 | 157 |
|
| 159 | 158 |
///Test equality |
| 160 | 159 |
bool operator==(const Point<T> &u) const {
|
| 161 | 160 |
return (x==u.x) && (y==u.y); |
| 162 | 161 |
} |
| 163 | 162 |
|
| 164 | 163 |
///Test inequality |
| 165 | 164 |
bool operator!=(Point u) const {
|
| 166 | 165 |
return (x!=u.x) || (y!=u.y); |
| 167 | 166 |
} |
| 168 | 167 |
|
| 169 | 168 |
}; |
| 170 | 169 |
|
| 171 | 170 |
///Return a Point |
| 172 | 171 |
|
| 173 | 172 |
///Return a Point. |
| 174 | 173 |
///\relates Point |
| 175 | 174 |
template <typename T> |
| 176 | 175 |
inline Point<T> makePoint(const T& x, const T& y) {
|
| 177 | 176 |
return Point<T>(x, y); |
| 178 | 177 |
} |
| 179 | 178 |
|
| 180 | 179 |
///Return a vector multiplied by a scalar |
| 181 | 180 |
|
| 182 | 181 |
///Return a vector multiplied by a scalar. |
| 183 | 182 |
///\relates Point |
| 184 | 183 |
template<typename T> Point<T> operator*(const T &u,const Point<T> &x) {
|
| 185 | 184 |
return x*u; |
| 186 | 185 |
} |
| 187 | 186 |
|
| 188 | 187 |
///Read a plain vector from a stream |
| 189 | 188 |
|
| 190 | 189 |
///Read a plain vector from a stream. |
| 191 | 190 |
///\relates Point |
| 192 | 191 |
/// |
| 193 | 192 |
template<typename T> |
| 194 | 193 |
inline std::istream& operator>>(std::istream &is, Point<T> &z) {
|
| 195 | 194 |
char c; |
| 196 | 195 |
if (is >> c) {
|
| 197 | 196 |
if (c != '(') is.putback(c);
|
| 198 | 197 |
} else {
|
| 199 | 198 |
is.clear(); |
| 200 | 199 |
} |
| 201 | 200 |
if (!(is >> z.x)) return is; |
| 202 | 201 |
if (is >> c) {
|
| 203 | 202 |
if (c != ',') is.putback(c); |
| 204 | 203 |
} else {
|
| 205 | 204 |
is.clear(); |
| 206 | 205 |
} |
| 207 | 206 |
if (!(is >> z.y)) return is; |
| 208 | 207 |
if (is >> c) {
|
| 209 | 208 |
if (c != ')') is.putback(c); |
| 210 | 209 |
} else {
|
| 211 | 210 |
is.clear(); |
| 212 | 211 |
} |
| 213 | 212 |
return is; |
| 214 | 213 |
} |
| 215 | 214 |
|
| 216 | 215 |
///Write a plain vector to a stream |
| 217 | 216 |
|
| 218 | 217 |
///Write a plain vector to a stream. |
| 219 | 218 |
///\relates Point |
| 220 | 219 |
/// |
| 221 | 220 |
template<typename T> |
| 222 | 221 |
inline std::ostream& operator<<(std::ostream &os, const Point<T>& z) |
| 223 | 222 |
{
|
| 224 | 223 |
os << "(" << z.x << "," << z.y << ")";
|
| 225 | 224 |
return os; |
| 226 | 225 |
} |
| 227 | 226 |
|
| 228 | 227 |
///Rotate by 90 degrees |
| 229 | 228 |
|
| 230 | 229 |
///Returns the parameter rotated by 90 degrees in positive direction. |
| 231 | 230 |
///\relates Point |
| 232 | 231 |
/// |
| 233 | 232 |
template<typename T> |
| 234 | 233 |
inline Point<T> rot90(const Point<T> &z) |
| 235 | 234 |
{
|
| 236 | 235 |
return Point<T>(-z.y,z.x); |
| 237 | 236 |
} |
| 238 | 237 |
|
| 239 | 238 |
///Rotate by 180 degrees |
| 240 | 239 |
|
| 241 | 240 |
///Returns the parameter rotated by 180 degrees. |
| 242 | 241 |
///\relates Point |
| 243 | 242 |
/// |
| 244 | 243 |
template<typename T> |
| 245 | 244 |
inline Point<T> rot180(const Point<T> &z) |
| 246 | 245 |
{
|
| 247 | 246 |
return Point<T>(-z.x,-z.y); |
| 248 | 247 |
} |
| 249 | 248 |
|
| 250 | 249 |
///Rotate by 270 degrees |
| 251 | 250 |
|
| 252 | 251 |
///Returns the parameter rotated by 90 degrees in negative direction. |
| 253 | 252 |
///\relates Point |
| 254 | 253 |
/// |
| 255 | 254 |
template<typename T> |
| 256 | 255 |
inline Point<T> rot270(const Point<T> &z) |
| 257 | 256 |
{
|
| 258 | 257 |
return Point<T>(z.y,-z.x); |
| 259 | 258 |
} |
| 260 | 259 |
|
| 261 | 260 |
|
| 262 | 261 |
|
| 263 |
|
|
| 262 |
/// Bounding box of plain vectors (\ref Point points). |
|
| 264 | 263 |
|
| 265 |
/// A class to calculate or store the bounding box of plain vectors. |
|
| 266 |
/// |
|
| 267 |
template<typename T> |
|
| 268 |
class BoundingBox {
|
|
| 264 |
/// A class to calculate or store the bounding box of plain vectors |
|
| 265 |
/// (\ref Point points). |
|
| 266 |
template<typename T> |
|
| 267 |
class Box {
|
|
| 269 | 268 |
Point<T> _bottom_left, _top_right; |
| 270 | 269 |
bool _empty; |
| 271 | 270 |
public: |
| 272 | 271 |
|
| 273 |
///Default constructor: creates an empty bounding box |
|
| 274 |
BoundingBox() { _empty = true; }
|
|
| 272 |
///Default constructor: creates an empty box |
|
| 273 |
Box() { _empty = true; }
|
|
| 275 | 274 |
|
| 276 |
///Construct an instance from one point |
|
| 277 |
BoundingBox(Point<T> a) {
|
|
| 275 |
///Construct a box from one point |
|
| 276 |
Box(Point<T> a) {
|
|
| 278 | 277 |
_bottom_left = _top_right = a; |
| 279 | 278 |
_empty = false; |
| 280 | 279 |
} |
| 281 | 280 |
|
| 282 |
///Construct |
|
| 281 |
///Construct a box from two points |
|
| 283 | 282 |
|
| 284 |
///Construct |
|
| 283 |
///Construct a box from two points. |
|
| 285 | 284 |
///\param a The bottom left corner. |
| 286 | 285 |
///\param b The top right corner. |
| 287 | 286 |
///\warning The coordinates of the bottom left corner must be no more |
| 288 | 287 |
///than those of the top right one. |
| 289 |
|
|
| 288 |
Box(Point<T> a,Point<T> b) |
|
| 290 | 289 |
{
|
| 291 | 290 |
_bottom_left = a; |
| 292 | 291 |
_top_right = b; |
| 293 | 292 |
_empty = false; |
| 294 | 293 |
} |
| 295 | 294 |
|
| 296 |
///Construct |
|
| 295 |
///Construct a box from four numbers |
|
| 297 | 296 |
|
| 298 |
///Construct |
|
| 297 |
///Construct a box from four numbers. |
|
| 299 | 298 |
///\param l The left side of the box. |
| 300 | 299 |
///\param b The bottom of the box. |
| 301 | 300 |
///\param r The right side of the box. |
| 302 | 301 |
///\param t The top of the box. |
| 303 | 302 |
///\warning The left side must be no more than the right side and |
| 304 | 303 |
///bottom must be no more than the top. |
| 305 |
|
|
| 304 |
Box(T l,T b,T r,T t) |
|
| 306 | 305 |
{
|
| 307 | 306 |
_bottom_left=Point<T>(l,b); |
| 308 | 307 |
_top_right=Point<T>(r,t); |
| 309 | 308 |
_empty = false; |
| 310 | 309 |
} |
| 311 | 310 |
|
| 312 |
///Return \c true if the |
|
| 311 |
///Return \c true if the box is empty. |
|
| 313 | 312 |
|
| 314 |
///Return \c true if the |
|
| 313 |
///Return \c true if the box is empty (i.e. return \c false |
|
| 315 | 314 |
///if at least one point was added to the box or the coordinates of |
| 316 | 315 |
///the box were set). |
| 317 | 316 |
/// |
| 318 |
///The coordinates of an empty |
|
| 317 |
///The coordinates of an empty box are not defined. |
|
| 319 | 318 |
bool empty() const {
|
| 320 | 319 |
return _empty; |
| 321 | 320 |
} |
| 322 | 321 |
|
| 323 |
///Make the |
|
| 322 |
///Make the box empty |
|
| 324 | 323 |
void clear() {
|
| 325 | 324 |
_empty = true; |
| 326 | 325 |
} |
| 327 | 326 |
|
| 328 | 327 |
///Give back the bottom left corner of the box |
| 329 | 328 |
|
| 330 | 329 |
///Give back the bottom left corner of the box. |
| 331 |
///If the |
|
| 330 |
///If the box is empty, then the return value is not defined. |
|
| 332 | 331 |
Point<T> bottomLeft() const {
|
| 333 | 332 |
return _bottom_left; |
| 334 | 333 |
} |
| 335 | 334 |
|
| 336 | 335 |
///Set the bottom left corner of the box |
| 337 | 336 |
|
| 338 | 337 |
///Set the bottom left corner of the box. |
| 339 | 338 |
///\pre The box must not be empty. |
| 340 | 339 |
void bottomLeft(Point<T> p) {
|
| 341 | 340 |
_bottom_left = p; |
| 342 | 341 |
} |
| 343 | 342 |
|
| 344 | 343 |
///Give back the top right corner of the box |
| 345 | 344 |
|
| 346 | 345 |
///Give back the top right corner of the box. |
| 347 |
///If the |
|
| 346 |
///If the box is empty, then the return value is not defined. |
|
| 348 | 347 |
Point<T> topRight() const {
|
| 349 | 348 |
return _top_right; |
| 350 | 349 |
} |
| 351 | 350 |
|
| 352 | 351 |
///Set the top right corner of the box |
| 353 | 352 |
|
| 354 | 353 |
///Set the top right corner of the box. |
| 355 | 354 |
///\pre The box must not be empty. |
| 356 | 355 |
void topRight(Point<T> p) {
|
| 357 | 356 |
_top_right = p; |
| 358 | 357 |
} |
| 359 | 358 |
|
| 360 | 359 |
///Give back the bottom right corner of the box |
| 361 | 360 |
|
| 362 | 361 |
///Give back the bottom right corner of the box. |
| 363 |
///If the |
|
| 362 |
///If the box is empty, then the return value is not defined. |
|
| 364 | 363 |
Point<T> bottomRight() const {
|
| 365 | 364 |
return Point<T>(_top_right.x,_bottom_left.y); |
| 366 | 365 |
} |
| 367 | 366 |
|
| 368 | 367 |
///Set the bottom right corner of the box |
| 369 | 368 |
|
| 370 | 369 |
///Set the bottom right corner of the box. |
| 371 | 370 |
///\pre The box must not be empty. |
| 372 | 371 |
void bottomRight(Point<T> p) {
|
| 373 | 372 |
_top_right.x = p.x; |
| 374 | 373 |
_bottom_left.y = p.y; |
| 375 | 374 |
} |
| 376 | 375 |
|
| 377 | 376 |
///Give back the top left corner of the box |
| 378 | 377 |
|
| 379 | 378 |
///Give back the top left corner of the box. |
| 380 |
///If the |
|
| 379 |
///If the box is empty, then the return value is not defined. |
|
| 381 | 380 |
Point<T> topLeft() const {
|
| 382 | 381 |
return Point<T>(_bottom_left.x,_top_right.y); |
| 383 | 382 |
} |
| 384 | 383 |
|
| 385 | 384 |
///Set the top left corner of the box |
| 386 | 385 |
|
| 387 | 386 |
///Set the top left corner of the box. |
| 388 | 387 |
///\pre The box must not be empty. |
| 389 | 388 |
void topLeft(Point<T> p) {
|
| 390 | 389 |
_top_right.y = p.y; |
| 391 | 390 |
_bottom_left.x = p.x; |
| 392 | 391 |
} |
| 393 | 392 |
|
| 394 | 393 |
///Give back the bottom of the box |
| 395 | 394 |
|
| 396 | 395 |
///Give back the bottom of the box. |
| 397 |
///If the |
|
| 396 |
///If the box is empty, then the return value is not defined. |
|
| 398 | 397 |
T bottom() const {
|
| 399 | 398 |
return _bottom_left.y; |
| 400 | 399 |
} |
| 401 | 400 |
|
| 402 | 401 |
///Set the bottom of the box |
| 403 | 402 |
|
| 404 | 403 |
///Set the bottom of the box. |
| 405 | 404 |
///\pre The box must not be empty. |
| 406 | 405 |
void bottom(T t) {
|
| 407 | 406 |
_bottom_left.y = t; |
| 408 | 407 |
} |
| 409 | 408 |
|
| 410 | 409 |
///Give back the top of the box |
| 411 | 410 |
|
| 412 | 411 |
///Give back the top of the box. |
| 413 |
///If the |
|
| 412 |
///If the box is empty, then the return value is not defined. |
|
| 414 | 413 |
T top() const {
|
| 415 | 414 |
return _top_right.y; |
| 416 | 415 |
} |
| 417 | 416 |
|
| 418 | 417 |
///Set the top of the box |
| 419 | 418 |
|
| 420 | 419 |
///Set the top of the box. |
| 421 | 420 |
///\pre The box must not be empty. |
| 422 | 421 |
void top(T t) {
|
| 423 | 422 |
_top_right.y = t; |
| 424 | 423 |
} |
| 425 | 424 |
|
| 426 | 425 |
///Give back the left side of the box |
| 427 | 426 |
|
| 428 | 427 |
///Give back the left side of the box. |
| 429 |
///If the |
|
| 428 |
///If the box is empty, then the return value is not defined. |
|
| 430 | 429 |
T left() const {
|
| 431 | 430 |
return _bottom_left.x; |
| 432 | 431 |
} |
| 433 | 432 |
|
| 434 | 433 |
///Set the left side of the box |
| 435 | 434 |
|
| 436 | 435 |
///Set the left side of the box. |
| 437 | 436 |
///\pre The box must not be empty. |
| 438 | 437 |
void left(T t) {
|
| 439 | 438 |
_bottom_left.x = t; |
| 440 | 439 |
} |
| 441 | 440 |
|
| 442 | 441 |
/// Give back the right side of the box |
| 443 | 442 |
|
| 444 | 443 |
/// Give back the right side of the box. |
| 445 |
///If the |
|
| 444 |
///If the box is empty, then the return value is not defined. |
|
| 446 | 445 |
T right() const {
|
| 447 | 446 |
return _top_right.x; |
| 448 | 447 |
} |
| 449 | 448 |
|
| 450 | 449 |
///Set the right side of the box |
| 451 | 450 |
|
| 452 | 451 |
///Set the right side of the box. |
| 453 | 452 |
///\pre The box must not be empty. |
| 454 | 453 |
void right(T t) {
|
| 455 | 454 |
_top_right.x = t; |
| 456 | 455 |
} |
| 457 | 456 |
|
| 458 | 457 |
///Give back the height of the box |
| 459 | 458 |
|
| 460 | 459 |
///Give back the height of the box. |
| 461 |
///If the |
|
| 460 |
///If the box is empty, then the return value is not defined. |
|
| 462 | 461 |
T height() const {
|
| 463 | 462 |
return _top_right.y-_bottom_left.y; |
| 464 | 463 |
} |
| 465 | 464 |
|
| 466 | 465 |
///Give back the width of the box |
| 467 | 466 |
|
| 468 | 467 |
///Give back the width of the box. |
| 469 |
///If the |
|
| 468 |
///If the box is empty, then the return value is not defined. |
|
| 470 | 469 |
T width() const {
|
| 471 | 470 |
return _top_right.x-_bottom_left.x; |
| 472 | 471 |
} |
| 473 | 472 |
|
| 474 |
///Checks whether a point is inside |
|
| 473 |
///Checks whether a point is inside the box |
|
| 475 | 474 |
bool inside(const Point<T>& u) const {
|
| 476 | 475 |
if (_empty) |
| 477 | 476 |
return false; |
| 478 | 477 |
else {
|
| 479 | 478 |
return ( (u.x-_bottom_left.x)*(_top_right.x-u.x) >= 0 && |
| 480 | 479 |
(u.y-_bottom_left.y)*(_top_right.y-u.y) >= 0 ); |
| 481 | 480 |
} |
| 482 | 481 |
} |
| 483 | 482 |
|
| 484 |
///Increments |
|
| 483 |
///Increments the box with a point |
|
| 485 | 484 |
|
| 486 |
///Increments |
|
| 485 |
///Increments the box with a point. |
|
| 487 | 486 |
/// |
| 488 |
|
|
| 487 |
Box& add(const Point<T>& u){
|
|
| 489 | 488 |
if (_empty) {
|
| 490 | 489 |
_bottom_left = _top_right = u; |
| 491 | 490 |
_empty = false; |
| 492 | 491 |
} |
| 493 | 492 |
else {
|
| 494 | 493 |
if (_bottom_left.x > u.x) _bottom_left.x = u.x; |
| 495 | 494 |
if (_bottom_left.y > u.y) _bottom_left.y = u.y; |
| 496 | 495 |
if (_top_right.x < u.x) _top_right.x = u.x; |
| 497 | 496 |
if (_top_right.y < u.y) _top_right.y = u.y; |
| 498 | 497 |
} |
| 499 | 498 |
return *this; |
| 500 | 499 |
} |
| 501 | 500 |
|
| 502 |
///Increments |
|
| 501 |
///Increments the box to contain another box |
|
| 503 | 502 |
|
| 504 |
///Increments |
|
| 503 |
///Increments the box to contain another box. |
|
| 505 | 504 |
/// |
| 506 |
|
|
| 505 |
Box& add(const Box &u){
|
|
| 507 | 506 |
if ( !u.empty() ){
|
| 508 | 507 |
add(u._bottom_left); |
| 509 | 508 |
add(u._top_right); |
| 510 | 509 |
} |
| 511 | 510 |
return *this; |
| 512 | 511 |
} |
| 513 | 512 |
|
| 514 |
///Intersection of two |
|
| 513 |
///Intersection of two boxes |
|
| 515 | 514 |
|
| 516 |
///Intersection of two |
|
| 515 |
///Intersection of two boxes. |
|
| 517 | 516 |
/// |
| 518 |
BoundingBox operator&(const BoundingBox& u) const {
|
|
| 519 |
BoundingBox b; |
|
| 517 |
Box operator&(const Box& u) const {
|
|
| 518 |
Box b; |
|
| 520 | 519 |
if (_empty || u._empty) {
|
| 521 | 520 |
b._empty = true; |
| 522 | 521 |
} else {
|
| 523 | 522 |
b._bottom_left.x = std::max(_bottom_left.x, u._bottom_left.x); |
| 524 | 523 |
b._bottom_left.y = std::max(_bottom_left.y, u._bottom_left.y); |
| 525 | 524 |
b._top_right.x = std::min(_top_right.x, u._top_right.x); |
| 526 | 525 |
b._top_right.y = std::min(_top_right.y, u._top_right.y); |
| 527 | 526 |
b._empty = b._bottom_left.x > b._top_right.x || |
| 528 | 527 |
b._bottom_left.y > b._top_right.y; |
| 529 | 528 |
} |
| 530 | 529 |
return b; |
| 531 | 530 |
} |
| 532 | 531 |
|
| 533 |
|
|
| 532 |
};//class Box |
|
| 534 | 533 |
|
| 535 | 534 |
|
| 536 |
///Read a |
|
| 535 |
///Read a box from a stream |
|
| 537 | 536 |
|
| 538 |
///Read a bounding box from a stream. |
|
| 539 |
///\relates BoundingBox |
|
| 537 |
///Read a box from a stream. |
|
| 538 |
///\relates Box |
|
| 540 | 539 |
template<typename T> |
| 541 |
inline std::istream& operator>>(std::istream &is, |
|
| 540 |
inline std::istream& operator>>(std::istream &is, Box<T>& b) {
|
|
| 542 | 541 |
char c; |
| 543 | 542 |
Point<T> p; |
| 544 | 543 |
if (is >> c) {
|
| 545 | 544 |
if (c != '(') is.putback(c);
|
| 546 | 545 |
} else {
|
| 547 | 546 |
is.clear(); |
| 548 | 547 |
} |
| 549 | 548 |
if (!(is >> p)) return is; |
| 550 | 549 |
b.bottomLeft(p); |
| 551 | 550 |
if (is >> c) {
|
| 552 | 551 |
if (c != ',') is.putback(c); |
| 553 | 552 |
} else {
|
| 554 | 553 |
is.clear(); |
| 555 | 554 |
} |
| 556 | 555 |
if (!(is >> p)) return is; |
| 557 | 556 |
b.topRight(p); |
| 558 | 557 |
if (is >> c) {
|
| 559 | 558 |
if (c != ')') is.putback(c); |
| 560 | 559 |
} else {
|
| 561 | 560 |
is.clear(); |
| 562 | 561 |
} |
| 563 | 562 |
return is; |
| 564 | 563 |
} |
| 565 | 564 |
|
| 566 |
///Write a |
|
| 565 |
///Write a box to a stream |
|
| 567 | 566 |
|
| 568 |
///Write a bounding box to a stream. |
|
| 569 |
///\relates BoundingBox |
|
| 567 |
///Write a box to a stream. |
|
| 568 |
///\relates Box |
|
| 570 | 569 |
template<typename T> |
| 571 |
inline std::ostream& operator<<(std::ostream &os, const |
|
| 570 |
inline std::ostream& operator<<(std::ostream &os, const Box<T>& b) |
|
| 572 | 571 |
{
|
| 573 | 572 |
os << "(" << b.bottomLeft() << "," << b.topRight() << ")";
|
| 574 | 573 |
return os; |
| 575 | 574 |
} |
| 576 | 575 |
|
| 577 | 576 |
///Map of x-coordinates of a \ref Point "Point"-map |
| 578 | 577 |
|
| 579 | 578 |
///\ingroup maps |
| 580 | 579 |
///Map of x-coordinates of a \ref Point "Point"-map. |
| 581 | 580 |
/// |
| 582 | 581 |
template<class M> |
| 583 | 582 |
class XMap |
| 584 | 583 |
{
|
| 585 | 584 |
M& _map; |
| 586 | 585 |
public: |
| 587 | 586 |
|
| 588 | 587 |
typedef typename M::Value::Value Value; |
| 589 | 588 |
typedef typename M::Key Key; |
| 590 | 589 |
///\e |
| 591 | 590 |
XMap(M& map) : _map(map) {}
|
| 592 | 591 |
Value operator[](Key k) const {return _map[k].x;}
|
| 593 | 592 |
void set(Key k,Value v) {_map.set(k,typename M::Value(v,_map[k].y));}
|
| 594 | 593 |
}; |
| 595 | 594 |
|
| 596 | 595 |
///Returns an \ref XMap class |
| 597 | 596 |
|
| 598 | 597 |
///This function just returns an \ref XMap class. |
| 599 | 598 |
/// |
| 600 | 599 |
///\ingroup maps |
| 601 | 600 |
///\relates XMap |
| 602 | 601 |
template<class M> |
| 603 | 602 |
inline XMap<M> xMap(M &m) |
| 604 | 603 |
{
|
| 605 | 604 |
return XMap<M>(m); |
| 606 | 605 |
} |
| 607 | 606 |
|
| 608 | 607 |
template<class M> |
| 609 | 608 |
inline XMap<M> xMap(const M &m) |
| 610 | 609 |
{
|
| 611 | 610 |
return XMap<M>(m); |
| 612 | 611 |
} |
| 613 | 612 |
|
| 614 | 613 |
///Constant (read only) version of \ref XMap |
| 615 | 614 |
|
| 616 | 615 |
///\ingroup maps |
| 617 | 616 |
///Constant (read only) version of \ref XMap |
| 618 | 617 |
/// |
| 619 | 618 |
template<class M> |
| 620 | 619 |
class ConstXMap |
| 621 | 620 |
{
|
| 622 | 621 |
const M& _map; |
| 623 | 622 |
public: |
| 624 | 623 |
|
| 625 | 624 |
typedef typename M::Value::Value Value; |
| 626 | 625 |
typedef typename M::Key Key; |
| 627 | 626 |
///\e |
| 628 | 627 |
ConstXMap(const M &map) : _map(map) {}
|
| 629 | 628 |
Value operator[](Key k) const {return _map[k].x;}
|
| 630 | 629 |
}; |
| 631 | 630 |
|
| 632 | 631 |
///Returns a \ref ConstXMap class |
| 633 | 632 |
|
| 634 | 633 |
///This function just returns a \ref ConstXMap class. |
| 635 | 634 |
/// |
| 636 | 635 |
///\ingroup maps |
| 637 | 636 |
///\relates ConstXMap |
| 638 | 637 |
template<class M> |
| 639 | 638 |
inline ConstXMap<M> xMap(const M &m) |
| 640 | 639 |
{
|
| 641 | 640 |
return ConstXMap<M>(m); |
| 642 | 641 |
} |
| 643 | 642 |
|
| 644 | 643 |
///Map of y-coordinates of a \ref Point "Point"-map |
| 645 | 644 |
|
| 646 | 645 |
///\ingroup maps |
| 647 | 646 |
///Map of y-coordinates of a \ref Point "Point"-map. |
| 648 | 647 |
/// |
| 649 | 648 |
template<class M> |
| 650 | 649 |
class YMap |
| 651 | 650 |
{
|
| 652 | 651 |
M& _map; |
| 653 | 652 |
public: |
| 654 | 653 |
|
| 655 | 654 |
typedef typename M::Value::Value Value; |
| 656 | 655 |
typedef typename M::Key Key; |
| 657 | 656 |
///\e |
| 658 | 657 |
YMap(M& map) : _map(map) {}
|
| 659 | 658 |
Value operator[](Key k) const {return _map[k].y;}
|
| 660 | 659 |
void set(Key k,Value v) {_map.set(k,typename M::Value(_map[k].x,v));}
|
| 661 | 660 |
}; |
| 662 | 661 |
|
| 663 | 662 |
///Returns a \ref YMap class |
| 664 | 663 |
|
| 665 | 664 |
///This function just returns a \ref YMap class. |
| 666 | 665 |
/// |
| 667 | 666 |
///\ingroup maps |
| 668 | 667 |
///\relates YMap |
| 669 | 668 |
template<class M> |
| 670 | 669 |
inline YMap<M> yMap(M &m) |
| 671 | 670 |
{
|
| 672 | 671 |
return YMap<M>(m); |
| 673 | 672 |
} |
| 674 | 673 |
|
| 675 | 674 |
template<class M> |
| 676 | 675 |
inline YMap<M> yMap(const M &m) |
| 677 | 676 |
{
|
| 678 | 677 |
return YMap<M>(m); |
| 679 | 678 |
} |
| 680 | 679 |
|
| 681 | 680 |
///Constant (read only) version of \ref YMap |
| 682 | 681 |
|
| 683 | 682 |
///\ingroup maps |
| 684 | 683 |
///Constant (read only) version of \ref YMap |
| 685 | 684 |
/// |
| 686 | 685 |
template<class M> |
| 687 | 686 |
class ConstYMap |
| 688 | 687 |
{
|
| 689 | 688 |
const M& _map; |
| 690 | 689 |
public: |
| 691 | 690 |
|
| 692 | 691 |
typedef typename M::Value::Value Value; |
| 693 | 692 |
typedef typename M::Key Key; |
| 694 | 693 |
///\e |
| 695 | 694 |
ConstYMap(const M &map) : _map(map) {}
|
| 696 | 695 |
Value operator[](Key k) const {return _map[k].y;}
|
| 697 | 696 |
}; |
| 698 | 697 |
|
| 699 | 698 |
///Returns a \ref ConstYMap class |
| 700 | 699 |
|
| 701 | 700 |
///This function just returns a \ref ConstYMap class. |
| 702 | 701 |
/// |
| 703 | 702 |
///\ingroup maps |
| 704 | 703 |
///\relates ConstYMap |
| 705 | 704 |
template<class M> |
| 706 | 705 |
inline ConstYMap<M> yMap(const M &m) |
| 707 | 706 |
{
|
| 708 | 707 |
return ConstYMap<M>(m); |
| 709 | 708 |
} |
| 710 | 709 |
|
| 711 | 710 |
|
| 712 | 711 |
///\brief Map of the \ref Point::normSquare() "normSquare()" |
| 713 | 712 |
///of a \ref Point "Point"-map |
| 714 | 713 |
/// |
| 715 | 714 |
///Map of the \ref Point::normSquare() "normSquare()" |
| 716 | 715 |
///of a \ref Point "Point"-map. |
| 717 | 716 |
///\ingroup maps |
| 718 | 717 |
template<class M> |
| 719 | 718 |
class NormSquareMap |
| 720 | 719 |
{
|
| 721 | 720 |
const M& _map; |
| 722 | 721 |
public: |
| 723 | 722 |
|
| 724 | 723 |
typedef typename M::Value::Value Value; |
| 725 | 724 |
typedef typename M::Key Key; |
| 726 | 725 |
///\e |
| 727 | 726 |
NormSquareMap(const M &map) : _map(map) {}
|
| 728 | 727 |
Value operator[](Key k) const {return _map[k].normSquare();}
|
| 729 | 728 |
}; |
| 730 | 729 |
|
| 731 | 730 |
///Returns a \ref NormSquareMap class |
| 732 | 731 |
|
| 733 | 732 |
///This function just returns a \ref NormSquareMap class. |
| 734 | 733 |
/// |
| 735 | 734 |
///\ingroup maps |
| 736 | 735 |
///\relates NormSquareMap |
| 737 | 736 |
template<class M> |
| 738 | 737 |
inline NormSquareMap<M> normSquareMap(const M &m) |
| 739 | 738 |
{
|
| 740 | 739 |
return NormSquareMap<M>(m); |
| 741 | 740 |
} |
| 742 | 741 |
|
| 743 | 742 |
/// @} |
| 744 | 743 |
|
| 745 | 744 |
} //namespce dim2 |
| 746 | 745 |
|
| 747 | 746 |
} //namespace lemon |
| 748 | 747 |
|
| 749 | 748 |
#endif //LEMON_DIM2_H |
| ... | ... |
@@ -536,418 +536,418 @@ |
| 536 | 536 |
/// If both arcWidths() and autoArcWidthScale() are used, then the |
| 537 | 537 |
/// arc withs will be scaled in such a way that the greatest width will be |
| 538 | 538 |
/// equal to \c d. |
| 539 | 539 |
GraphToEps<T> &arcWidthScale(double d=.003) {_arcWidthScale=d;return *this;}
|
| 540 | 540 |
///Turns on/off the automatic arc width scaling. |
| 541 | 541 |
|
| 542 | 542 |
///Turns on/off the automatic arc width scaling. |
| 543 | 543 |
/// |
| 544 | 544 |
///\sa arcWidthScale() |
| 545 | 545 |
/// |
| 546 | 546 |
GraphToEps<T> &autoArcWidthScale(bool b=true) {
|
| 547 | 547 |
_autoArcWidthScale=b;return *this; |
| 548 | 548 |
} |
| 549 | 549 |
///Turns on/off the absolutematic arc width scaling. |
| 550 | 550 |
|
| 551 | 551 |
///Turns on/off the absolutematic arc width scaling. |
| 552 | 552 |
/// |
| 553 | 553 |
///\sa arcWidthScale() |
| 554 | 554 |
/// |
| 555 | 555 |
GraphToEps<T> &absoluteArcWidths(bool b=true) {
|
| 556 | 556 |
_absoluteArcWidths=b;return *this; |
| 557 | 557 |
} |
| 558 | 558 |
///Sets a global scale factor for the whole picture |
| 559 | 559 |
GraphToEps<T> &scale(double d) {_scale=d;return *this;}
|
| 560 | 560 |
///Sets the width of the border around the picture |
| 561 | 561 |
GraphToEps<T> &border(double b=10) {_xBorder=_yBorder=b;return *this;}
|
| 562 | 562 |
///Sets the width of the border around the picture |
| 563 | 563 |
GraphToEps<T> &border(double x, double y) {
|
| 564 | 564 |
_xBorder=x;_yBorder=y;return *this; |
| 565 | 565 |
} |
| 566 | 566 |
///Sets whether to draw arrows |
| 567 | 567 |
GraphToEps<T> &drawArrows(bool b=true) {_drawArrows=b;return *this;}
|
| 568 | 568 |
///Sets the length of the arrowheads |
| 569 | 569 |
GraphToEps<T> &arrowLength(double d=1.0) {_arrowLength*=d;return *this;}
|
| 570 | 570 |
///Sets the width of the arrowheads |
| 571 | 571 |
GraphToEps<T> &arrowWidth(double d=.3) {_arrowWidth*=d;return *this;}
|
| 572 | 572 |
|
| 573 | 573 |
///Scales the drawing to fit to A4 page |
| 574 | 574 |
GraphToEps<T> &scaleToA4() {_scaleToA4=true;return *this;}
|
| 575 | 575 |
|
| 576 | 576 |
///Enables parallel arcs |
| 577 | 577 |
GraphToEps<T> &enableParallel(bool b=true) {_enableParallel=b;return *this;}
|
| 578 | 578 |
|
| 579 | 579 |
///Sets the distance between parallel arcs |
| 580 | 580 |
GraphToEps<T> &parArcDist(double d) {_parArcDist*=d;return *this;}
|
| 581 | 581 |
|
| 582 | 582 |
///Hides the arcs |
| 583 | 583 |
GraphToEps<T> &hideArcs(bool b=true) {_showArcs=!b;return *this;}
|
| 584 | 584 |
///Hides the nodes |
| 585 | 585 |
GraphToEps<T> &hideNodes(bool b=true) {_showNodes=!b;return *this;}
|
| 586 | 586 |
|
| 587 | 587 |
///Sets the size of the node texts |
| 588 | 588 |
GraphToEps<T> &nodeTextSize(double d) {_nodeTextSize=d;return *this;}
|
| 589 | 589 |
|
| 590 | 590 |
///Sets the color of the node texts to be different from the node color |
| 591 | 591 |
|
| 592 | 592 |
///Sets the color of the node texts to be as different from the node color |
| 593 | 593 |
///as it is possible. |
| 594 | 594 |
GraphToEps<T> &distantColorNodeTexts() |
| 595 | 595 |
{_nodeTextColorType=DIST_COL;return *this;}
|
| 596 | 596 |
///Sets the color of the node texts to be black or white and always visible. |
| 597 | 597 |
|
| 598 | 598 |
///Sets the color of the node texts to be black or white according to |
| 599 | 599 |
///which is more different from the node color. |
| 600 | 600 |
GraphToEps<T> &distantBWNodeTexts() |
| 601 | 601 |
{_nodeTextColorType=DIST_BW;return *this;}
|
| 602 | 602 |
|
| 603 | 603 |
///Gives a preamble block for node Postscript block. |
| 604 | 604 |
|
| 605 | 605 |
///Gives a preamble block for node Postscript block. |
| 606 | 606 |
/// |
| 607 | 607 |
///\sa nodePsTexts() |
| 608 | 608 |
GraphToEps<T> & nodePsTextsPreamble(const char *str) {
|
| 609 | 609 |
_nodePsTextsPreamble=str ;return *this; |
| 610 | 610 |
} |
| 611 | 611 |
///Sets whether the graph is undirected |
| 612 | 612 |
|
| 613 | 613 |
///Sets whether the graph is undirected. |
| 614 | 614 |
/// |
| 615 | 615 |
///This setting is the default for undirected graphs. |
| 616 | 616 |
/// |
| 617 | 617 |
///\sa directed() |
| 618 | 618 |
GraphToEps<T> &undirected(bool b=true) {_undirected=b;return *this;}
|
| 619 | 619 |
|
| 620 | 620 |
///Sets whether the graph is directed |
| 621 | 621 |
|
| 622 | 622 |
///Sets whether the graph is directed. |
| 623 | 623 |
///Use it to show the edges as a pair of directed ones. |
| 624 | 624 |
/// |
| 625 | 625 |
///This setting is the default for digraphs. |
| 626 | 626 |
/// |
| 627 | 627 |
///\sa undirected() |
| 628 | 628 |
GraphToEps<T> &directed(bool b=true) {_undirected=!b;return *this;}
|
| 629 | 629 |
|
| 630 | 630 |
///Sets the title. |
| 631 | 631 |
|
| 632 | 632 |
///Sets the title of the generated image, |
| 633 | 633 |
///namely it inserts a <tt>%%Title:</tt> DSC field to the header of |
| 634 | 634 |
///the EPS file. |
| 635 | 635 |
GraphToEps<T> &title(const std::string &t) {_title=t;return *this;}
|
| 636 | 636 |
///Sets the copyright statement. |
| 637 | 637 |
|
| 638 | 638 |
///Sets the copyright statement of the generated image, |
| 639 | 639 |
///namely it inserts a <tt>%%Copyright:</tt> DSC field to the header of |
| 640 | 640 |
///the EPS file. |
| 641 | 641 |
GraphToEps<T> ©right(const std::string &t) {_copyright=t;return *this;}
|
| 642 | 642 |
|
| 643 | 643 |
protected: |
| 644 | 644 |
bool isInsideNode(dim2::Point<double> p, double r,int t) |
| 645 | 645 |
{
|
| 646 | 646 |
switch(t) {
|
| 647 | 647 |
case CIRCLE: |
| 648 | 648 |
case MALE: |
| 649 | 649 |
case FEMALE: |
| 650 | 650 |
return p.normSquare()<=r*r; |
| 651 | 651 |
case SQUARE: |
| 652 | 652 |
return p.x<=r&&p.x>=-r&&p.y<=r&&p.y>=-r; |
| 653 | 653 |
case DIAMOND: |
| 654 | 654 |
return p.x+p.y<=r && p.x-p.y<=r && -p.x+p.y<=r && -p.x-p.y<=r; |
| 655 | 655 |
} |
| 656 | 656 |
return false; |
| 657 | 657 |
} |
| 658 | 658 |
|
| 659 | 659 |
public: |
| 660 | 660 |
~GraphToEps() { }
|
| 661 | 661 |
|
| 662 | 662 |
///Draws the graph. |
| 663 | 663 |
|
| 664 | 664 |
///Like other functions using |
| 665 | 665 |
///\ref named-templ-func-param "named template parameters", |
| 666 | 666 |
///this function calls the algorithm itself, i.e. in this case |
| 667 | 667 |
///it draws the graph. |
| 668 | 668 |
void run() {
|
| 669 | 669 |
//\todo better 'epsilon' would be nice here. |
| 670 | 670 |
const double EPSILON=1e-9; |
| 671 | 671 |
if(dontPrint) return; |
| 672 | 672 |
|
| 673 | 673 |
_graph_to_eps_bits::_NegY<typename T::CoordsMapType> |
| 674 | 674 |
mycoords(_coords,_negY); |
| 675 | 675 |
|
| 676 | 676 |
os << "%!PS-Adobe-2.0 EPSF-2.0\n"; |
| 677 | 677 |
if(_title.size()>0) os << "%%Title: " << _title << '\n'; |
| 678 | 678 |
if(_copyright.size()>0) os << "%%Copyright: " << _copyright << '\n'; |
| 679 | 679 |
os << "%%Creator: LEMON, graphToEps()\n"; |
| 680 | 680 |
|
| 681 | 681 |
{
|
| 682 | 682 |
#ifndef WIN32 |
| 683 | 683 |
timeval tv; |
| 684 | 684 |
gettimeofday(&tv, 0); |
| 685 | 685 |
|
| 686 | 686 |
char cbuf[26]; |
| 687 | 687 |
ctime_r(&tv.tv_sec,cbuf); |
| 688 | 688 |
os << "%%CreationDate: " << cbuf; |
| 689 | 689 |
#else |
| 690 | 690 |
SYSTEMTIME time; |
| 691 | 691 |
char buf1[11], buf2[9], buf3[5]; |
| 692 | 692 |
|
| 693 | 693 |
GetSystemTime(&time); |
| 694 | 694 |
if (GetDateFormat(LOCALE_USER_DEFAULT, 0, &time, |
| 695 | 695 |
"ddd MMM dd", buf1, 11) && |
| 696 | 696 |
GetTimeFormat(LOCALE_USER_DEFAULT, 0, &time, |
| 697 | 697 |
"HH':'mm':'ss", buf2, 9) && |
| 698 | 698 |
GetDateFormat(LOCALE_USER_DEFAULT, 0, &time, |
| 699 | 699 |
"yyyy", buf3, 5)) {
|
| 700 | 700 |
os << "%%CreationDate: " << buf1 << ' ' |
| 701 | 701 |
<< buf2 << ' ' << buf3 << std::endl; |
| 702 | 702 |
} |
| 703 | 703 |
#endif |
| 704 | 704 |
} |
| 705 | 705 |
|
| 706 | 706 |
if (_autoArcWidthScale) {
|
| 707 | 707 |
double max_w=0; |
| 708 | 708 |
for(ArcIt e(g);e!=INVALID;++e) |
| 709 | 709 |
max_w=std::max(double(_arcWidths[e]),max_w); |
| 710 | 710 |
//\todo better 'epsilon' would be nice here. |
| 711 | 711 |
if(max_w>EPSILON) {
|
| 712 | 712 |
_arcWidthScale/=max_w; |
| 713 | 713 |
} |
| 714 | 714 |
} |
| 715 | 715 |
|
| 716 | 716 |
if (_autoNodeScale) {
|
| 717 | 717 |
double max_s=0; |
| 718 | 718 |
for(NodeIt n(g);n!=INVALID;++n) |
| 719 | 719 |
max_s=std::max(double(_nodeSizes[n]),max_s); |
| 720 | 720 |
//\todo better 'epsilon' would be nice here. |
| 721 | 721 |
if(max_s>EPSILON) {
|
| 722 | 722 |
_nodeScale/=max_s; |
| 723 | 723 |
} |
| 724 | 724 |
} |
| 725 | 725 |
|
| 726 | 726 |
double diag_len = 1; |
| 727 | 727 |
if(!(_absoluteNodeSizes&&_absoluteArcWidths)) {
|
| 728 |
dim2:: |
|
| 728 |
dim2::Box<double> bb; |
|
| 729 | 729 |
for(NodeIt n(g);n!=INVALID;++n) bb.add(mycoords[n]); |
| 730 | 730 |
if (bb.empty()) {
|
| 731 |
bb = dim2:: |
|
| 731 |
bb = dim2::Box<double>(dim2::Point<double>(0,0)); |
|
| 732 | 732 |
} |
| 733 | 733 |
diag_len = std::sqrt((bb.bottomLeft()-bb.topRight()).normSquare()); |
| 734 | 734 |
if(diag_len<EPSILON) diag_len = 1; |
| 735 | 735 |
if(!_absoluteNodeSizes) _nodeScale*=diag_len; |
| 736 | 736 |
if(!_absoluteArcWidths) _arcWidthScale*=diag_len; |
| 737 | 737 |
} |
| 738 | 738 |
|
| 739 |
dim2:: |
|
| 739 |
dim2::Box<double> bb; |
|
| 740 | 740 |
for(NodeIt n(g);n!=INVALID;++n) {
|
| 741 | 741 |
double ns=_nodeSizes[n]*_nodeScale; |
| 742 | 742 |
dim2::Point<double> p(ns,ns); |
| 743 | 743 |
switch(_nodeShapes[n]) {
|
| 744 | 744 |
case CIRCLE: |
| 745 | 745 |
case SQUARE: |
| 746 | 746 |
case DIAMOND: |
| 747 | 747 |
bb.add(p+mycoords[n]); |
| 748 | 748 |
bb.add(-p+mycoords[n]); |
| 749 | 749 |
break; |
| 750 | 750 |
case MALE: |
| 751 | 751 |
bb.add(-p+mycoords[n]); |
| 752 | 752 |
bb.add(dim2::Point<double>(1.5*ns,1.5*std::sqrt(3.0)*ns)+mycoords[n]); |
| 753 | 753 |
break; |
| 754 | 754 |
case FEMALE: |
| 755 | 755 |
bb.add(p+mycoords[n]); |
| 756 | 756 |
bb.add(dim2::Point<double>(-ns,-3.01*ns)+mycoords[n]); |
| 757 | 757 |
break; |
| 758 | 758 |
} |
| 759 | 759 |
} |
| 760 | 760 |
if (bb.empty()) {
|
| 761 |
bb = dim2:: |
|
| 761 |
bb = dim2::Box<double>(dim2::Point<double>(0,0)); |
|
| 762 | 762 |
} |
| 763 | 763 |
|
| 764 | 764 |
if(_scaleToA4) |
| 765 | 765 |
os <<"%%BoundingBox: 0 0 596 842\n%%DocumentPaperSizes: a4\n"; |
| 766 | 766 |
else {
|
| 767 | 767 |
if(_preScale) {
|
| 768 | 768 |
//Rescale so that BoundingBox won't be neither to big nor too small. |
| 769 | 769 |
while(bb.height()*_scale>1000||bb.width()*_scale>1000) _scale/=10; |
| 770 | 770 |
while(bb.height()*_scale<100||bb.width()*_scale<100) _scale*=10; |
| 771 | 771 |
} |
| 772 | 772 |
|
| 773 | 773 |
os << "%%BoundingBox: " |
| 774 | 774 |
<< int(floor(bb.left() * _scale - _xBorder)) << ' ' |
| 775 | 775 |
<< int(floor(bb.bottom() * _scale - _yBorder)) << ' ' |
| 776 | 776 |
<< int(ceil(bb.right() * _scale + _xBorder)) << ' ' |
| 777 | 777 |
<< int(ceil(bb.top() * _scale + _yBorder)) << '\n'; |
| 778 | 778 |
} |
| 779 | 779 |
|
| 780 | 780 |
os << "%%EndComments\n"; |
| 781 | 781 |
|
| 782 | 782 |
//x1 y1 x2 y2 x3 y3 cr cg cb w |
| 783 | 783 |
os << "/lb { setlinewidth setrgbcolor newpath moveto\n"
|
| 784 | 784 |
<< " 4 2 roll 1 index 1 index curveto stroke } bind def\n"; |
| 785 | 785 |
os << "/l { setlinewidth setrgbcolor newpath moveto lineto stroke }"
|
| 786 | 786 |
<< " bind def\n"; |
| 787 | 787 |
//x y r |
| 788 | 788 |
os << "/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath }"
|
| 789 | 789 |
<< " bind def\n"; |
| 790 | 790 |
//x y r |
| 791 | 791 |
os << "/sq { newpath 2 index 1 index add 2 index 2 index add moveto\n"
|
| 792 | 792 |
<< " 2 index 1 index sub 2 index 2 index add lineto\n" |
| 793 | 793 |
<< " 2 index 1 index sub 2 index 2 index sub lineto\n" |
| 794 | 794 |
<< " 2 index 1 index add 2 index 2 index sub lineto\n" |
| 795 | 795 |
<< " closepath pop pop pop} bind def\n"; |
| 796 | 796 |
//x y r |
| 797 | 797 |
os << "/di { newpath 2 index 1 index add 2 index moveto\n"
|
| 798 | 798 |
<< " 2 index 2 index 2 index add lineto\n" |
| 799 | 799 |
<< " 2 index 1 index sub 2 index lineto\n" |
| 800 | 800 |
<< " 2 index 2 index 2 index sub lineto\n" |
| 801 | 801 |
<< " closepath pop pop pop} bind def\n"; |
| 802 | 802 |
// x y r cr cg cb |
| 803 | 803 |
os << "/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill\n"
|
| 804 | 804 |
<< " setrgbcolor " << 1+_nodeBorderQuotient << " div c fill\n" |
| 805 | 805 |
<< " } bind def\n"; |
| 806 | 806 |
os << "/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill\n"
|
| 807 | 807 |
<< " setrgbcolor " << 1+_nodeBorderQuotient << " div sq fill\n" |
| 808 | 808 |
<< " } bind def\n"; |
| 809 | 809 |
os << "/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill\n"
|
| 810 | 810 |
<< " setrgbcolor " << 1+_nodeBorderQuotient << " div di fill\n" |
| 811 | 811 |
<< " } bind def\n"; |
| 812 | 812 |
os << "/nfemale { 0 0 0 setrgbcolor 3 index "
|
| 813 | 813 |
<< _nodeBorderQuotient/(1+_nodeBorderQuotient) |
| 814 | 814 |
<< " 1.5 mul mul setlinewidth\n" |
| 815 | 815 |
<< " newpath 5 index 5 index moveto " |
| 816 | 816 |
<< "5 index 5 index 5 index 3.01 mul sub\n" |
| 817 | 817 |
<< " lineto 5 index 4 index .7 mul sub 5 index 5 index 2.2 mul sub" |
| 818 | 818 |
<< " moveto\n" |
| 819 | 819 |
<< " 5 index 4 index .7 mul add 5 index 5 index 2.2 mul sub lineto " |
| 820 | 820 |
<< "stroke\n" |
| 821 | 821 |
<< " 5 index 5 index 5 index c fill\n" |
| 822 | 822 |
<< " setrgbcolor " << 1+_nodeBorderQuotient << " div c fill\n" |
| 823 | 823 |
<< " } bind def\n"; |
| 824 | 824 |
os << "/nmale {\n"
|
| 825 | 825 |
<< " 0 0 0 setrgbcolor 3 index " |
| 826 | 826 |
<< _nodeBorderQuotient/(1+_nodeBorderQuotient) |
| 827 | 827 |
<<" 1.5 mul mul setlinewidth\n" |
| 828 | 828 |
<< " newpath 5 index 5 index moveto\n" |
| 829 | 829 |
<< " 5 index 4 index 1 mul 1.5 mul add\n" |
| 830 | 830 |
<< " 5 index 5 index 3 sqrt 1.5 mul mul add\n" |
| 831 | 831 |
<< " 1 index 1 index lineto\n" |
| 832 | 832 |
<< " 1 index 1 index 7 index sub moveto\n" |
| 833 | 833 |
<< " 1 index 1 index lineto\n" |
| 834 | 834 |
<< " exch 5 index 3 sqrt .5 mul mul sub exch 5 index .5 mul sub" |
| 835 | 835 |
<< " lineto\n" |
| 836 | 836 |
<< " stroke\n" |
| 837 | 837 |
<< " 5 index 5 index 5 index c fill\n" |
| 838 | 838 |
<< " setrgbcolor " << 1+_nodeBorderQuotient << " div c fill\n" |
| 839 | 839 |
<< " } bind def\n"; |
| 840 | 840 |
|
| 841 | 841 |
|
| 842 | 842 |
os << "/arrl " << _arrowLength << " def\n"; |
| 843 | 843 |
os << "/arrw " << _arrowWidth << " def\n"; |
| 844 | 844 |
// l dx_norm dy_norm |
| 845 | 845 |
os << "/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def\n";
|
| 846 | 846 |
//len w dx_norm dy_norm x1 y1 cr cg cb |
| 847 | 847 |
os << "/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx "
|
| 848 | 848 |
<< "exch def\n" |
| 849 | 849 |
<< " /w exch def /len exch def\n" |
| 850 | 850 |
//<< "0.1 setlinewidth x1 y1 moveto dx len mul dy len mul rlineto stroke" |
| 851 | 851 |
<< " newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto\n" |
| 852 | 852 |
<< " len w sub arrl sub dx dy lrl\n" |
| 853 | 853 |
<< " arrw dy dx neg lrl\n" |
| 854 | 854 |
<< " dx arrl w add mul dy w 2 div arrw add mul sub\n" |
| 855 | 855 |
<< " dy arrl w add mul dx w 2 div arrw add mul add rlineto\n" |
| 856 | 856 |
<< " dx arrl w add mul neg dy w 2 div arrw add mul sub\n" |
| 857 | 857 |
<< " dy arrl w add mul neg dx w 2 div arrw add mul add rlineto\n" |
| 858 | 858 |
<< " arrw dy dx neg lrl\n" |
| 859 | 859 |
<< " len w sub arrl sub neg dx dy lrl\n" |
| 860 | 860 |
<< " closepath fill } bind def\n"; |
| 861 | 861 |
os << "/cshow { 2 index 2 index moveto dup stringwidth pop\n"
|
| 862 | 862 |
<< " neg 2 div fosi .35 mul neg rmoveto show pop pop} def\n"; |
| 863 | 863 |
|
| 864 | 864 |
os << "\ngsave\n"; |
| 865 | 865 |
if(_scaleToA4) |
| 866 | 866 |
if(bb.height()>bb.width()) {
|
| 867 | 867 |
double sc= std::min((A4HEIGHT-2*A4BORDER)/bb.height(), |
| 868 | 868 |
(A4WIDTH-2*A4BORDER)/bb.width()); |
| 869 | 869 |
os << ((A4WIDTH -2*A4BORDER)-sc*bb.width())/2 + A4BORDER << ' ' |
| 870 | 870 |
<< ((A4HEIGHT-2*A4BORDER)-sc*bb.height())/2 + A4BORDER |
| 871 | 871 |
<< " translate\n" |
| 872 | 872 |
<< sc << " dup scale\n" |
| 873 | 873 |
<< -bb.left() << ' ' << -bb.bottom() << " translate\n"; |
| 874 | 874 |
} |
| 875 | 875 |
else {
|
| 876 | 876 |
//\todo Verify centering |
| 877 | 877 |
double sc= std::min((A4HEIGHT-2*A4BORDER)/bb.width(), |
| 878 | 878 |
(A4WIDTH-2*A4BORDER)/bb.height()); |
| 879 | 879 |
os << ((A4WIDTH -2*A4BORDER)-sc*bb.height())/2 + A4BORDER << ' ' |
| 880 | 880 |
<< ((A4HEIGHT-2*A4BORDER)-sc*bb.width())/2 + A4BORDER |
| 881 | 881 |
<< " translate\n" |
| 882 | 882 |
<< sc << " dup scale\n90 rotate\n" |
| 883 | 883 |
<< -bb.left() << ' ' << -bb.top() << " translate\n"; |
| 884 | 884 |
} |
| 885 | 885 |
else if(_scale!=1.0) os << _scale << " dup scale\n"; |
| 886 | 886 |
|
| 887 | 887 |
if(_showArcs) {
|
| 888 | 888 |
os << "%Arcs:\ngsave\n"; |
| 889 | 889 |
if(_enableParallel) {
|
| 890 | 890 |
std::vector<Arc> el; |
| 891 | 891 |
for(ArcIt e(g);e!=INVALID;++e) |
| 892 | 892 |
if((!_undirected||g.source(e)<g.target(e))&&_arcWidths[e]>0 |
| 893 | 893 |
&&g.source(e)!=g.target(e)) |
| 894 | 894 |
el.push_back(e); |
| 895 | 895 |
std::sort(el.begin(),el.end(),arcLess(g)); |
| 896 | 896 |
|
| 897 | 897 |
typename std::vector<Arc>::iterator j; |
| 898 | 898 |
for(typename std::vector<Arc>::iterator i=el.begin();i!=el.end();i=j) {
|
| 899 | 899 |
for(j=i+1;j!=el.end()&&isParallel(*i,*j);++j) ; |
| 900 | 900 |
|
| 901 | 901 |
double sw=0; |
| 902 | 902 |
for(typename std::vector<Arc>::iterator e=i;e!=j;++e) |
| 903 | 903 |
sw+=_arcWidths[*e]*_arcWidthScale+_parArcDist; |
| 904 | 904 |
sw-=_parArcDist; |
| 905 | 905 |
sw/=-2.0; |
| 906 | 906 |
dim2::Point<double> |
| 907 | 907 |
dvec(mycoords[g.target(*i)]-mycoords[g.source(*i)]); |
| 908 | 908 |
double l=std::sqrt(dvec.normSquare()); |
| 909 | 909 |
//\todo better 'epsilon' would be nice here. |
| 910 | 910 |
dim2::Point<double> d(dvec/std::max(l,EPSILON)); |
| 911 | 911 |
dim2::Point<double> m; |
| 912 | 912 |
// m=dim2::Point<double>(mycoords[g.target(*i)]+ |
| 913 | 913 |
// mycoords[g.source(*i)])/2.0; |
| 914 | 914 |
|
| 915 | 915 |
// m=dim2::Point<double>(mycoords[g.source(*i)])+ |
| 916 | 916 |
// dvec*(double(_nodeSizes[g.source(*i)])/ |
| 917 | 917 |
// (_nodeSizes[g.source(*i)]+_nodeSizes[g.target(*i)])); |
| 918 | 918 |
|
| 919 | 919 |
m=dim2::Point<double>(mycoords[g.source(*i)])+ |
| 920 | 920 |
d*(l+_nodeSizes[g.source(*i)]-_nodeSizes[g.target(*i)])/2.0; |
| 921 | 921 |
|
| 922 | 922 |
for(typename std::vector<Arc>::iterator e=i;e!=j;++e) {
|
| 923 | 923 |
sw+=_arcWidths[*e]*_arcWidthScale/2.0; |
| 924 | 924 |
dim2::Point<double> mm=m+rot90(d)*sw/.75; |
| 925 | 925 |
if(_drawArrows) {
|
| 926 | 926 |
int node_shape; |
| 927 | 927 |
dim2::Point<double> s=mycoords[g.source(*e)]; |
| 928 | 928 |
dim2::Point<double> t=mycoords[g.target(*e)]; |
| 929 | 929 |
double rn=_nodeSizes[g.target(*e)]*_nodeScale; |
| 930 | 930 |
node_shape=_nodeShapes[g.target(*e)]; |
| 931 | 931 |
dim2::Bezier3 bez(s,mm,mm,t); |
| 932 | 932 |
double t1=0,t2=1; |
| 933 | 933 |
for(int ii=0;ii<INTERPOL_PREC;++ii) |
| 934 | 934 |
if(isInsideNode(bez((t1+t2)/2)-t,rn,node_shape)) t2=(t1+t2)/2; |
| 935 | 935 |
else t1=(t1+t2)/2; |
| 936 | 936 |
dim2::Point<double> apoint=bez((t1+t2)/2); |
| 937 | 937 |
rn = _arrowLength+_arcWidths[*e]*_arcWidthScale; |
| 938 | 938 |
rn*=rn; |
| 939 | 939 |
t2=(t1+t2)/2;t1=0; |
| 940 | 940 |
for(int ii=0;ii<INTERPOL_PREC;++ii) |
| 941 | 941 |
if((bez((t1+t2)/2)-apoint).normSquare()>rn) t1=(t1+t2)/2; |
| 942 | 942 |
else t2=(t1+t2)/2; |
| 943 | 943 |
dim2::Point<double> linend=bez((t1+t2)/2); |
| 944 | 944 |
bez=bez.before((t1+t2)/2); |
| 945 | 945 |
// rn=_nodeSizes[g.source(*e)]*_nodeScale; |
| 946 | 946 |
// node_shape=_nodeShapes[g.source(*e)]; |
| 947 | 947 |
// t1=0;t2=1; |
| 948 | 948 |
// for(int i=0;i<INTERPOL_PREC;++i) |
| 949 | 949 |
// if(isInsideNode(bez((t1+t2)/2)-t,rn,node_shape)) |
| 950 | 950 |
// t1=(t1+t2)/2; |
| 951 | 951 |
// else t2=(t1+t2)/2; |
| 952 | 952 |
// bez=bez.after((t1+t2)/2); |
| 953 | 953 |
os << _arcWidths[*e]*_arcWidthScale << " setlinewidth " |
| 1 | 1 |
/* -*- mode: C++; indent-tabs-mode: nil; -*- |
| 2 | 2 |
* |
| 3 | 3 |
* This file is a part of LEMON, a generic C++ optimization library. |
| 4 | 4 |
* |
| 5 | 5 |
* Copyright (C) 2003-2008 |
| 6 | 6 |
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
| 7 | 7 |
* (Egervary Research Group on Combinatorial Optimization, EGRES). |
| 8 | 8 |
* |
| 9 | 9 |
* Permission to use, modify and distribute this software is granted |
| 10 | 10 |
* provided that this copyright notice appears in all copies. For |
| 11 | 11 |
* precise terms see the accompanying LICENSE file. |
| 12 | 12 |
* |
| 13 | 13 |
* This software is provided "AS IS" with no warranty of any kind, |
| 14 | 14 |
* express or implied, and with no claim as to its suitability for any |
| 15 | 15 |
* purpose. |
| 16 | 16 |
* |
| 17 | 17 |
*/ |
| 18 | 18 |
|
| 19 | 19 |
#include <lemon/dim2.h> |
| 20 | 20 |
#include <iostream> |
| 21 | 21 |
#include "test_tools.h" |
| 22 | 22 |
|
| 23 | 23 |
using namespace std; |
| 24 | 24 |
using namespace lemon; |
| 25 | 25 |
|
| 26 | 26 |
int main() |
| 27 | 27 |
{
|
| 28 | 28 |
typedef dim2::Point<int> Point; |
| 29 | 29 |
|
| 30 | 30 |
Point p; |
| 31 | 31 |
check(p.size()==2, "Wrong dim2::Point initialization."); |
| 32 | 32 |
|
| 33 | 33 |
Point a(1,2); |
| 34 | 34 |
Point b(3,4); |
| 35 | 35 |
check(a[0]==1 && a[1]==2, "Wrong dim2::Point initialization."); |
| 36 | 36 |
|
| 37 | 37 |
p = a+b; |
| 38 | 38 |
check(p.x==4 && p.y==6, "Wrong dim2::Point addition."); |
| 39 | 39 |
|
| 40 | 40 |
p = a-b; |
| 41 | 41 |
check(p.x==-2 && p.y==-2, "Wrong dim2::Point subtraction."); |
| 42 | 42 |
|
| 43 | 43 |
check(a.normSquare()==5,"Wrong dim2::Point norm calculation."); |
| 44 | 44 |
check(a*b==11, "Wrong dim2::Point scalar product."); |
| 45 | 45 |
|
| 46 | 46 |
int l=2; |
| 47 | 47 |
p = a*l; |
| 48 | 48 |
check(p.x==2 && p.y==4, "Wrong dim2::Point multiplication by a scalar."); |
| 49 | 49 |
|
| 50 | 50 |
p = b/l; |
| 51 | 51 |
check(p.x==1 && p.y==2, "Wrong dim2::Point division by a scalar."); |
| 52 | 52 |
|
| 53 |
typedef dim2::BoundingBox<int> BB; |
|
| 54 |
BB box1; |
|
| 55 |
|
|
| 53 |
typedef dim2::Box<int> Box; |
|
| 54 |
Box box1; |
|
| 55 |
check(box1.empty(), "Wrong empty() in dim2::Box."); |
|
| 56 | 56 |
|
| 57 | 57 |
box1.add(a); |
| 58 |
check(!box1.empty(), "Wrong empty() in dim2:: |
|
| 58 |
check(!box1.empty(), "Wrong empty() in dim2::Box."); |
|
| 59 | 59 |
box1.add(b); |
| 60 | 60 |
|
| 61 | 61 |
check(box1.left()==1 && box1.bottom()==2 && |
| 62 | 62 |
box1.right()==3 && box1.top()==4, |
| 63 |
"Wrong addition of points to dim2:: |
|
| 63 |
"Wrong addition of points to dim2::Box."); |
|
| 64 | 64 |
|
| 65 |
check(box1.inside(Point(2,3)), "Wrong inside() in dim2::BoundingBox."); |
|
| 66 |
check(box1.inside(Point(1,3)), "Wrong inside() in dim2::BoundingBox."); |
|
| 67 |
check( |
|
| 65 |
check(box1.inside(Point(2,3)), "Wrong inside() in dim2::Box."); |
|
| 66 |
check(box1.inside(Point(1,3)), "Wrong inside() in dim2::Box."); |
|
| 67 |
check(!box1.inside(Point(0,3)), "Wrong inside() in dim2::Box."); |
|
| 68 | 68 |
|
| 69 |
BB box2(Point(2,2)); |
|
| 70 |
check(!box2.empty(), "Wrong empty() in dim2::BoundingBox."); |
|
| 71 |
|
|
| 69 |
Box box2(Point(2,2)); |
|
| 70 |
check(!box2.empty(), "Wrong empty() in dim2::Box."); |
|
| 71 |
|
|
| 72 | 72 |
box2.bottomLeft(Point(2,0)); |
| 73 | 73 |
box2.topRight(Point(5,3)); |
| 74 |
|
|
| 74 |
Box box3 = box1 & box2; |
|
| 75 | 75 |
check(!box3.empty() && |
| 76 |
box3.left()==2 && box3.bottom()==2 && |
|
| 76 |
box3.left()==2 && box3.bottom()==2 && |
|
| 77 | 77 |
box3.right()==3 && box3.top()==3, |
| 78 |
"Wrong intersection of two dim2::BoundingBox objects."); |
|
| 79 |
|
|
| 78 |
"Wrong intersection of two dim2::Box objects."); |
|
| 79 |
|
|
| 80 | 80 |
box1.add(box2); |
| 81 | 81 |
check(!box1.empty() && |
| 82 | 82 |
box1.left()==1 && box1.bottom()==0 && |
| 83 | 83 |
box1.right()==5 && box1.top()==4, |
| 84 |
"Wrong addition of two dim2:: |
|
| 84 |
"Wrong addition of two dim2::Box objects."); |
|
| 85 | 85 |
|
| 86 | 86 |
return 0; |
| 87 | 87 |
} |
0 comments (0 inline)