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 29 namespace 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 polygon_90_set_data()42 inline polygon_90_set_data() : orient_(HORIZONTAL), data_(), dirty_(false), unsorted_(false) {} 43 44 // constructor polygon_90_set_data(orientation_2d orient)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> polygon_90_set_data(orientation_2d,iT input_begin,iT input_end)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 polygon_90_set_data(const polygon_90_set_data & that)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 polygon_90_set_data(orientation_2d orient,const polygon_90_set_data & that)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 ~polygon_90_set_data()70 inline ~polygon_90_set_data() {} 71 72 // assignement operator operator =(const polygon_90_set_data & that)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> operator =(const geometry_object & geometry)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 insert(iterator_type input_begin,iterator_type input_end,orientation_2d orient=HORIZONTAL)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> insert(iT input_begin,iT input_end,orientation_2d orient=HORIZONTAL)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 insert(const polygon_90_set_data & polygon_set)117 inline void insert(const polygon_90_set_data& polygon_set) { 118 insert(polygon_set.begin(), polygon_set.end(), polygon_set.orient()); 119 } 120 insert(const std::pair<std::pair<point_data<coordinate_type>,point_data<coordinate_type>>,int> & edge,bool is_hole=false,orientation_2d=HORIZONTAL)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> insert(const geometry_type & geometry_object,bool is_hole=false,orientation_2d=HORIZONTAL)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 insert(const std::pair<coordinate_type,std::pair<coordinate_type,int>> & vertex,bool is_hole=false,orientation_2d orient=HORIZONTAL)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 insert(coordinate_type major_coordinate,const std::pair<interval_data<coordinate_type>,int> & edge)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> get(output_container & output) const162 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> get(output_container & output,size_t vthreshold) const167 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> get_polygons(output_container & output) const173 inline void get_polygons(output_container& output) const { 174 get_dispatch(output, polygon_90_concept()); 175 } 176 177 template <typename output_container> get_rectangles(output_container & output) const178 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> get_rectangles(output_container & output,orientation_2d slicing_orientation) const184 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 operator ==(const polygon_90_set_data & p) const200 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 operator !=(const polygon_90_set_data & p) const211 inline bool operator!=(const polygon_90_set_data& p) const { 212 return !((*this) == p); 213 } 214 215 // get iterator to begin vertex data begin() const216 inline iterator_type begin() const { 217 return data_.begin(); 218 } 219 220 // get iterator to end vertex data end() const221 inline iterator_type end() const { 222 return data_.end(); 223 } 224 value() const225 const value_type& value() const { 226 return data_; 227 } 228 229 // clear the contents of the polygon_90_set_data clear()230 inline void clear() { data_.clear(); dirty_ = unsorted_ = false; } 231 232 // find out if Polygon set is empty empty() const233 inline bool empty() const { clean(); return data_.empty(); } 234 235 // get the Polygon set size in vertices size() const236 inline std::size_t size() const { clean(); return data_.size(); } 237 238 // get the current Polygon set capacity in vertices capacity() const239 inline std::size_t capacity() const { return data_.capacity(); } 240 241 // reserve size of polygon set in vertices reserve(std::size_t size)242 inline void reserve(std::size_t size) { return data_.reserve(size); } 243 244 // find out if Polygon set is sorted sorted() const245 inline bool sorted() const { return !unsorted_; } 246 247 // find out if Polygon set is clean dirty() const248 inline bool dirty() const { return dirty_; } 249 250 // get the scanline orientation of the polygon set orient() const251 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 clean() const295 void clean() const { 296 sort(); 297 if(dirty_) { 298 boolean_op::default_arg_workaround<int>::applyBooleanOr(data_); 299 dirty_ = false; 300 } 301 } 302 sort() const303 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> set(input_iterator_type input_begin,input_iterator_type input_end,orientation_2d orient)311 void set(input_iterator_type input_begin, input_iterator_type input_end, orientation_2d orient) { 312 data_.clear(); 313 reserve(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 set(const value_type & value,orientation_2d orient)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 extents(rectangle_type & extents_rectangle) const330 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& bloat2(typename coordinate_traits<coordinate_type>::unsigned_area_type west_bloating,typename coordinate_traits<coordinate_type>::unsigned_area_type east_bloating,typename coordinate_traits<coordinate_type>::unsigned_area_type south_bloating,typename coordinate_traits<coordinate_type>::unsigned_area_type north_bloating)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 modify_pt(point_data<coordinate_type> & pt,const point_data<coordinate_type> & prev_pt,const point_data<coordinate_type> & current_pt,const point_data<coordinate_type> & next_pt,coordinate_type west_bloating,coordinate_type east_bloating,coordinate_type south_bloating,coordinate_type north_bloating)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 } resize_poly_up(std::vector<point_data<coordinate_type>> & poly,coordinate_type west_bloating,coordinate_type east_bloating,coordinate_type south_bloating,coordinate_type north_bloating)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(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(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(poly[0], prev_pt, current_pt, next_pt, west_bloating, east_bloating, south_bloating, north_bloating); 423 remove_colinear_pts(poly); 424 } resize_poly_down(std::vector<point_data<coordinate_type>> & poly,coordinate_type west_shrinking,coordinate_type east_shrinking,coordinate_type south_shrinking,coordinate_type north_shrinking)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(poly[i-1], prev_pt, current_pt, next_pt, west_shrinking, east_shrinking, south_shrinking, 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(poly.back(), prev_pt, current_pt, next_pt, west_shrinking, east_shrinking, south_shrinking, north_shrinking); 450 prev_pt = current_pt; 451 current_pt = next_pt; 452 next_pt = second_pt; 453 modify_pt(poly[0], prev_pt, current_pt, next_pt, west_shrinking, east_shrinking, south_shrinking, north_shrinking); 454 return remove_colinear_pts(poly); 455 } 456 remove_colinear_pts(std::vector<point_data<coordinate_type>> & poly)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& bloat(typename coordinate_traits<coordinate_type>::unsigned_area_type west_bloating,typename coordinate_traits<coordinate_type>::unsigned_area_type east_bloating,typename coordinate_traits<coordinate_type>::unsigned_area_type south_bloating,typename coordinate_traits<coordinate_type>::unsigned_area_type north_bloating)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((*itr).self_.coords_, (coordinate_type)west_bloating, (coordinate_type)east_bloating, 504 (coordinate_type)south_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((*itrh).coords_,(coordinate_type)west_bloating, (coordinate_type)east_bloating, 524 (coordinate_type)south_bloating, (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& shrink(typename coordinate_traits<coordinate_type>::unsigned_area_type west_shrinking,typename coordinate_traits<coordinate_type>::unsigned_area_type east_shrinking,typename coordinate_traits<coordinate_type>::unsigned_area_type south_shrinking,typename coordinate_traits<coordinate_type>::unsigned_area_type north_shrinking)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((*itr).self_.coords_, -(coordinate_type)west_shrinking, -(coordinate_type)east_shrinking, 569 -(coordinate_type)south_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((*itrh).coords_, -(coordinate_type)west_shrinking, -(coordinate_type)east_shrinking, 591 -(coordinate_type)south_shrinking, -(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& shrink2(typename coordinate_traits<coordinate_type>::unsigned_area_type west_shrinking,typename coordinate_traits<coordinate_type>::unsigned_area_type east_shrinking,typename coordinate_traits<coordinate_type>::unsigned_area_type south_shrinking,typename coordinate_traits<coordinate_type>::unsigned_area_type north_shrinking)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& shrink(direction_2d dir,typename coordinate_traits<coordinate_type>::unsigned_area_type shrinking)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& bloat(direction_2d dir,typename coordinate_traits<coordinate_type>::unsigned_area_type shrinking)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 move(coordinate_type x_delta,coordinate_type y_delta)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> transform(const transformation_type & transformation)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 scale_up(typename coordinate_traits<coordinate_type>::unsigned_area_type factor)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 } scale_down(typename coordinate_traits<coordinate_type>::unsigned_area_type factor)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> scale(const anisotropic_scale_factor<scaling_type> & scaling)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> scale_with(const scaling_type & scaling)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 } scale(double factor)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 self_xor()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 self_intersect()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 interact(const polygon_90_set_data & that)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> applyBooleanBinaryOp(iterator_type_1 itr1,iterator_type_1 itr1_end,iterator_type_2 itr2,iterator_type_2 itr2_end,T2 defaultCount)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> get_dispatch(output_container & output,rectangle_concept) const830 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> get_dispatch(output_container & output,polygon_90_concept tag) const835 void get_dispatch(output_container& output, polygon_90_concept tag) const { 836 get_fracture(output, true, tag); 837 } 838 839 template <typename output_container> get_dispatch(output_container & output,polygon_90_concept tag,size_t vthreshold) const840 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> get_dispatch(output_container & output,polygon_90_with_holes_concept tag) const846 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> get_dispatch(output_container & output,polygon_90_with_holes_concept tag,size_t vthreshold) const851 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> get_dispatch(output_container & output,polygon_45_concept tag) const858 void get_dispatch(output_container& output, polygon_45_concept tag) const { 859 get_fracture(output, true, tag); 860 } 861 template <typename output_container> get_dispatch(output_container & output,polygon_45_with_holes_concept tag) const862 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> get_dispatch(output_container & output,polygon_concept tag) const866 void get_dispatch(output_container& output, polygon_concept tag) const { 867 get_fracture(output, true, tag); 868 } 869 template <typename output_container> get_dispatch(output_container & output,polygon_with_holes_concept tag) const870 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> get_fracture(output_container & container,bool fracture_holes,concept_type tag) const874 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> get_fracture(output_container & container,bool fracture_holes,concept_type tag,size_t vthreshold) const880 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>& resize(coordinate_type west,coordinate_type east,coordinate_type south,coordinate_type north)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(-west, -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: property_merge_90()924 inline property_merge_90() : pmd_() {} property_merge_90(const property_merge_90 & that)925 inline property_merge_90(const property_merge_90& that) : pmd_(that.pmd_) {} operator =(const property_merge_90 & that)926 inline property_merge_90& operator=(const property_merge_90& that) { pmd_ = that.pmd_; return *this; } insert(const polygon_90_set_data<coordinate_type> & ps,const property_type & property)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> insert(const GeoObjT & geoObj,const property_type & property)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> merge(ResultType & result)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: connectivity_extraction_90()957 inline connectivity_extraction_90() : tsd_(), nodeCount_(0) {} connectivity_extraction_90(const connectivity_extraction_90 & that)958 inline connectivity_extraction_90(const connectivity_extraction_90& that) : tsd_(that.tsd_), 959 nodeCount_(that.nodeCount_) {} operator =(const connectivity_extraction_90 & that)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 insert(const polygon_90_set_data<coordinate_type> & ps)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> insert(const GeoObjT & geoObj)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> extract(GraphT & graph)983 inline void extract(GraphT& graph) { 984 touch_90_operation<coordinate_type>::performTouch(graph, tsd_); 985 } 986 }; 987 } 988 } 989 #endif 990