1 // Boost.Polygon library transform.hpp header file 2 3 // Copyright (c) Intel Corporation 2008. 4 // Copyright (c) 2008-2012 Simonson Lucanus. 5 // Copyright (c) 2012-2012 Andrii Sydorchuk. 6 7 // See http://www.boost.org for updates, documentation, and revision history. 8 // Use, modification and distribution is subject to the Boost Software License, 9 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at 10 // http://www.boost.org/LICENSE_1_0.txt) 11 12 #ifndef BOOST_POLYGON_TRANSFORM_HPP 13 #define BOOST_POLYGON_TRANSFORM_HPP 14 15 #include "isotropy.hpp" 16 17 namespace boost { 18 namespace polygon { 19 // Transformation of Coordinate System. 20 // Enum meaning: 21 // Select which direction_2d to change the positive direction of each 22 // axis in the old coordinate system to map it to the new coordiante system. 23 // The first direction_2d listed for each enum is the direction to map the 24 // positive horizontal direction to. 25 // The second direction_2d listed for each enum is the direction to map the 26 // positive vertical direction to. 27 // The zero position bit (LSB) indicates whether the horizontal axis flips 28 // when transformed. 29 // The 1st postion bit indicates whether the vertical axis flips when 30 // transformed. 31 // The 2nd position bit indicates whether the horizontal and vertical axis 32 // swap positions when transformed. 33 // Enum Values: 34 // 000 EAST NORTH 35 // 001 WEST NORTH 36 // 010 EAST SOUTH 37 // 011 WEST SOUTH 38 // 100 NORTH EAST 39 // 101 SOUTH EAST 40 // 110 NORTH WEST 41 // 111 SOUTH WEST 42 class axis_transformation { 43 public: 44 enum ATR { 45 #ifdef BOOST_POLYGON_ENABLE_DEPRECATED 46 EN = 0, 47 WN = 1, 48 ES = 2, 49 WS = 3, 50 NE = 4, 51 SE = 5, 52 NW = 6, 53 SW = 7, 54 #endif 55 NULL_TRANSFORM = 0, 56 BEGIN_TRANSFORM = 0, 57 EAST_NORTH = 0, 58 WEST_NORTH = 1, FLIP_X = 1, 59 EAST_SOUTH = 2, FLIP_Y = 2, 60 WEST_SOUTH = 3, FLIP_XY = 3, 61 NORTH_EAST = 4, SWAP_XY = 4, 62 SOUTH_EAST = 5, ROTATE_LEFT = 5, 63 NORTH_WEST = 6, ROTATE_RIGHT = 6, 64 SOUTH_WEST = 7, FLIP_SWAP_XY = 7, 65 END_TRANSFORM = 7 66 }; 67 68 // Individual axis enum values indicate which axis an implicit individual 69 // axis will be mapped to. 70 // The value of the enum paired with an axis provides the information 71 // about what the axis will transform to. 72 // Three individual axis values, one for each axis, are equivalent to one 73 // ATR enum value, but easier to work with because they are independent. 74 // Converting to and from the individual axis values from the ATR value 75 // is a convenient way to implement tranformation related functionality. 76 // Enum meanings: 77 // PX: map to positive x axis 78 // NX: map to negative x axis 79 // PY: map to positive y axis 80 // NY: map to negative y axis 81 enum INDIVIDUAL_AXIS { 82 PX = 0, 83 NX = 1, 84 PY = 2, 85 NY = 3 86 }; 87 axis_transformation()88 axis_transformation() : atr_(NULL_TRANSFORM) {} axis_transformation(ATR atr)89 explicit axis_transformation(ATR atr) : atr_(atr) {} axis_transformation(const axis_transformation & atr)90 axis_transformation(const axis_transformation& atr) : atr_(atr.atr_) {} 91 axis_transformation(const orientation_2d & orient)92 explicit axis_transformation(const orientation_2d& orient) { 93 const ATR tmp[2] = { 94 NORTH_EAST, // sort x, then y 95 EAST_NORTH // sort y, then x 96 }; 97 atr_ = tmp[orient.to_int()]; 98 } 99 axis_transformation(const direction_2d & dir)100 explicit axis_transformation(const direction_2d& dir) { 101 const ATR tmp[4] = { 102 SOUTH_EAST, // sort x, then y 103 NORTH_EAST, // sort x, then y 104 EAST_SOUTH, // sort y, then x 105 EAST_NORTH // sort y, then x 106 }; 107 atr_ = tmp[dir.to_int()]; 108 } 109 110 // assignment operator operator =(const axis_transformation & a)111 axis_transformation& operator=(const axis_transformation& a) { 112 atr_ = a.atr_; 113 return *this; 114 } 115 116 // assignment operator operator =(const ATR & atr)117 axis_transformation& operator=(const ATR& atr) { 118 atr_ = atr; 119 return *this; 120 } 121 122 // equivalence operator operator ==(const axis_transformation & a) const123 bool operator==(const axis_transformation& a) const { 124 return atr_ == a.atr_; 125 } 126 127 // inequivalence operator operator !=(const axis_transformation & a) const128 bool operator!=(const axis_transformation& a) const { 129 return !(*this == a); 130 } 131 132 // ordering operator <(const axis_transformation & a) const133 bool operator<(const axis_transformation& a) const { 134 return atr_ < a.atr_; 135 } 136 137 // concatenate this with that operator +=(const axis_transformation & a)138 axis_transformation& operator+=(const axis_transformation& a) { 139 bool abit2 = (a.atr_ & 4) != 0; 140 bool abit1 = (a.atr_ & 2) != 0; 141 bool abit0 = (a.atr_ & 1) != 0; 142 bool bit2 = (atr_ & 4) != 0; 143 bool bit1 = (atr_ & 2) != 0; 144 bool bit0 = (atr_ & 1) != 0; 145 int indexes[2][2] = { 146 { (int)bit2, (int)(!bit2) }, 147 { (int)abit2, (int)(!abit2) } 148 }; 149 int zero_bits[2][2] = { 150 {bit0, bit1}, {abit0, abit1} 151 }; 152 int nbit1 = zero_bits[0][1] ^ zero_bits[1][indexes[0][1]]; 153 int nbit0 = zero_bits[0][0] ^ zero_bits[1][indexes[0][0]]; 154 indexes[0][0] = indexes[1][indexes[0][0]]; 155 indexes[0][1] = indexes[1][indexes[0][1]]; 156 int nbit2 = indexes[0][0] & 1; // swap xy 157 atr_ = (ATR)((nbit2 << 2) + (nbit1 << 1) + nbit0); 158 return *this; 159 } 160 161 // concatenation operator operator +(const axis_transformation & a) const162 axis_transformation operator+(const axis_transformation& a) const { 163 axis_transformation retval(*this); 164 return retval+=a; 165 } 166 167 // populate_axis_array writes the three INDIVIDUAL_AXIS values that the 168 // ATR enum value of 'this' represent into axis_array populate_axis_array(INDIVIDUAL_AXIS axis_array[]) const169 void populate_axis_array(INDIVIDUAL_AXIS axis_array[]) const { 170 bool bit2 = (atr_ & 4) != 0; 171 bool bit1 = (atr_ & 2) != 0; 172 bool bit0 = (atr_ & 1) != 0; 173 axis_array[1] = (INDIVIDUAL_AXIS)(((int)(!bit2) << 1) + bit1); 174 axis_array[0] = (INDIVIDUAL_AXIS)(((int)(bit2) << 1) + bit0); 175 } 176 177 // it is recommended that the directions stored in an array 178 // in the caller code for easier isotropic access by orientation value get_directions(direction_2d & horizontal_dir,direction_2d & vertical_dir) const179 void get_directions(direction_2d& horizontal_dir, 180 direction_2d& vertical_dir) const { 181 bool bit2 = (atr_ & 4) != 0; 182 bool bit1 = (atr_ & 2) != 0; 183 bool bit0 = (atr_ & 1) != 0; 184 vertical_dir = direction_2d((direction_2d_enum)(((int)(!bit2) << 1) + !bit1)); 185 horizontal_dir = direction_2d((direction_2d_enum)(((int)(bit2) << 1) + !bit0)); 186 } 187 188 // combine_axis_arrays concatenates this_array and that_array overwriting 189 // the result into this_array combine_axis_arrays(INDIVIDUAL_AXIS this_array[],const INDIVIDUAL_AXIS that_array[])190 static void combine_axis_arrays(INDIVIDUAL_AXIS this_array[], 191 const INDIVIDUAL_AXIS that_array[]) { 192 int indexes[2] = { this_array[0] >> 1, this_array[1] >> 1 }; 193 int zero_bits[2][2] = { 194 { this_array[0] & 1, this_array[1] & 1 }, 195 { that_array[0] & 1, that_array[1] & 1 } 196 }; 197 this_array[0] = (INDIVIDUAL_AXIS)((int)this_array[0] | 198 ((int)zero_bits[0][0] ^ 199 (int)zero_bits[1][indexes[0]])); 200 this_array[1] = (INDIVIDUAL_AXIS)((int)this_array[1] | 201 ((int)zero_bits[0][1] ^ 202 (int)zero_bits[1][indexes[1]])); 203 } 204 205 // write_back_axis_array converts an array of three INDIVIDUAL_AXIS values 206 // to the ATR enum value and sets 'this' to that value write_back_axis_array(const INDIVIDUAL_AXIS this_array[])207 void write_back_axis_array(const INDIVIDUAL_AXIS this_array[]) { 208 int bit2 = ((int)this_array[0] & 2) != 0; // swap xy 209 int bit1 = ((int)this_array[1] & 1); 210 int bit0 = ((int)this_array[0] & 1); 211 atr_ = ATR((bit2 << 2) + (bit1 << 1) + bit0); 212 } 213 214 // behavior is deterministic but undefined in the case where illegal 215 // combinations of directions are passed in. set_directions(const direction_2d & horizontal_dir,const direction_2d & vertical_dir)216 axis_transformation& set_directions(const direction_2d& horizontal_dir, 217 const direction_2d& vertical_dir) { 218 int bit2 = (static_cast<orientation_2d>(horizontal_dir).to_int()) != 0; 219 int bit1 = !(vertical_dir.to_int() & 1); 220 int bit0 = !(horizontal_dir.to_int() & 1); 221 atr_ = ATR((bit2 << 2) + (bit1 << 1) + bit0); 222 return *this; 223 } 224 225 // transform the three coordinates by reference 226 template <typename coordinate_type> transform(coordinate_type & x,coordinate_type & y) const227 void transform(coordinate_type& x, coordinate_type& y) const { 228 int bit2 = (atr_ & 4) != 0; 229 int bit1 = (atr_ & 2) != 0; 230 int bit0 = (atr_ & 1) != 0; 231 x *= -((bit0 << 1) - 1); 232 y *= -((bit1 << 1) - 1); 233 predicated_swap(bit2 != 0, x, y); 234 } 235 236 // invert this axis_transformation invert()237 axis_transformation& invert() { 238 int bit2 = ((atr_ & 4) != 0); 239 int bit1 = ((atr_ & 2) != 0); 240 int bit0 = ((atr_ & 1) != 0); 241 // swap bit 0 and bit 1 if bit2 is 1 242 predicated_swap(bit2 != 0, bit0, bit1); 243 bit1 = bit1 << 1; 244 atr_ = (ATR)(atr_ & (32+16+8+4)); // mask away bit0 and bit1 245 atr_ = (ATR)(atr_ | bit0 | bit1); 246 return *this; 247 } 248 249 // get the inverse axis_transformation of this inverse() const250 axis_transformation inverse() const { 251 axis_transformation retval(*this); 252 return retval.invert(); 253 } 254 255 private: 256 ATR atr_; 257 }; 258 259 // Scaling object to be used to store the scale factor for each axis. 260 // For use by the transformation object, in that context the scale factor 261 // is the amount that each axis scales by when transformed. 262 template <typename scale_factor_type> 263 class anisotropic_scale_factor { 264 public: anisotropic_scale_factor()265 anisotropic_scale_factor() { 266 scale_[0] = 1; 267 scale_[1] = 1; 268 } anisotropic_scale_factor(scale_factor_type xscale,scale_factor_type yscale)269 anisotropic_scale_factor(scale_factor_type xscale, 270 scale_factor_type yscale) { 271 scale_[0] = xscale; 272 scale_[1] = yscale; 273 } 274 275 // get a component of the anisotropic_scale_factor by orientation get(orientation_2d orient) const276 scale_factor_type get(orientation_2d orient) const { 277 return scale_[orient.to_int()]; 278 } 279 280 // set a component of the anisotropic_scale_factor by orientation set(orientation_2d orient,scale_factor_type value)281 void set(orientation_2d orient, scale_factor_type value) { 282 scale_[orient.to_int()] = value; 283 } 284 x() const285 scale_factor_type x() const { 286 return scale_[HORIZONTAL]; 287 } 288 y() const289 scale_factor_type y() const { 290 return scale_[VERTICAL]; 291 } 292 x(scale_factor_type value)293 void x(scale_factor_type value) { 294 scale_[HORIZONTAL] = value; 295 } 296 y(scale_factor_type value)297 void y(scale_factor_type value) { 298 scale_[VERTICAL] = value; 299 } 300 301 // concatination operator (convolve scale factors) operator +(const anisotropic_scale_factor & s) const302 anisotropic_scale_factor operator+(const anisotropic_scale_factor& s) const { 303 anisotropic_scale_factor<scale_factor_type> retval(*this); 304 return retval += s; 305 } 306 307 // concatinate this with that operator +=(const anisotropic_scale_factor & s)308 const anisotropic_scale_factor& operator+=( 309 const anisotropic_scale_factor& s) { 310 scale_[0] *= s.scale_[0]; 311 scale_[1] *= s.scale_[1]; 312 return *this; 313 } 314 315 // transform this scale with an axis_transform transform(axis_transformation atr)316 anisotropic_scale_factor& transform(axis_transformation atr) { 317 direction_2d dirs[2]; 318 atr.get_directions(dirs[0], dirs[1]); 319 scale_factor_type tmp[2] = {scale_[0], scale_[1]}; 320 for (int i = 0; i < 2; ++i) { 321 scale_[orientation_2d(dirs[i]).to_int()] = tmp[i]; 322 } 323 return *this; 324 } 325 326 // scale the two coordinates 327 template <typename coordinate_type> scale(coordinate_type & x,coordinate_type & y) const328 void scale(coordinate_type& x, coordinate_type& y) const { 329 x = scaling_policy<coordinate_type>::round( 330 (scale_factor_type)x * get(HORIZONTAL)); 331 y = scaling_policy<coordinate_type>::round( 332 (scale_factor_type)y * get(HORIZONTAL)); 333 } 334 335 // invert this scale factor to give the reverse scale factor invert()336 anisotropic_scale_factor& invert() { 337 x(1/x()); 338 y(1/y()); 339 return *this; 340 } 341 342 private: 343 scale_factor_type scale_[2]; 344 }; 345 346 // Transformation object, stores and provides services for transformations. 347 // Consits of axis transformation, scale factor and translation. 348 // The tranlation is the position of the origin of the new coordinate system of 349 // in the old system. Coordinates are scaled before they are transformed. 350 template <typename coordinate_type> 351 class transformation { 352 public: transformation()353 transformation() : atr_(), p_(0, 0) {} transformation(axis_transformation atr)354 explicit transformation(axis_transformation atr) : atr_(atr), p_(0, 0) {} transformation(axis_transformation::ATR atr)355 explicit transformation(axis_transformation::ATR atr) : atr_(atr), p_(0, 0) {} transformation(const transformation & tr)356 transformation(const transformation& tr) : atr_(tr.atr_), p_(tr.p_) {} 357 358 template <typename point_type> transformation(const point_type & p)359 explicit transformation(const point_type& p) : atr_(), p_(0, 0) { 360 set_translation(p); 361 } 362 363 template <typename point_type> transformation(axis_transformation atr,const point_type & p)364 transformation(axis_transformation atr, 365 const point_type& p) : atr_(atr), p_(0, 0) { 366 set_translation(p); 367 } 368 369 template <typename point_type> transformation(axis_transformation atr,const point_type & referencePt,const point_type & destinationPt)370 transformation(axis_transformation atr, 371 const point_type& referencePt, 372 const point_type& destinationPt) : atr_(), p_(0, 0) { 373 transformation<coordinate_type> tmp(referencePt); 374 transformation<coordinate_type> rotRef(atr); 375 transformation<coordinate_type> tmpInverse = tmp.inverse(); 376 point_type decon(referencePt); 377 deconvolve(decon, destinationPt); 378 transformation<coordinate_type> displacement(decon); 379 tmp += rotRef; 380 tmp += tmpInverse; 381 tmp += displacement; 382 (*this) = tmp; 383 } 384 385 // equivalence operator operator ==(const transformation & tr) const386 bool operator==(const transformation& tr) const { 387 return (atr_ == tr.atr_) && (p_ == tr.p_); 388 } 389 390 // inequivalence operator operator !=(const transformation & tr) const391 bool operator!=(const transformation& tr) const { 392 return !(*this == tr); 393 } 394 395 // ordering operator <(const transformation & tr) const396 bool operator<(const transformation& tr) const { 397 return (atr_ < tr.atr_) || ((atr_ == tr.atr_) && (p_ < tr.p_)); 398 } 399 400 // concatenation operator operator +(const transformation & tr) const401 transformation operator+(const transformation& tr) const { 402 transformation<coordinate_type> retval(*this); 403 return retval+=tr; 404 } 405 406 // concatenate this with that operator +=(const transformation & tr)407 const transformation& operator+=(const transformation& tr) { 408 coordinate_type x, y; 409 transformation<coordinate_type> inv = inverse(); 410 inv.transform(x, y); 411 p_.set(HORIZONTAL, p_.get(HORIZONTAL) + x); 412 p_.set(VERTICAL, p_.get(VERTICAL) + y); 413 // concatenate axis transforms 414 atr_ += tr.atr_; 415 return *this; 416 } 417 418 // get the axis_transformation portion of this get_axis_transformation() const419 axis_transformation get_axis_transformation() const { 420 return atr_; 421 } 422 423 // set the axis_transformation portion of this set_axis_transformation(const axis_transformation & atr)424 void set_axis_transformation(const axis_transformation& atr) { 425 atr_ = atr; 426 } 427 428 // get the translation 429 template <typename point_type> get_translation(point_type & p) const430 void get_translation(point_type& p) const { 431 assign(p, p_); 432 } 433 434 // set the translation 435 template <typename point_type> set_translation(const point_type & p)436 void set_translation(const point_type& p) { 437 assign(p_, p); 438 } 439 440 // apply the 2D portion of this transformation to the two coordinates given transform(coordinate_type & x,coordinate_type & y) const441 void transform(coordinate_type& x, coordinate_type& y) const { 442 y -= p_.get(VERTICAL); 443 x -= p_.get(HORIZONTAL); 444 atr_.transform(x, y); 445 } 446 447 // invert this transformation invert()448 transformation& invert() { 449 coordinate_type x = p_.get(HORIZONTAL), y = p_.get(VERTICAL); 450 atr_.transform(x, y); 451 x *= -1; 452 y *= -1; 453 p_ = point_data<coordinate_type>(x, y); 454 atr_.invert(); 455 return *this; 456 } 457 458 // get the inverse of this transformation inverse() const459 transformation inverse() const { 460 transformation<coordinate_type> ret_val(*this); 461 return ret_val.invert(); 462 } 463 get_directions(direction_2d & horizontal_dir,direction_2d & vertical_dir) const464 void get_directions(direction_2d& horizontal_dir, 465 direction_2d& vertical_dir) const { 466 return atr_.get_directions(horizontal_dir, vertical_dir); 467 } 468 469 private: 470 axis_transformation atr_; 471 point_data<coordinate_type> p_; 472 }; 473 } // polygon 474 } // boost 475 476 #endif // BOOST_POLYGON_TRANSFORM_HPP 477