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 | |
88 | axis_transformation() : atr_(NULL_TRANSFORM) {} |
89 | explicit axis_transformation(ATR atr) : atr_(atr) {} |
90 | axis_transformation(const axis_transformation& atr) : atr_(atr.atr_) {} |
91 | |
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 | |
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 |
111 | axis_transformation& operator=(const axis_transformation& a) { |
112 | atr_ = a.atr_; |
113 | return *this; |
114 | } |
115 | |
116 | // assignment operator |
117 | axis_transformation& operator=(const ATR& atr) { |
118 | atr_ = atr; |
119 | return *this; |
120 | } |
121 | |
122 | // equivalence operator |
123 | bool operator==(const axis_transformation& a) const { |
124 | return atr_ == a.atr_; |
125 | } |
126 | |
127 | // inequivalence operator |
128 | bool operator!=(const axis_transformation& a) const { |
129 | return !(*this == a); |
130 | } |
131 | |
132 | // ordering |
133 | bool operator<(const axis_transformation& a) const { |
134 | return atr_ < a.atr_; |
135 | } |
136 | |
137 | // concatenate this with that |
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 |
162 | 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 |
169 | 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 |
179 | 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 |
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 |
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. |
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> |
227 | 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 |
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(pred: bit2 != 0, a&: bit0, b&: 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 |
250 | 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: |
265 | anisotropic_scale_factor() { |
266 | scale_[0] = 1; |
267 | scale_[1] = 1; |
268 | } |
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 |
276 | 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 |
281 | void set(orientation_2d orient, scale_factor_type value) { |
282 | scale_[orient.to_int()] = value; |
283 | } |
284 | |
285 | scale_factor_type x() const { |
286 | return scale_[HORIZONTAL]; |
287 | } |
288 | |
289 | scale_factor_type y() const { |
290 | return scale_[VERTICAL]; |
291 | } |
292 | |
293 | void x(scale_factor_type value) { |
294 | scale_[HORIZONTAL] = value; |
295 | } |
296 | |
297 | void y(scale_factor_type value) { |
298 | scale_[VERTICAL] = value; |
299 | } |
300 | |
301 | // concatination operator (convolve scale factors) |
302 | 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 |
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 |
316 | anisotropic_scale_factor& transform(axis_transformation atr) { |
317 | direction_2d dirs[2]; |
318 | atr.get_directions(horizontal_dir&: dirs[0], vertical_dir&: 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> |
328 | void scale(coordinate_type& x, coordinate_type& y) const { |
329 | x = scaling_policy<coordinate_type>::round( |
330 | (scale_factor_type)x * get(orient: HORIZONTAL)); |
331 | y = scaling_policy<coordinate_type>::round( |
332 | (scale_factor_type)y * get(orient: HORIZONTAL)); |
333 | } |
334 | |
335 | // invert this scale factor to give the reverse scale factor |
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: |
353 | transformation() : atr_(), p_(0, 0) {} |
354 | explicit transformation(axis_transformation atr) : atr_(atr), p_(0, 0) {} |
355 | explicit transformation(axis_transformation::ATR atr) : atr_(atr), p_(0, 0) {} |
356 | transformation(const transformation& tr) : atr_(tr.atr_), p_(tr.p_) {} |
357 | |
358 | template <typename point_type> |
359 | explicit transformation(const point_type& p) : atr_(), p_(0, 0) { |
360 | set_translation(p); |
361 | } |
362 | |
363 | template <typename point_type> |
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> |
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 |
386 | bool operator==(const transformation& tr) const { |
387 | return (atr_ == tr.atr_) && (p_ == tr.p_); |
388 | } |
389 | |
390 | // inequivalence operator |
391 | bool operator!=(const transformation& tr) const { |
392 | return !(*this == tr); |
393 | } |
394 | |
395 | // ordering |
396 | bool operator<(const transformation& tr) const { |
397 | return (atr_ < tr.atr_) || ((atr_ == tr.atr_) && (p_ < tr.p_)); |
398 | } |
399 | |
400 | // concatenation operator |
401 | transformation operator+(const transformation& tr) const { |
402 | transformation<coordinate_type> retval(*this); |
403 | return retval+=tr; |
404 | } |
405 | |
406 | // concatenate this with that |
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 |
419 | axis_transformation get_axis_transformation() const { |
420 | return atr_; |
421 | } |
422 | |
423 | // set the axis_transformation portion of this |
424 | void set_axis_transformation(const axis_transformation& atr) { |
425 | atr_ = atr; |
426 | } |
427 | |
428 | // get the translation |
429 | template <typename point_type> |
430 | void get_translation(point_type& p) const { |
431 | assign(p, p_); |
432 | } |
433 | |
434 | // set the translation |
435 | template <typename point_type> |
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 |
441 | 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 |
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 |
459 | transformation inverse() const { |
460 | transformation<coordinate_type> ret_val(*this); |
461 | return ret_val.invert(); |
462 | } |
463 | |
464 | 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 | |