1/*
2 Copyright 2008 Intel Corporation
3
4 Use, modification and distribution are subject to the Boost Software License,
5 Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
6 http://www.boost.org/LICENSE_1_0.txt).
7*/
8#ifndef BOOST_POLYGON_POLYGON_90_SET_DATA_HPP
9#define BOOST_POLYGON_POLYGON_90_SET_DATA_HPP
10#include "isotropy.hpp"
11#include "point_concept.hpp"
12#include "transform.hpp"
13#include "interval_concept.hpp"
14#include "rectangle_concept.hpp"
15#include "segment_concept.hpp"
16#include "detail/iterator_points_to_compact.hpp"
17#include "detail/iterator_compact_to_points.hpp"
18#include "polygon_traits.hpp"
19
20//manhattan boolean algorithms
21#include "detail/boolean_op.hpp"
22#include "detail/polygon_formation.hpp"
23#include "detail/rectangle_formation.hpp"
24#include "detail/max_cover.hpp"
25#include "detail/property_merge.hpp"
26#include "detail/polygon_90_touch.hpp"
27#include "detail/iterator_geometry_to_set.hpp"
28
29namespace boost { namespace polygon{
30 template <typename ltype, typename rtype, typename op_type>
31 class polygon_90_set_view;
32
33 template <typename T>
34 class polygon_90_set_data {
35 public:
36 typedef T coordinate_type;
37 typedef std::vector<std::pair<coordinate_type, std::pair<coordinate_type, int> > > value_type;
38 typedef typename std::vector<std::pair<coordinate_type, std::pair<coordinate_type, int> > >::const_iterator iterator_type;
39 typedef polygon_90_set_data operator_arg_type;
40
41 // default constructor
42 inline polygon_90_set_data() : orient_(HORIZONTAL), data_(), dirty_(false), unsorted_(false) {}
43
44 // constructor
45 inline polygon_90_set_data(orientation_2d orient) : orient_(orient), data_(), dirty_(false), unsorted_(false) {}
46
47 // constructor from an iterator pair over vertex data
48 template <typename iT>
49 inline polygon_90_set_data(orientation_2d, iT input_begin, iT input_end) :
50 orient_(HORIZONTAL), data_(), dirty_(false), unsorted_(false) {
51 dirty_ = true;
52 unsorted_ = true;
53 for( ; input_begin != input_end; ++input_begin) { insert(*input_begin); }
54 }
55
56 // copy constructor
57 inline polygon_90_set_data(const polygon_90_set_data& that) :
58 orient_(that.orient_), data_(that.data_), dirty_(that.dirty_), unsorted_(that.unsorted_) {}
59
60 template <typename ltype, typename rtype, typename op_type>
61 inline polygon_90_set_data(const polygon_90_set_view<ltype, rtype, op_type>& that);
62
63 // copy with orientation change constructor
64 inline polygon_90_set_data(orientation_2d orient, const polygon_90_set_data& that) :
65 orient_(orient), data_(), dirty_(false), unsorted_(false) {
66 insert(that, false, that.orient_);
67 }
68
69 // destructor
70 inline ~polygon_90_set_data() {}
71
72 // assignement operator
73 inline polygon_90_set_data& operator=(const polygon_90_set_data& that) {
74 if(this == &that) return *this;
75 orient_ = that.orient_;
76 data_ = that.data_;
77 dirty_ = that.dirty_;
78 unsorted_ = that.unsorted_;
79 return *this;
80 }
81
82 template <typename ltype, typename rtype, typename op_type>
83 inline polygon_90_set_data& operator=(const polygon_90_set_view<ltype, rtype, op_type>& that);
84
85 template <typename geometry_object>
86 inline polygon_90_set_data& operator=(const geometry_object& geometry) {
87 data_.clear();
88 insert(geometry);
89 return *this;
90 }
91
92 // insert iterator range
93 inline void insert(iterator_type input_begin, iterator_type input_end, orientation_2d orient = HORIZONTAL) {
94 if(input_begin == input_end || (!data_.empty() && &(*input_begin) == &(*(data_.begin())))) return;
95 dirty_ = true;
96 unsorted_ = true;
97 if(orient == orient_)
98 data_.insert(data_.end(), input_begin, input_end);
99 else {
100 for( ; input_begin != input_end; ++input_begin) {
101 insert(*input_begin, false, orient);
102 }
103 }
104 }
105
106 // insert iterator range
107 template <typename iT>
108 inline void insert(iT input_begin, iT input_end, orientation_2d orient = HORIZONTAL) {
109 if(input_begin == input_end) return;
110 dirty_ = true;
111 unsorted_ = true;
112 for( ; input_begin != input_end; ++input_begin) {
113 insert(*input_begin, false, orient);
114 }
115 }
116
117 inline void insert(const polygon_90_set_data& polygon_set) {
118 insert(polygon_set.begin(), polygon_set.end(), polygon_set.orient());
119 }
120
121 inline void insert(const std::pair<std::pair<point_data<coordinate_type>, point_data<coordinate_type> >, int>& edge, bool is_hole = false,
122 orientation_2d = HORIZONTAL) {
123 std::pair<coordinate_type, std::pair<coordinate_type, int> > vertex;
124 vertex.first = edge.first.first.x();
125 vertex.second.first = edge.first.first.y();
126 vertex.second.second = edge.second * (is_hole ? -1 : 1);
127 insert(vertex, false, VERTICAL);
128 vertex.first = edge.first.second.x();
129 vertex.second.first = edge.first.second.y();
130 vertex.second.second *= -1;
131 insert(vertex, false, VERTICAL);
132 }
133
134 template <typename geometry_type>
135 inline void insert(const geometry_type& geometry_object, bool is_hole = false, orientation_2d = HORIZONTAL) {
136 iterator_geometry_to_set<typename geometry_concept<geometry_type>::type, geometry_type>
137 begin_input(geometry_object, LOW, orient_, is_hole), end_input(geometry_object, HIGH, orient_, is_hole);
138 insert(begin_input, end_input, orient_);
139 }
140
141 inline void insert(const std::pair<coordinate_type, std::pair<coordinate_type, int> >& vertex, bool is_hole = false,
142 orientation_2d orient = HORIZONTAL) {
143 data_.push_back(vertex);
144 if(orient != orient_) std::swap(data_.back().first, data_.back().second.first);
145 if(is_hole) data_.back().second.second *= -1;
146 dirty_ = true;
147 unsorted_ = true;
148 }
149
150 inline void insert(coordinate_type major_coordinate, const std::pair<interval_data<coordinate_type>, int>& edge) {
151 std::pair<coordinate_type, std::pair<coordinate_type, int> > vertex;
152 vertex.first = major_coordinate;
153 vertex.second.first = edge.first.get(LOW);
154 vertex.second.second = edge.second;
155 insert(vertex, false, orient_);
156 vertex.second.first = edge.first.get(HIGH);
157 vertex.second.second *= -1;
158 insert(vertex, false, orient_);
159 }
160
161 template <typename output_container>
162 inline void get(output_container& output) const {
163 get_dispatch(output, typename geometry_concept<typename output_container::value_type>::type());
164 }
165
166 template <typename output_container>
167 inline void get(output_container& output, size_t vthreshold) const {
168 get_dispatch(output, typename geometry_concept<typename output_container::value_type>::type(), vthreshold);
169 }
170
171
172 template <typename output_container>
173 inline void get_polygons(output_container& output) const {
174 get_dispatch(output, polygon_90_concept());
175 }
176
177 template <typename output_container>
178 inline void get_rectangles(output_container& output) const {
179 clean();
180 form_rectangles(output, data_.begin(), data_.end(), orient_, rectangle_concept());
181 }
182
183 template <typename output_container>
184 inline void get_rectangles(output_container& output, orientation_2d slicing_orientation) const {
185 if(slicing_orientation == orient_) {
186 get_rectangles(output);
187 } else {
188 polygon_90_set_data<coordinate_type> ps(*this);
189 ps.transform(axis_transformation(axis_transformation::SWAP_XY));
190 output_container result;
191 ps.get_rectangles(result);
192 for(typename output_container::iterator itr = result.begin(); itr != result.end(); ++itr) {
193 ::boost::polygon::transform(*itr, axis_transformation(axis_transformation::SWAP_XY));
194 }
195 output.insert(output.end(), result.begin(), result.end());
196 }
197 }
198
199 // equivalence operator
200 inline bool operator==(const polygon_90_set_data& p) const {
201 if(orient_ == p.orient()) {
202 clean();
203 p.clean();
204 return data_ == p.data_;
205 } else {
206 return false;
207 }
208 }
209
210 // inequivalence operator
211 inline bool operator!=(const polygon_90_set_data& p) const {
212 return !((*this) == p);
213 }
214
215 // get iterator to begin vertex data
216 inline iterator_type begin() const {
217 return data_.begin();
218 }
219
220 // get iterator to end vertex data
221 inline iterator_type end() const {
222 return data_.end();
223 }
224
225 const value_type& value() const {
226 return data_;
227 }
228
229 // clear the contents of the polygon_90_set_data
230 inline void clear() { data_.clear(); dirty_ = unsorted_ = false; }
231
232 // find out if Polygon set is empty
233 inline bool empty() const { clean(); return data_.empty(); }
234
235 // get the Polygon set size in vertices
236 inline std::size_t size() const { clean(); return data_.size(); }
237
238 // get the current Polygon set capacity in vertices
239 inline std::size_t capacity() const { return data_.capacity(); }
240
241 // reserve size of polygon set in vertices
242 inline void reserve(std::size_t size) { return data_.reserve(size); }
243
244 // find out if Polygon set is sorted
245 inline bool sorted() const { return !unsorted_; }
246
247 // find out if Polygon set is clean
248 inline bool dirty() const { return dirty_; }
249
250 // get the scanline orientation of the polygon set
251 inline orientation_2d orient() const { return orient_; }
252
253 // Start BM
254 // The problem: If we have two polygon sets with two different scanline orientations:
255 // I tried changing the orientation of one to coincide with other (If not, resulting boolean operation
256 // produces spurious results).
257 // First I tried copying polygon data from one of the sets into another set with corrected orientation
258 // using one of the copy constructor that takes in orientation (see somewhere above in this file) --> copy constructor throws error
259 // Then I tried another approach:(see below). This approach also fails to produce the desired results when test case is run.
260 // Here is the part that beats me: If I comment out the whole section, I can do all the operations (^=, -=, &= )these commented out
261 // operations perform. So then why do we need them?. Hence, I commented out this whole section.
262 // End BM
263 // polygon_90_set_data<coordinate_type>& operator-=(const polygon_90_set_data& that) {
264 // sort();
265 // that.sort();
266 // value_type data;
267 // std::swap(data, data_);
268 // applyBooleanBinaryOp(data.begin(), data.end(),
269 // that.begin(), that.end(), boolean_op::BinaryCount<boolean_op::BinaryNot>());
270 // return *this;
271 // }
272 // polygon_90_set_data<coordinate_type>& operator^=(const polygon_90_set_data& that) {
273 // sort();
274 // that.sort();
275 // value_type data;
276 // std::swap(data, data_);
277 // applyBooleanBinaryOp(data.begin(), data.end(),
278 // that.begin(), that.end(), boolean_op::BinaryCount<boolean_op::BinaryXor>());
279 // return *this;
280 // }
281 // polygon_90_set_data<coordinate_type>& operator&=(const polygon_90_set_data& that) {
282 // sort();
283 // that.sort();
284 // value_type data;
285 // std::swap(data, data_);
286 // applyBooleanBinaryOp(data.begin(), data.end(),
287 // that.begin(), that.end(), boolean_op::BinaryCount<boolean_op::BinaryAnd>());
288 // return *this;
289 // }
290 // polygon_90_set_data<coordinate_type>& operator|=(const polygon_90_set_data& that) {
291 // insert(that);
292 // return *this;
293 // }
294
295 void clean() const {
296 sort();
297 if(dirty_) {
298 boolean_op::default_arg_workaround<int>::applyBooleanOr(data_);
299 dirty_ = false;
300 }
301 }
302
303 void sort() const{
304 if(unsorted_) {
305 polygon_sort(data_.begin(), data_.end());
306 unsorted_ = false;
307 }
308 }
309
310 template <typename input_iterator_type>
311 void set(input_iterator_type input_begin, input_iterator_type input_end, orientation_2d orient) {
312 data_.clear();
313 reserve(size: std::distance(input_begin, input_end));
314 data_.insert(data_.end(), input_begin, input_end);
315 orient_ = orient;
316 dirty_ = true;
317 unsorted_ = true;
318 }
319
320 void set(const value_type& value, orientation_2d orient) {
321 data_ = value;
322 orient_ = orient;
323 dirty_ = true;
324 unsorted_ = true;
325 }
326
327 //extents
328 template <typename rectangle_type>
329 bool
330 extents(rectangle_type& extents_rectangle) const {
331 clean();
332 if(data_.empty()) return false;
333 if(orient_ == HORIZONTAL)
334 set_points(extents_rectangle, point_data<coordinate_type>(data_[0].second.first, data_[0].first),
335 point_data<coordinate_type>(data_[data_.size() - 1].second.first, data_[data_.size() - 1].first));
336 else
337 set_points(extents_rectangle, point_data<coordinate_type>(data_[0].first, data_[0].second.first),
338 point_data<coordinate_type>(data_[data_.size() - 1].first, data_[data_.size() - 1].second.first));
339 for(std::size_t i = 1; i < data_.size() - 1; ++i) {
340 if(orient_ == HORIZONTAL)
341 encompass(extents_rectangle, point_data<coordinate_type>(data_[i].second.first, data_[i].first));
342 else
343 encompass(extents_rectangle, point_data<coordinate_type>(data_[i].first, data_[i].second.first));
344 }
345 return true;
346 }
347
348 polygon_90_set_data&
349 bloat2(typename coordinate_traits<coordinate_type>::unsigned_area_type west_bloating,
350 typename coordinate_traits<coordinate_type>::unsigned_area_type east_bloating,
351 typename coordinate_traits<coordinate_type>::unsigned_area_type south_bloating,
352 typename coordinate_traits<coordinate_type>::unsigned_area_type north_bloating) {
353 std::vector<rectangle_data<coordinate_type> > rects;
354 clean();
355 rects.reserve(data_.size() / 2);
356 get(rects);
357 rectangle_data<coordinate_type> convolutionRectangle(interval_data<coordinate_type>(-((coordinate_type)west_bloating),
358 (coordinate_type)east_bloating),
359 interval_data<coordinate_type>(-((coordinate_type)south_bloating),
360 (coordinate_type)north_bloating));
361 for(typename std::vector<rectangle_data<coordinate_type> >::iterator itr = rects.begin();
362 itr != rects.end(); ++itr) {
363 convolve(*itr, convolutionRectangle);
364 }
365 clear();
366 insert(rects.begin(), rects.end());
367 return *this;
368 }
369
370 static void modify_pt(point_data<coordinate_type>& pt, const point_data<coordinate_type>& prev_pt,
371 const point_data<coordinate_type>& current_pt, const point_data<coordinate_type>& next_pt,
372 coordinate_type west_bloating,
373 coordinate_type east_bloating,
374 coordinate_type south_bloating,
375 coordinate_type north_bloating) {
376 bool pxl = prev_pt.x() < current_pt.x();
377 bool pyl = prev_pt.y() < current_pt.y();
378 bool nxl = next_pt.x() < current_pt.x();
379 bool nyl = next_pt.y() < current_pt.y();
380 bool pxg = prev_pt.x() > current_pt.x();
381 bool pyg = prev_pt.y() > current_pt.y();
382 bool nxg = next_pt.x() > current_pt.x();
383 bool nyg = next_pt.y() > current_pt.y();
384 //two of the four if statements will execute
385 if(pxl)
386 pt.y(current_pt.y() - south_bloating);
387 if(pxg)
388 pt.y(current_pt.y() + north_bloating);
389 if(nxl)
390 pt.y(current_pt.y() + north_bloating);
391 if(nxg)
392 pt.y(current_pt.y() - south_bloating);
393 if(pyl)
394 pt.x(current_pt.x() + east_bloating);
395 if(pyg)
396 pt.x(current_pt.x() - west_bloating);
397 if(nyl)
398 pt.x(current_pt.x() - west_bloating);
399 if(nyg)
400 pt.x(current_pt.x() + east_bloating);
401 }
402 static void resize_poly_up(std::vector<point_data<coordinate_type> >& poly,
403 coordinate_type west_bloating,
404 coordinate_type east_bloating,
405 coordinate_type south_bloating,
406 coordinate_type north_bloating) {
407 point_data<coordinate_type> first_pt = poly[0];
408 point_data<coordinate_type> second_pt = poly[1];
409 point_data<coordinate_type> prev_pt = poly[0];
410 point_data<coordinate_type> current_pt = poly[1];
411 for(std::size_t i = 2; i < poly.size(); ++i) {
412 point_data<coordinate_type> next_pt = poly[i];
413 modify_pt(pt&: poly[i-1], prev_pt, current_pt, next_pt, west_bloating, east_bloating, south_bloating, north_bloating);
414 prev_pt = current_pt;
415 current_pt = next_pt;
416 }
417 point_data<coordinate_type> next_pt = first_pt;
418 modify_pt(pt&: poly.back(), prev_pt, current_pt, next_pt, west_bloating, east_bloating, south_bloating, north_bloating);
419 prev_pt = current_pt;
420 current_pt = next_pt;
421 next_pt = second_pt;
422 modify_pt(pt&: poly[0], prev_pt, current_pt, next_pt, west_bloating, east_bloating, south_bloating, north_bloating);
423 remove_colinear_pts(poly);
424 }
425 static bool resize_poly_down(std::vector<point_data<coordinate_type> >& poly,
426 coordinate_type west_shrinking,
427 coordinate_type east_shrinking,
428 coordinate_type south_shrinking,
429 coordinate_type north_shrinking) {
430 rectangle_data<coordinate_type> extents_rectangle;
431 set_points(extents_rectangle, poly[0], poly[0]);
432 point_data<coordinate_type> first_pt = poly[0];
433 point_data<coordinate_type> second_pt = poly[1];
434 point_data<coordinate_type> prev_pt = poly[0];
435 point_data<coordinate_type> current_pt = poly[1];
436 encompass(extents_rectangle, current_pt);
437 for(std::size_t i = 2; i < poly.size(); ++i) {
438 point_data<coordinate_type> next_pt = poly[i];
439 encompass(extents_rectangle, next_pt);
440 modify_pt(pt&: poly[i-1], prev_pt, current_pt, next_pt, west_bloating: west_shrinking, east_bloating: east_shrinking, south_bloating: south_shrinking, north_bloating: north_shrinking);
441 prev_pt = current_pt;
442 current_pt = next_pt;
443 }
444 if(delta(extents_rectangle, HORIZONTAL) < std::abs(west_shrinking + east_shrinking))
445 return false;
446 if(delta(extents_rectangle, VERTICAL) < std::abs(north_shrinking + south_shrinking))
447 return false;
448 point_data<coordinate_type> next_pt = first_pt;
449 modify_pt(pt&: poly.back(), prev_pt, current_pt, next_pt, west_bloating: west_shrinking, east_bloating: east_shrinking, south_bloating: south_shrinking, north_bloating: north_shrinking);
450 prev_pt = current_pt;
451 current_pt = next_pt;
452 next_pt = second_pt;
453 modify_pt(pt&: poly[0], prev_pt, current_pt, next_pt, west_bloating: west_shrinking, east_bloating: east_shrinking, south_bloating: south_shrinking, north_bloating: north_shrinking);
454 return remove_colinear_pts(poly);
455 }
456
457 static bool remove_colinear_pts(std::vector<point_data<coordinate_type> >& poly) {
458 bool found_colinear = true;
459 while(found_colinear && poly.size() >= 4) {
460 found_colinear = false;
461 typename std::vector<point_data<coordinate_type> >::iterator itr = poly.begin();
462 itr += poly.size() - 1; //get last element position
463 typename std::vector<point_data<coordinate_type> >::iterator itr2 = poly.begin();
464 typename std::vector<point_data<coordinate_type> >::iterator itr3 = itr2;
465 ++itr3;
466 std::size_t count = 0;
467 for( ; itr3 < poly.end(); ++itr3) {
468 if(((*itr).x() == (*itr2).x() && (*itr).x() == (*itr3).x()) ||
469 ((*itr).y() == (*itr2).y() && (*itr).y() == (*itr3).y()) ) {
470 ++count;
471 found_colinear = true;
472 } else {
473 itr = itr2;
474 ++itr2;
475 }
476 *itr2 = *itr3;
477 }
478 itr3 = poly.begin();
479 if(((*itr).x() == (*itr2).x() && (*itr).x() == (*itr3).x()) ||
480 ((*itr).y() == (*itr2).y() && (*itr).y() == (*itr3).y()) ) {
481 ++count;
482 found_colinear = true;
483 }
484 poly.erase(poly.end() - count, poly.end());
485 }
486 return poly.size() >= 4;
487 }
488
489 polygon_90_set_data&
490 bloat(typename coordinate_traits<coordinate_type>::unsigned_area_type west_bloating,
491 typename coordinate_traits<coordinate_type>::unsigned_area_type east_bloating,
492 typename coordinate_traits<coordinate_type>::unsigned_area_type south_bloating,
493 typename coordinate_traits<coordinate_type>::unsigned_area_type north_bloating) {
494 std::list<polygon_45_with_holes_data<coordinate_type> > polys;
495 get(polys);
496 clear();
497 for(typename std::list<polygon_45_with_holes_data<coordinate_type> >::iterator itr = polys.begin();
498 itr != polys.end(); ++itr) {
499 //polygon_90_set_data<coordinate_type> psref;
500 //psref.insert(view_as<polygon_90_concept>((*itr).self_));
501 //rectangle_data<coordinate_type> prerect;
502 //psref.extents(prerect);
503 resize_poly_up(poly&: (*itr).self_.coords_, west_bloating: (coordinate_type)west_bloating, east_bloating: (coordinate_type)east_bloating,
504 south_bloating: (coordinate_type)south_bloating, north_bloating: (coordinate_type)north_bloating);
505 iterator_geometry_to_set<polygon_90_concept, view_of<polygon_90_concept, polygon_45_data<coordinate_type> > >
506 begin_input(view_as<polygon_90_concept>((*itr).self_), LOW, orient_, false, true, COUNTERCLOCKWISE),
507 end_input(view_as<polygon_90_concept>((*itr).self_), HIGH, orient_, false, true, COUNTERCLOCKWISE);
508 insert(begin_input, end_input, orient_);
509 //polygon_90_set_data<coordinate_type> pstest;
510 //pstest.insert(view_as<polygon_90_concept>((*itr).self_));
511 //psref.bloat2(west_bloating, east_bloating, south_bloating, north_bloating);
512 //if(!equivalence(psref, pstest)) {
513 // std::cout << "test failed\n";
514 //}
515 for(typename std::list<polygon_45_data<coordinate_type> >::iterator itrh = (*itr).holes_.begin();
516 itrh != (*itr).holes_.end(); ++itrh) {
517 //rectangle_data<coordinate_type> rect;
518 //psref.extents(rect);
519 //polygon_90_set_data<coordinate_type> psrefhole;
520 //psrefhole.insert(prerect);
521 //psrefhole.insert(view_as<polygon_90_concept>(*itrh), true);
522 //polygon_45_data<coordinate_type> testpoly(*itrh);
523 if(resize_poly_down(poly&: (*itrh).coords_,west_shrinking: (coordinate_type)west_bloating, east_shrinking: (coordinate_type)east_bloating,
524 south_shrinking: (coordinate_type)south_bloating, north_shrinking: (coordinate_type)north_bloating)) {
525 iterator_geometry_to_set<polygon_90_concept, view_of<polygon_90_concept, polygon_45_data<coordinate_type> > >
526 begin_input2(view_as<polygon_90_concept>(*itrh), LOW, orient_, true, true),
527 end_input2(view_as<polygon_90_concept>(*itrh), HIGH, orient_, true, true);
528 insert(begin_input2, end_input2, orient_);
529 //polygon_90_set_data<coordinate_type> pstesthole;
530 //pstesthole.insert(rect);
531 //iterator_geometry_to_set<polygon_90_concept, view_of<polygon_90_concept, polygon_45_data<coordinate_type> > >
532 // begin_input2(view_as<polygon_90_concept>(*itrh), LOW, orient_, true, true);
533 //pstesthole.insert(begin_input2, end_input, orient_);
534 //psrefhole.bloat2(west_bloating, east_bloating, south_bloating, north_bloating);
535 //if(!equivalence(psrefhole, pstesthole)) {
536 // std::cout << (winding(testpoly) == CLOCKWISE) << std::endl;
537 // std::cout << (winding(*itrh) == CLOCKWISE) << std::endl;
538 // polygon_90_set_data<coordinate_type> c(psrefhole);
539 // c.clean();
540 // polygon_90_set_data<coordinate_type> a(pstesthole);
541 // polygon_90_set_data<coordinate_type> b(pstesthole);
542 // a.sort();
543 // b.clean();
544 // std::cout << "test hole failed\n";
545 // //std::cout << testpoly << std::endl;
546 //}
547 }
548 }
549 }
550 return *this;
551 }
552
553 polygon_90_set_data&
554 shrink(typename coordinate_traits<coordinate_type>::unsigned_area_type west_shrinking,
555 typename coordinate_traits<coordinate_type>::unsigned_area_type east_shrinking,
556 typename coordinate_traits<coordinate_type>::unsigned_area_type south_shrinking,
557 typename coordinate_traits<coordinate_type>::unsigned_area_type north_shrinking) {
558 std::list<polygon_45_with_holes_data<coordinate_type> > polys;
559 get(polys);
560 clear();
561 for(typename std::list<polygon_45_with_holes_data<coordinate_type> >::iterator itr = polys.begin();
562 itr != polys.end(); ++itr) {
563 //polygon_90_set_data<coordinate_type> psref;
564 //psref.insert(view_as<polygon_90_concept>((*itr).self_));
565 //rectangle_data<coordinate_type> prerect;
566 //psref.extents(prerect);
567 //polygon_45_data<coordinate_type> testpoly((*itr).self_);
568 if(resize_poly_down(poly&: (*itr).self_.coords_, west_shrinking: -(coordinate_type)west_shrinking, east_shrinking: -(coordinate_type)east_shrinking,
569 south_shrinking: -(coordinate_type)south_shrinking, north_shrinking: -(coordinate_type)north_shrinking)) {
570 iterator_geometry_to_set<polygon_90_concept, view_of<polygon_90_concept, polygon_45_data<coordinate_type> > >
571 begin_input(view_as<polygon_90_concept>((*itr).self_), LOW, orient_, false, true, COUNTERCLOCKWISE),
572 end_input(view_as<polygon_90_concept>((*itr).self_), HIGH, orient_, false, true, COUNTERCLOCKWISE);
573 insert(begin_input, end_input, orient_);
574 //iterator_geometry_to_set<polygon_90_concept, view_of<polygon_90_concept, polygon_45_data<coordinate_type> > >
575 // begin_input2(view_as<polygon_90_concept>((*itr).self_), LOW, orient_, false, true, COUNTERCLOCKWISE);
576 //polygon_90_set_data<coordinate_type> pstest;
577 //pstest.insert(begin_input2, end_input, orient_);
578 //psref.shrink2(west_shrinking, east_shrinking, south_shrinking, north_shrinking);
579 //if(!equivalence(psref, pstest)) {
580 // std::cout << "test failed\n";
581 //}
582 for(typename std::list<polygon_45_data<coordinate_type> >::iterator itrh = (*itr).holes_.begin();
583 itrh != (*itr).holes_.end(); ++itrh) {
584 //rectangle_data<coordinate_type> rect;
585 //psref.extents(rect);
586 //polygon_90_set_data<coordinate_type> psrefhole;
587 //psrefhole.insert(prerect);
588 //psrefhole.insert(view_as<polygon_90_concept>(*itrh), true);
589 //polygon_45_data<coordinate_type> testpoly(*itrh);
590 resize_poly_up(poly&: (*itrh).coords_, west_bloating: -(coordinate_type)west_shrinking, east_bloating: -(coordinate_type)east_shrinking,
591 south_bloating: -(coordinate_type)south_shrinking, north_bloating: -(coordinate_type)north_shrinking);
592 iterator_geometry_to_set<polygon_90_concept, view_of<polygon_90_concept, polygon_45_data<coordinate_type> > >
593 begin_input2(view_as<polygon_90_concept>(*itrh), LOW, orient_, true, true),
594 end_input2(view_as<polygon_90_concept>(*itrh), HIGH, orient_, true, true);
595 insert(begin_input2, end_input2, orient_);
596 //polygon_90_set_data<coordinate_type> pstesthole;
597 //pstesthole.insert(rect);
598 //iterator_geometry_to_set<polygon_90_concept, view_of<polygon_90_concept, polygon_45_data<coordinate_type> > >
599 // begin_input2(view_as<polygon_90_concept>(*itrh), LOW, orient_, true, true);
600 //pstesthole.insert(begin_input2, end_input, orient_);
601 //psrefhole.shrink2(west_shrinking, east_shrinking, south_shrinking, north_shrinking);
602 //if(!equivalence(psrefhole, pstesthole)) {
603 // std::cout << (winding(testpoly) == CLOCKWISE) << std::endl;
604 // std::cout << (winding(*itrh) == CLOCKWISE) << std::endl;
605 // polygon_90_set_data<coordinate_type> c(psrefhole);
606 // c.clean();
607 // polygon_90_set_data<coordinate_type> a(pstesthole);
608 // polygon_90_set_data<coordinate_type> b(pstesthole);
609 // a.sort();
610 // b.clean();
611 // std::cout << "test hole failed\n";
612 // //std::cout << testpoly << std::endl;
613 //}
614 }
615 }
616 }
617 return *this;
618 }
619
620 polygon_90_set_data&
621 shrink2(typename coordinate_traits<coordinate_type>::unsigned_area_type west_shrinking,
622 typename coordinate_traits<coordinate_type>::unsigned_area_type east_shrinking,
623 typename coordinate_traits<coordinate_type>::unsigned_area_type south_shrinking,
624 typename coordinate_traits<coordinate_type>::unsigned_area_type north_shrinking) {
625 rectangle_data<coordinate_type> externalBoundary;
626 if(!extents(externalBoundary)) return *this;
627 ::boost::polygon::bloat(externalBoundary, 10); //bloat by diferential ammount
628 //insert a hole that encompasses the data
629 insert(externalBoundary, true); //note that the set is in a dirty state now
630 sort(); //does not apply implicit OR operation
631 std::vector<rectangle_data<coordinate_type> > rects;
632 rects.reserve(data_.size() / 2);
633 //begin does not apply implicit or operation, this is a dirty range
634 form_rectangles(rects, data_.begin(), data_.end(), orient_, rectangle_concept());
635 clear();
636 rectangle_data<coordinate_type> convolutionRectangle(interval_data<coordinate_type>(-((coordinate_type)east_shrinking),
637 (coordinate_type)west_shrinking),
638 interval_data<coordinate_type>(-((coordinate_type)north_shrinking),
639 (coordinate_type)south_shrinking));
640 for(typename std::vector<rectangle_data<coordinate_type> >::iterator itr = rects.begin();
641 itr != rects.end(); ++itr) {
642 rectangle_data<coordinate_type>& rect = *itr;
643 convolve(rect, convolutionRectangle);
644 //insert rectangle as a hole
645 insert(rect, true);
646 }
647 convolve(externalBoundary, convolutionRectangle);
648 //insert duplicate of external boundary as solid to cancel out the external hole boundaries
649 insert(externalBoundary);
650 clean(); //we have negative values in the set, so we need to apply an OR operation to make it valid input to a boolean
651 return *this;
652 }
653
654 polygon_90_set_data&
655 shrink(direction_2d dir, typename coordinate_traits<coordinate_type>::unsigned_area_type shrinking) {
656 if(dir == WEST)
657 return shrink(shrinking, 0, 0, 0);
658 if(dir == EAST)
659 return shrink(0, shrinking, 0, 0);
660 if(dir == SOUTH)
661 return shrink(0, 0, shrinking, 0);
662 return shrink(0, 0, 0, shrinking);
663 }
664
665 polygon_90_set_data&
666 bloat(direction_2d dir, typename coordinate_traits<coordinate_type>::unsigned_area_type shrinking) {
667 if(dir == WEST)
668 return bloat(shrinking, 0, 0, 0);
669 if(dir == EAST)
670 return bloat(0, shrinking, 0, 0);
671 if(dir == SOUTH)
672 return bloat(0, 0, shrinking, 0);
673 return bloat(0, 0, 0, shrinking);
674 }
675
676 polygon_90_set_data&
677 resize(coordinate_type west, coordinate_type east, coordinate_type south, coordinate_type north);
678
679 polygon_90_set_data& move(coordinate_type x_delta, coordinate_type y_delta) {
680 for(typename std::vector<std::pair<coordinate_type, std::pair<coordinate_type, int> > >::iterator
681 itr = data_.begin(); itr != data_.end(); ++itr) {
682 if(orient_ == orientation_2d(VERTICAL)) {
683 (*itr).first += x_delta;
684 (*itr).second.first += y_delta;
685 } else {
686 (*itr).second.first += x_delta;
687 (*itr).first += y_delta;
688 }
689 }
690 return *this;
691 }
692
693 // transform set
694 template <typename transformation_type>
695 polygon_90_set_data& transform(const transformation_type& transformation) {
696 direction_2d dir1, dir2;
697 transformation.get_directions(dir1, dir2);
698 int sign = dir1.get_sign() * dir2.get_sign();
699 for(typename std::vector<std::pair<coordinate_type, std::pair<coordinate_type, int> > >::iterator
700 itr = data_.begin(); itr != data_.end(); ++itr) {
701 if(orient_ == orientation_2d(VERTICAL)) {
702 transformation.transform((*itr).first, (*itr).second.first);
703 } else {
704 transformation.transform((*itr).second.first, (*itr).first);
705 }
706 (*itr).second.second *= sign;
707 }
708 if(dir1 != EAST || dir2 != NORTH)
709 unsorted_ = true; //some mirroring or rotation must have happened
710 return *this;
711 }
712
713 // scale set
714 polygon_90_set_data& scale_up(typename coordinate_traits<coordinate_type>::unsigned_area_type factor) {
715 for(typename std::vector<std::pair<coordinate_type, std::pair<coordinate_type, int> > >::iterator
716 itr = data_.begin(); itr != data_.end(); ++itr) {
717 (*itr).first *= (coordinate_type)factor;
718 (*itr).second.first *= (coordinate_type)factor;
719 }
720 return *this;
721 }
722 polygon_90_set_data& scale_down(typename coordinate_traits<coordinate_type>::unsigned_area_type factor) {
723 typedef typename coordinate_traits<coordinate_type>::coordinate_distance dt;
724 for(typename std::vector<std::pair<coordinate_type, std::pair<coordinate_type, int> > >::iterator
725 itr = data_.begin(); itr != data_.end(); ++itr) {
726 (*itr).first = scaling_policy<coordinate_type>::round((dt)((*itr).first) / (dt)factor);
727 (*itr).second.first = scaling_policy<coordinate_type>::round((dt)((*itr).second.first) / (dt)factor);
728 }
729 unsorted_ = true; //scaling down can make coordinates equal that were not previously equal
730 return *this;
731 }
732 template <typename scaling_type>
733 polygon_90_set_data& scale(const anisotropic_scale_factor<scaling_type>& scaling) {
734 for(typename std::vector<std::pair<coordinate_type, std::pair<coordinate_type, int> > >::iterator
735 itr = data_.begin(); itr != data_.end(); ++itr) {
736 if(orient_ == orientation_2d(VERTICAL)) {
737 scaling.scale((*itr).first, (*itr).second.first);
738 } else {
739 scaling.scale((*itr).second.first, (*itr).first);
740 }
741 }
742 unsorted_ = true;
743 return *this;
744 }
745 template <typename scaling_type>
746 polygon_90_set_data& scale_with(const scaling_type& scaling) {
747 for(typename std::vector<std::pair<coordinate_type, std::pair<coordinate_type, int> > >::iterator
748 itr = data_.begin(); itr != data_.end(); ++itr) {
749 if(orient_ == orientation_2d(VERTICAL)) {
750 scaling.scale((*itr).first, (*itr).second.first);
751 } else {
752 scaling.scale((*itr).second.first, (*itr).first);
753 }
754 }
755 unsorted_ = true;
756 return *this;
757 }
758 polygon_90_set_data& scale(double factor) {
759 typedef typename coordinate_traits<coordinate_type>::coordinate_distance dt;
760 for(typename std::vector<std::pair<coordinate_type, std::pair<coordinate_type, int> > >::iterator
761 itr = data_.begin(); itr != data_.end(); ++itr) {
762 (*itr).first = scaling_policy<coordinate_type>::round((dt)((*itr).first) * (dt)factor);
763 (*itr).second.first = scaling_policy<coordinate_type>::round((dt)((*itr).second.first) * (dt)factor);
764 }
765 unsorted_ = true; //scaling make coordinates equal that were not previously equal
766 return *this;
767 }
768
769 polygon_90_set_data& self_xor() {
770 sort();
771 if(dirty_) { //if it is clean it is a no-op
772 boolean_op::default_arg_workaround<boolean_op::UnaryCount>::applyBooleanOr(data_);
773 dirty_ = false;
774 }
775 return *this;
776 }
777
778 polygon_90_set_data& self_intersect() {
779 sort();
780 if(dirty_) { //if it is clean it is a no-op
781 interval_data<coordinate_type> ivl((std::numeric_limits<coordinate_type>::min)(), (std::numeric_limits<coordinate_type>::max)());
782 rectangle_data<coordinate_type> rect(ivl, ivl);
783 insert(rect, true);
784 clean();
785 }
786 return *this;
787 }
788
789 inline polygon_90_set_data& interact(const polygon_90_set_data& that) {
790 typedef coordinate_type Unit;
791 if(that.dirty_) that.clean();
792 typename touch_90_operation<Unit>::TouchSetData tsd;
793 touch_90_operation<Unit>::populateTouchSetData(tsd, that.data_, 0);
794 std::vector<polygon_90_data<Unit> > polys;
795 get(polys);
796 std::vector<std::set<int> > graph(polys.size()+1, std::set<int>());
797 for(std::size_t i = 0; i < polys.size(); ++i){
798 polygon_90_set_data<Unit> psTmp(that.orient_);
799 psTmp.insert(polys[i]);
800 psTmp.clean();
801 touch_90_operation<Unit>::populateTouchSetData(tsd, psTmp.data_, i+1);
802 }
803 touch_90_operation<Unit>::performTouch(graph, tsd);
804 clear();
805 for(std::set<int>::iterator itr = graph[0].begin(); itr != graph[0].end(); ++itr){
806 insert(polys[(*itr)-1]);
807 }
808 dirty_ = false;
809 return *this;
810 }
811
812
813 template <class T2, typename iterator_type_1, typename iterator_type_2>
814 void applyBooleanBinaryOp(iterator_type_1 itr1, iterator_type_1 itr1_end,
815 iterator_type_2 itr2, iterator_type_2 itr2_end,
816 T2 defaultCount) {
817 data_.clear();
818 boolean_op::applyBooleanBinaryOp(data_, itr1, itr1_end, itr2, itr2_end, defaultCount);
819 }
820
821 private:
822 orientation_2d orient_;
823 mutable value_type data_;
824 mutable bool dirty_;
825 mutable bool unsorted_;
826
827 private:
828 //functions
829 template <typename output_container>
830 void get_dispatch(output_container& output, rectangle_concept ) const {
831 clean();
832 form_rectangles(output, data_.begin(), data_.end(), orient_, rectangle_concept());
833 }
834 template <typename output_container>
835 void get_dispatch(output_container& output, polygon_90_concept tag) const {
836 get_fracture(output, true, tag);
837 }
838
839 template <typename output_container>
840 void get_dispatch(output_container& output, polygon_90_concept tag,
841 size_t vthreshold) const {
842 get_fracture(output, true, tag, vthreshold);
843 }
844
845 template <typename output_container>
846 void get_dispatch(output_container& output, polygon_90_with_holes_concept tag) const {
847 get_fracture(output, false, tag);
848 }
849
850 template <typename output_container>
851 void get_dispatch(output_container& output, polygon_90_with_holes_concept tag,
852 size_t vthreshold) const {
853 get_fracture(output, false, tag, vthreshold);
854 }
855
856
857 template <typename output_container>
858 void get_dispatch(output_container& output, polygon_45_concept tag) const {
859 get_fracture(output, true, tag);
860 }
861 template <typename output_container>
862 void get_dispatch(output_container& output, polygon_45_with_holes_concept tag) const {
863 get_fracture(output, false, tag);
864 }
865 template <typename output_container>
866 void get_dispatch(output_container& output, polygon_concept tag) const {
867 get_fracture(output, true, tag);
868 }
869 template <typename output_container>
870 void get_dispatch(output_container& output, polygon_with_holes_concept tag) const {
871 get_fracture(output, false, tag);
872 }
873 template <typename output_container, typename concept_type>
874 void get_fracture(output_container& container, bool fracture_holes, concept_type tag) const {
875 clean();
876 ::boost::polygon::get_polygons(container, data_.begin(), data_.end(), orient_, fracture_holes, tag);
877 }
878
879 template <typename output_container, typename concept_type>
880 void get_fracture(output_container& container, bool fracture_holes, concept_type tag,
881 size_t vthreshold) const {
882 clean();
883 ::boost::polygon::get_polygons(container, data_.begin(), data_.end(), orient_, fracture_holes, tag, vthreshold);
884 }
885 };
886
887 template <typename coordinate_type>
888 polygon_90_set_data<coordinate_type>&
889 polygon_90_set_data<coordinate_type>::resize(coordinate_type west,
890 coordinate_type east,
891 coordinate_type south,
892 coordinate_type north) {
893 move(x_delta: -west, y_delta: -south);
894 coordinate_type e_total = west + east;
895 coordinate_type n_total = south + north;
896 if((e_total < 0) ^ (n_total < 0)) {
897 //different signs
898 if(e_total < 0) {
899 shrink(0, -e_total, 0, 0);
900 if(n_total != 0)
901 return bloat(0, 0, 0, n_total);
902 else
903 return (*this);
904 } else {
905 shrink(0, 0, 0, -n_total); //shrink first
906 if(e_total != 0)
907 return bloat(0, e_total, 0, 0);
908 else
909 return (*this);
910 }
911 } else {
912 if(e_total < 0) {
913 return shrink(0, -e_total, 0, -n_total);
914 }
915 return bloat(0, e_total, 0, n_total);
916 }
917 }
918
919 template <typename coordinate_type, typename property_type>
920 class property_merge_90 {
921 private:
922 std::vector<std::pair<property_merge_point<coordinate_type>, std::pair<property_type, int> > > pmd_;
923 public:
924 inline property_merge_90() : pmd_() {}
925 inline property_merge_90(const property_merge_90& that) : pmd_(that.pmd_) {}
926 inline property_merge_90& operator=(const property_merge_90& that) { pmd_ = that.pmd_; return *this; }
927 inline void insert(const polygon_90_set_data<coordinate_type>& ps, const property_type& property) {
928 merge_scanline<coordinate_type, property_type, polygon_90_set_data<coordinate_type> >::
929 populate_property_merge_data(pmd_, ps.begin(), ps.end(), property, ps.orient());
930 }
931 template <class GeoObjT>
932 inline void insert(const GeoObjT& geoObj, const property_type& property) {
933 polygon_90_set_data<coordinate_type> ps;
934 ps.insert(geoObj);
935 insert(ps, property);
936 }
937 //merge properties of input geometries and store the resulting geometries of regions
938 //with unique sets of merged properties to polygons sets in a map keyed by sets of properties
939 // T = std::map<std::set<property_type>, polygon_90_set_data<coordiante_type> > or
940 // T = std::map<std::vector<property_type>, polygon_90_set_data<coordiante_type> >
941 template <typename ResultType>
942 inline void merge(ResultType& result) {
943 merge_scanline<coordinate_type, property_type, polygon_90_set_data<coordinate_type>, typename ResultType::key_type> ms;
944 ms.perform_merge(result, pmd_);
945 }
946 };
947
948 //ConnectivityExtraction computes the graph of connectivity between rectangle, polygon and
949 //polygon set graph nodes where an edge is created whenever the geometry in two nodes overlap
950 template <typename coordinate_type>
951 class connectivity_extraction_90 {
952 private:
953 typedef typename touch_90_operation<coordinate_type>::TouchSetData tsd;
954 tsd tsd_;
955 unsigned int nodeCount_;
956 public:
957 inline connectivity_extraction_90() : tsd_(), nodeCount_(0) {}
958 inline connectivity_extraction_90(const connectivity_extraction_90& that) : tsd_(that.tsd_),
959 nodeCount_(that.nodeCount_) {}
960 inline connectivity_extraction_90& operator=(const connectivity_extraction_90& that) {
961 tsd_ = that.tsd_;
962 nodeCount_ = that.nodeCount_; {}
963 return *this;
964 }
965
966 //insert a polygon set graph node, the value returned is the id of the graph node
967 inline unsigned int insert(const polygon_90_set_data<coordinate_type>& ps) {
968 ps.clean();
969 touch_90_operation<coordinate_type>::populateTouchSetData(tsd_, ps.begin(), ps.end(), nodeCount_);
970 return nodeCount_++;
971 }
972 template <class GeoObjT>
973 inline unsigned int insert(const GeoObjT& geoObj) {
974 polygon_90_set_data<coordinate_type> ps;
975 ps.insert(geoObj);
976 return insert(ps);
977 }
978
979 //extract connectivity and store the edges in the graph
980 //graph must be indexable by graph node id and the indexed value must be a std::set of
981 //graph node id
982 template <class GraphT>
983 inline void extract(GraphT& graph) {
984 touch_90_operation<coordinate_type>::performTouch(graph, tsd_);
985 }
986 };
987}
988}
989#endif
990

source code of boost/boost/polygon/polygon_90_set_data.hpp