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_45_SET_DATA_HPP 9 #define BOOST_POLYGON_POLYGON_45_SET_DATA_HPP 10 #include "polygon_90_set_data.hpp" 11 #include "detail/boolean_op_45.hpp" 12 #include "detail/polygon_45_formation.hpp" 13 #include "detail/polygon_45_touch.hpp" 14 #include "detail/property_merge_45.hpp" 15 namespace boost { namespace polygon{ 16 17 enum RoundingOption { CLOSEST = 0, OVERSIZE = 1, UNDERSIZE = 2, SQRT2 = 3, SQRT1OVER2 = 4 }; 18 enum CornerOption { INTERSECTION = 0, ORTHOGONAL = 1, UNFILLED = 2 }; 19 20 template <typename ltype, typename rtype, int op_type> 21 class polygon_45_set_view; 22 23 struct polygon_45_set_concept {}; 24 25 template <typename Unit> 26 class polygon_45_set_data { 27 public: 28 typedef typename polygon_45_formation<Unit>::Vertex45Compact Vertex45Compact; 29 typedef std::vector<Vertex45Compact> Polygon45VertexData; 30 31 typedef Unit coordinate_type; 32 typedef Polygon45VertexData value_type; 33 typedef typename value_type::const_iterator iterator_type; 34 typedef polygon_45_set_data operator_arg_type; 35 36 // default constructor polygon_45_set_data()37 inline polygon_45_set_data() : error_data_(), data_(), dirty_(false), unsorted_(false), is_manhattan_(true) {} 38 39 // constructor from a geometry object 40 template <typename geometry_type> polygon_45_set_data(const geometry_type & that)41 inline polygon_45_set_data(const geometry_type& that) : error_data_(), data_(), dirty_(false), unsorted_(false), is_manhattan_(true) { 42 insert(that); 43 } 44 45 // copy constructor polygon_45_set_data(const polygon_45_set_data & that)46 inline polygon_45_set_data(const polygon_45_set_data& that) : 47 error_data_(that.error_data_), data_(that.data_), dirty_(that.dirty_), 48 unsorted_(that.unsorted_), is_manhattan_(that.is_manhattan_) {} 49 50 template <typename ltype, typename rtype, int op_type> polygon_45_set_data(const polygon_45_set_view<ltype,rtype,op_type> & that)51 inline polygon_45_set_data(const polygon_45_set_view<ltype, rtype, op_type>& that) : 52 error_data_(), data_(), dirty_(false), unsorted_(false), is_manhattan_(true) { 53 (*this) = that.value(); 54 } 55 56 // destructor ~polygon_45_set_data()57 inline ~polygon_45_set_data() {} 58 59 // assignement operator operator =(const polygon_45_set_data & that)60 inline polygon_45_set_data& operator=(const polygon_45_set_data& that) { 61 if(this == &that) return *this; 62 error_data_ = that.error_data_; 63 data_ = that.data_; 64 dirty_ = that.dirty_; 65 unsorted_ = that.unsorted_; 66 is_manhattan_ = that.is_manhattan_; 67 return *this; 68 } 69 70 template <typename ltype, typename rtype, int op_type> operator =(const polygon_45_set_view<ltype,rtype,op_type> & that)71 inline polygon_45_set_data& operator=(const polygon_45_set_view<ltype, rtype, op_type>& that) { 72 (*this) = that.value(); 73 return *this; 74 } 75 76 template <typename geometry_object> operator =(const geometry_object & geometry)77 inline polygon_45_set_data& operator=(const geometry_object& geometry) { 78 data_.clear(); 79 insert(geometry); 80 return *this; 81 } 82 83 // insert iterator range insert(iterator_type input_begin,iterator_type input_end,bool is_hole=false)84 inline void insert(iterator_type input_begin, iterator_type input_end, bool is_hole = false) { 85 if(input_begin == input_end || (!data_.empty() && &(*input_begin) == &(*(data_.begin())))) return; 86 dirty_ = true; 87 unsorted_ = true; 88 while(input_begin != input_end) { 89 insert(*input_begin, is_hole); 90 ++input_begin; 91 } 92 } 93 94 // insert iterator range 95 template <typename iT> insert(iT input_begin,iT input_end,bool is_hole=false)96 inline void insert(iT input_begin, iT input_end, bool is_hole = false) { 97 if(input_begin == input_end) return; 98 dirty_ = true; 99 unsorted_ = true; 100 while(input_begin != input_end) { 101 insert(*input_begin, is_hole); 102 ++input_begin; 103 } 104 } 105 106 inline void insert(const polygon_45_set_data& polygon_set, bool is_hole = false); 107 template <typename coord_type> 108 inline void insert(const polygon_45_set_data<coord_type>& polygon_set, bool is_hole = false); 109 110 template <typename geometry_type> insert(const geometry_type & geometry_object,bool is_hole=false)111 inline void insert(const geometry_type& geometry_object, bool is_hole = false) { 112 insert_dispatch(geometry_object, is_hole, typename geometry_concept<geometry_type>::type()); 113 } 114 insert_clean(const Vertex45Compact & vertex_45,bool is_hole=false)115 inline void insert_clean(const Vertex45Compact& vertex_45, bool is_hole = false) { 116 if(vertex_45.count.is_45()) is_manhattan_ = false; 117 data_.push_back(vertex_45); 118 if(is_hole) data_.back().count.invert(); 119 } 120 insert(const Vertex45Compact & vertex_45,bool is_hole=false)121 inline void insert(const Vertex45Compact& vertex_45, bool is_hole = false) { 122 dirty_ = true; 123 unsorted_ = true; 124 insert_clean(vertex_45, is_hole); 125 } 126 127 template <typename coordinate_type_2> insert(const polygon_90_set_data<coordinate_type_2> & polygon_set,bool is_hole=false)128 inline void insert(const polygon_90_set_data<coordinate_type_2>& polygon_set, bool is_hole = false) { 129 if(polygon_set.orient() == VERTICAL) { 130 for(typename polygon_90_set_data<coordinate_type_2>::iterator_type itr = polygon_set.begin(); 131 itr != polygon_set.end(); ++itr) { 132 Vertex45Compact vertex_45(point_data<Unit>((*itr).first, (*itr).second.first), 2, (*itr).second.second); 133 vertex_45.count[1] = (*itr).second.second; 134 if(is_hole) vertex_45.count[1] *= - 1; 135 insert_clean(vertex_45, is_hole); 136 } 137 } else { 138 for(typename polygon_90_set_data<coordinate_type_2>::iterator_type itr = polygon_set.begin(); 139 itr != polygon_set.end(); ++itr) { 140 Vertex45Compact vertex_45(point_data<Unit>((*itr).second.first, (*itr).first), 2, (*itr).second.second); 141 vertex_45.count[1] = (*itr).second.second; 142 if(is_hole) vertex_45.count[1] *= - 1; 143 insert_clean(vertex_45, is_hole); 144 } 145 } 146 dirty_ = true; 147 unsorted_ = true; 148 } 149 150 template <typename output_container> get(output_container & output) const151 inline void get(output_container& output) const { 152 get_dispatch(output, typename geometry_concept<typename output_container::value_type>::type()); 153 } 154 has_error_data() const155 inline bool has_error_data() const { return !error_data_.empty(); } error_count() const156 inline std::size_t error_count() const { return error_data_.size() / 4; } get_error_data(polygon_45_set_data & p) const157 inline void get_error_data(polygon_45_set_data& p) const { 158 p.data_.insert(p.data_.end(), error_data_.begin(), error_data_.end()); 159 } 160 161 // equivalence operator operator ==(const polygon_45_set_data & p) const162 inline bool operator==(const polygon_45_set_data& p) const { 163 clean(); 164 p.clean(); 165 return data_ == p.data_; 166 } 167 168 // inequivalence operator operator !=(const polygon_45_set_data & p) const169 inline bool operator!=(const polygon_45_set_data& p) const { 170 return !((*this) == p); 171 } 172 173 // get iterator to begin vertex data begin() const174 inline iterator_type begin() const { 175 return data_.begin(); 176 } 177 178 // get iterator to end vertex data end() const179 inline iterator_type end() const { 180 return data_.end(); 181 } 182 value() const183 const value_type& value() const { 184 return data_; 185 } 186 187 // clear the contents of the polygon_45_set_data clear()188 inline void clear() { data_.clear(); error_data_.clear(); dirty_ = unsorted_ = false; is_manhattan_ = true; } 189 190 // find out if Polygon set is empty empty() const191 inline bool empty() const { return data_.empty(); } 192 193 // get the Polygon set size in vertices size() const194 inline std::size_t size() const { clean(); return data_.size(); } 195 196 // get the current Polygon set capacity in vertices capacity() const197 inline std::size_t capacity() const { return data_.capacity(); } 198 199 // reserve size of polygon set in vertices reserve(std::size_t size)200 inline void reserve(std::size_t size) { return data_.reserve(size); } 201 202 // find out if Polygon set is sorted sorted() const203 inline bool sorted() const { return !unsorted_; } 204 205 // find out if Polygon set is clean dirty() const206 inline bool dirty() const { return dirty_; } 207 208 // find out if Polygon set is clean is_manhattan() const209 inline bool is_manhattan() const { return is_manhattan_; } 210 211 bool clean() const; 212 sort() const213 void sort() const{ 214 if(unsorted_) { 215 polygon_sort(data_.begin(), data_.end()); 216 unsorted_ = false; 217 } 218 } 219 220 template <typename input_iterator_type> set(input_iterator_type input_begin,input_iterator_type input_end)221 void set(input_iterator_type input_begin, input_iterator_type input_end) { 222 data_.clear(); 223 reserve(std::distance(input_begin, input_end)); 224 insert(input_begin, input_end); 225 dirty_ = true; 226 unsorted_ = true; 227 } 228 set_clean(const value_type & value)229 void set_clean(const value_type& value) { 230 data_ = value; 231 dirty_ = false; 232 unsorted_ = false; 233 } 234 set(const value_type & value)235 void set(const value_type& value) { 236 data_ = value; 237 dirty_ = true; 238 unsorted_ = true; 239 } 240 241 // append to the container cT with polygons (holes will be fractured vertically) 242 template <class cT> get_polygons(cT & container) const243 void get_polygons(cT& container) const { 244 get_dispatch(container, polygon_45_concept()); 245 } 246 247 // append to the container cT with PolygonWithHoles objects 248 template <class cT> get_polygons_with_holes(cT & container) const249 void get_polygons_with_holes(cT& container) const { 250 get_dispatch(container, polygon_45_with_holes_concept()); 251 } 252 253 // append to the container cT with polygons of three or four verticies 254 // slicing orientation is vertical 255 template <class cT> get_trapezoids(cT & container) const256 void get_trapezoids(cT& container) const { 257 clean(); 258 typename polygon_45_formation<Unit>::Polygon45Tiling pf; 259 //std::cout << "FORMING POLYGONS\n"; 260 pf.scan(container, data_.begin(), data_.end()); 261 //std::cout << "DONE FORMING POLYGONS\n"; 262 } 263 264 // append to the container cT with polygons of three or four verticies 265 template <class cT> get_trapezoids(cT & container,orientation_2d slicing_orientation) const266 void get_trapezoids(cT& container, orientation_2d slicing_orientation) const { 267 if(slicing_orientation == VERTICAL) { 268 get_trapezoids(container); 269 } else { 270 polygon_45_set_data<Unit> ps(*this); 271 ps.transform(axis_transformation(axis_transformation::SWAP_XY)); 272 cT result; 273 ps.get_trapezoids(result); 274 for(typename cT::iterator itr = result.begin(); itr != result.end(); ++itr) { 275 ::boost::polygon::transform(*itr, axis_transformation(axis_transformation::SWAP_XY)); 276 } 277 container.insert(container.end(), result.begin(), result.end()); 278 } 279 } 280 281 // insert vertex sequence 282 template <class iT> 283 void insert_vertex_sequence(iT begin_vertex, iT end_vertex, 284 direction_1d winding, bool is_hole = false); 285 286 // get the external boundary rectangle 287 template <typename rectangle_type> 288 bool extents(rectangle_type& rect) const; 289 290 // snap verticies of set to even,even or odd,odd coordinates 291 void snap() const; 292 293 // |= &= += *= -= ^= binary operators 294 polygon_45_set_data& operator|=(const polygon_45_set_data& b); 295 polygon_45_set_data& operator&=(const polygon_45_set_data& b); 296 polygon_45_set_data& operator+=(const polygon_45_set_data& b); 297 polygon_45_set_data& operator*=(const polygon_45_set_data& b); 298 polygon_45_set_data& operator-=(const polygon_45_set_data& b); 299 polygon_45_set_data& operator^=(const polygon_45_set_data& b); 300 301 // resizing operations 302 polygon_45_set_data& operator+=(Unit delta); 303 polygon_45_set_data& operator-=(Unit delta); 304 305 // shrink the Polygon45Set by shrinking 306 polygon_45_set_data& resize(coordinate_type resizing, RoundingOption rounding = CLOSEST, 307 CornerOption corner = INTERSECTION); 308 309 // transform set 310 template <typename transformation_type> 311 polygon_45_set_data& transform(const transformation_type& tr); 312 313 // scale set 314 polygon_45_set_data& scale_up(typename coordinate_traits<Unit>::unsigned_area_type factor); 315 polygon_45_set_data& scale_down(typename coordinate_traits<Unit>::unsigned_area_type factor); 316 polygon_45_set_data& scale(double scaling); 317 318 // self_intersect self_intersect()319 polygon_45_set_data& self_intersect() { 320 sort(); 321 applyAdaptiveUnary_<1>(); //1 = AND 322 dirty_ = false; 323 return *this; 324 } 325 326 // self_xor self_xor()327 polygon_45_set_data& self_xor() { 328 sort(); 329 applyAdaptiveUnary_<3>(); //3 = XOR 330 dirty_ = false; 331 return *this; 332 } 333 334 // accumulate the bloated polygon 335 template <typename geometry_type> insert_with_resize(const geometry_type & poly,coordinate_type resizing,RoundingOption rounding=CLOSEST,CornerOption corner=INTERSECTION,bool hole=false)336 polygon_45_set_data& insert_with_resize(const geometry_type& poly, 337 coordinate_type resizing, RoundingOption rounding = CLOSEST, 338 CornerOption corner = INTERSECTION, 339 bool hole = false) { 340 return insert_with_resize_dispatch(poly, resizing, rounding, corner, hole, typename geometry_concept<geometry_type>::type()); 341 } 342 343 private: 344 mutable value_type error_data_; 345 mutable value_type data_; 346 mutable bool dirty_; 347 mutable bool unsorted_; 348 mutable bool is_manhattan_; 349 350 private: 351 //functions 352 template <typename output_container> get_dispatch(output_container & output,polygon_45_concept tag) const353 void get_dispatch(output_container& output, polygon_45_concept tag) const { 354 get_fracture(output, true, tag); 355 } 356 template <typename output_container> get_dispatch(output_container & output,polygon_45_with_holes_concept tag) const357 void get_dispatch(output_container& output, polygon_45_with_holes_concept tag) const { 358 get_fracture(output, false, tag); 359 } 360 template <typename output_container> get_dispatch(output_container & output,polygon_concept tag) const361 void get_dispatch(output_container& output, polygon_concept tag) const { 362 get_fracture(output, true, tag); 363 } 364 template <typename output_container> get_dispatch(output_container & output,polygon_with_holes_concept tag) const365 void get_dispatch(output_container& output, polygon_with_holes_concept tag) const { 366 get_fracture(output, false, tag); 367 } 368 template <typename output_container, typename concept_type> get_fracture(output_container & container,bool fracture_holes,concept_type) const369 void get_fracture(output_container& container, bool fracture_holes, concept_type ) const { 370 clean(); 371 typename polygon_45_formation<Unit>::Polygon45Formation pf(fracture_holes); 372 //std::cout << "FORMING POLYGONS\n"; 373 pf.scan(container, data_.begin(), data_.end()); 374 } 375 376 template <typename geometry_type> insert_dispatch(const geometry_type & geometry_object,bool is_hole,undefined_concept)377 void insert_dispatch(const geometry_type& geometry_object, bool is_hole, undefined_concept) { 378 insert(geometry_object.begin(), geometry_object.end(), is_hole); 379 } 380 template <typename geometry_type> 381 void insert_dispatch(const geometry_type& geometry_object, bool is_hole, rectangle_concept tag); 382 template <typename geometry_type> insert_dispatch(const geometry_type & geometry_object,bool is_hole,polygon_90_concept)383 void insert_dispatch(const geometry_type& geometry_object, bool is_hole, polygon_90_concept ) { 384 insert_vertex_sequence(begin_points(geometry_object), end_points(geometry_object), winding(geometry_object), is_hole); 385 } 386 template <typename geometry_type> insert_dispatch(const geometry_type & geometry_object,bool is_hole,polygon_90_with_holes_concept)387 void insert_dispatch(const geometry_type& geometry_object, bool is_hole, polygon_90_with_holes_concept ) { 388 insert_vertex_sequence(begin_points(geometry_object), end_points(geometry_object), winding(geometry_object), is_hole); 389 for(typename polygon_with_holes_traits<geometry_type>::iterator_holes_type itr = 390 begin_holes(geometry_object); itr != end_holes(geometry_object); 391 ++itr) { 392 insert_vertex_sequence(begin_points(*itr), end_points(*itr), winding(*itr), !is_hole); 393 } 394 } 395 template <typename geometry_type> insert_dispatch(const geometry_type & geometry_object,bool is_hole,polygon_45_concept)396 void insert_dispatch(const geometry_type& geometry_object, bool is_hole, polygon_45_concept ) { 397 insert_vertex_sequence(begin_points(geometry_object), end_points(geometry_object), winding(geometry_object), is_hole); 398 } 399 template <typename geometry_type> insert_dispatch(const geometry_type & geometry_object,bool is_hole,polygon_45_with_holes_concept)400 void insert_dispatch(const geometry_type& geometry_object, bool is_hole, polygon_45_with_holes_concept ) { 401 insert_vertex_sequence(begin_points(geometry_object), end_points(geometry_object), winding(geometry_object), is_hole); 402 for(typename polygon_with_holes_traits<geometry_type>::iterator_holes_type itr = 403 begin_holes(geometry_object); itr != end_holes(geometry_object); 404 ++itr) { 405 insert_vertex_sequence(begin_points(*itr), end_points(*itr), winding(*itr), !is_hole); 406 } 407 } 408 template <typename geometry_type> insert_dispatch(const geometry_type & geometry_object,bool is_hole,polygon_45_set_concept)409 void insert_dispatch(const geometry_type& geometry_object, bool is_hole, polygon_45_set_concept ) { 410 polygon_45_set_data ps; 411 assign(ps, geometry_object); 412 insert(ps, is_hole); 413 } 414 template <typename geometry_type> insert_dispatch(const geometry_type & geometry_object,bool is_hole,polygon_90_set_concept)415 void insert_dispatch(const geometry_type& geometry_object, bool is_hole, polygon_90_set_concept ) { 416 std::list<polygon_90_data<coordinate_type> > pl; 417 assign(pl, geometry_object); 418 insert(pl.begin(), pl.end(), is_hole); 419 } 420 421 void insert_vertex_half_edge_45_pair(const point_data<Unit>& pt1, point_data<Unit>& pt2, 422 const point_data<Unit>& pt3, direction_1d wdir); 423 424 template <typename geometry_type> 425 polygon_45_set_data& insert_with_resize_dispatch(const geometry_type& poly, 426 coordinate_type resizing, RoundingOption rounding, 427 CornerOption corner, bool hole, polygon_45_concept tag); 428 429 // accumulate the bloated polygon with holes 430 template <typename geometry_type> 431 polygon_45_set_data& insert_with_resize_dispatch(const geometry_type& poly, 432 coordinate_type resizing, RoundingOption rounding, 433 CornerOption corner, bool hole, polygon_45_with_holes_concept tag); 434 435 static void snap_vertex_45(Vertex45Compact& vertex); 436 437 public: 438 template <int op> 439 void applyAdaptiveBoolean_(const polygon_45_set_data& rvalue) const; 440 template <int op> 441 void applyAdaptiveBoolean_(polygon_45_set_data& result, const polygon_45_set_data& rvalue) const; 442 template <int op> 443 void applyAdaptiveUnary_() const; 444 }; 445 446 template <typename T> 447 struct geometry_concept<polygon_45_set_data<T> > { 448 typedef polygon_45_set_concept type; 449 }; 450 451 template <typename iT, typename T> scale_up_vertex_45_compact_range(iT beginr,iT endr,T factor)452 void scale_up_vertex_45_compact_range(iT beginr, iT endr, T factor) { 453 for( ; beginr != endr; ++beginr) { 454 scale_up((*beginr).pt, factor); 455 } 456 } 457 template <typename iT, typename T> scale_down_vertex_45_compact_range_blindly(iT beginr,iT endr,T factor)458 void scale_down_vertex_45_compact_range_blindly(iT beginr, iT endr, T factor) { 459 for( ; beginr != endr; ++beginr) { 460 scale_down((*beginr).pt, factor); 461 } 462 } 463 464 template <typename Unit> characterizeEdge45(const point_data<Unit> & pt1,const point_data<Unit> & pt2)465 inline std::pair<int, int> characterizeEdge45(const point_data<Unit>& pt1, const point_data<Unit>& pt2) { 466 std::pair<int, int> retval(0, 1); 467 if(pt1.x() == pt2.x()) { 468 retval.first = 3; 469 retval.second = -1; 470 return retval; 471 } 472 //retval.second = pt1.x() < pt2.x() ? -1 : 1; 473 retval.second = 1; 474 if(pt1.y() == pt2.y()) { 475 retval.first = 1; 476 } else if(pt1.x() < pt2.x()) { 477 if(pt1.y() < pt2.y()) { 478 retval.first = 2; 479 } else { 480 retval.first = 0; 481 } 482 } else { 483 if(pt1.y() < pt2.y()) { 484 retval.first = 0; 485 } else { 486 retval.first = 2; 487 } 488 } 489 return retval; 490 } 491 492 template <typename cT, typename pT> insert_vertex_half_edge_45_pair_into_vector(cT & output,const pT & pt1,pT & pt2,const pT & pt3,direction_1d wdir)493 bool insert_vertex_half_edge_45_pair_into_vector(cT& output, 494 const pT& pt1, pT& pt2, 495 const pT& pt3, 496 direction_1d wdir) { 497 int multiplier = wdir == LOW ? -1 : 1; 498 typename cT::value_type vertex(pt2, 0, 0); 499 //std::cout << pt1 << " " << pt2 << " " << pt3 << std::endl; 500 std::pair<int, int> check; 501 check = characterizeEdge45(pt1, pt2); 502 //std::cout << "index " << check.first << " " << check.second * -multiplier << std::endl; 503 vertex.count[check.first] += check.second * -multiplier; 504 check = characterizeEdge45(pt2, pt3); 505 //std::cout << "index " << check.first << " " << check.second * multiplier << std::endl; 506 vertex.count[check.first] += check.second * multiplier; 507 output.push_back(vertex); 508 return vertex.count.is_45(); 509 } 510 511 template <typename Unit> insert_vertex_half_edge_45_pair(const point_data<Unit> & pt1,point_data<Unit> & pt2,const point_data<Unit> & pt3,direction_1d wdir)512 inline void polygon_45_set_data<Unit>::insert_vertex_half_edge_45_pair(const point_data<Unit>& pt1, point_data<Unit>& pt2, 513 const point_data<Unit>& pt3, 514 direction_1d wdir) { 515 if(insert_vertex_half_edge_45_pair_into_vector(data_, pt1, pt2, pt3, wdir)) is_manhattan_ = false; 516 } 517 518 template <typename Unit> 519 template <class iT> insert_vertex_sequence(iT begin_vertex,iT end_vertex,direction_1d winding,bool is_hole)520 inline void polygon_45_set_data<Unit>::insert_vertex_sequence(iT begin_vertex, iT end_vertex, 521 direction_1d winding, bool is_hole) { 522 if(begin_vertex == end_vertex) return; 523 if(is_hole) winding = winding.backward(); 524 iT itr = begin_vertex; 525 if(itr == end_vertex) return; 526 point_data<Unit> firstPt = *itr; 527 ++itr; 528 point_data<Unit> secondPt(firstPt); 529 //skip any duplicate points 530 do { 531 if(itr == end_vertex) return; 532 secondPt = *itr; 533 ++itr; 534 } while(secondPt == firstPt); 535 point_data<Unit> prevPt = secondPt; 536 point_data<Unit> prevPrevPt = firstPt; 537 while(itr != end_vertex) { 538 point_data<Unit> pt = *itr; 539 //skip any duplicate points 540 if(pt == prevPt) { 541 ++itr; 542 continue; 543 } 544 //operate on the three points 545 insert_vertex_half_edge_45_pair(prevPrevPt, prevPt, pt, winding); 546 prevPrevPt = prevPt; 547 prevPt = pt; 548 ++itr; 549 } 550 if(prevPt != firstPt) { 551 insert_vertex_half_edge_45_pair(prevPrevPt, prevPt, firstPt, winding); 552 insert_vertex_half_edge_45_pair(prevPt, firstPt, secondPt, winding); 553 } else { 554 insert_vertex_half_edge_45_pair(prevPrevPt, firstPt, secondPt, winding); 555 } 556 dirty_ = true; 557 unsorted_ = true; 558 } 559 560 // insert polygon set 561 template <typename Unit> insert(const polygon_45_set_data<Unit> & polygon_set,bool is_hole)562 inline void polygon_45_set_data<Unit>::insert(const polygon_45_set_data<Unit>& polygon_set, bool is_hole) { 563 std::size_t count = data_.size(); 564 data_.insert(data_.end(), polygon_set.data_.begin(), polygon_set.data_.end()); 565 error_data_.insert(error_data_.end(), polygon_set.error_data_.begin(), 566 polygon_set.error_data_.end()); 567 if(is_hole) { 568 for(std::size_t i = count; i < data_.size(); ++i) { 569 data_[i].count = data_[i].count.invert(); 570 } 571 } 572 dirty_ = true; 573 unsorted_ = true; 574 if(polygon_set.is_manhattan_ == false) is_manhattan_ = false; 575 return; 576 } 577 // insert polygon set 578 template <typename Unit> 579 template <typename coord_type> insert(const polygon_45_set_data<coord_type> & polygon_set,bool is_hole)580 inline void polygon_45_set_data<Unit>::insert(const polygon_45_set_data<coord_type>& polygon_set, bool is_hole) { 581 std::size_t count = data_.size(); 582 for(typename polygon_45_set_data<coord_type>::iterator_type itr = polygon_set.begin(); 583 itr != polygon_set.end(); ++itr) { 584 const typename polygon_45_set_data<coord_type>::Vertex45Compact& v = *itr; 585 typename polygon_45_set_data<Unit>::Vertex45Compact v2; 586 v2.pt.x(static_cast<Unit>(v.pt.x())); 587 v2.pt.y(static_cast<Unit>(v.pt.y())); 588 v2.count = typename polygon_45_formation<Unit>::Vertex45Count(v.count[0], v.count[1], v.count[2], v.count[3]); 589 data_.push_back(v2); 590 } 591 polygon_45_set_data<coord_type> tmp; 592 polygon_set.get_error_data(tmp); 593 for(typename polygon_45_set_data<coord_type>::iterator_type itr = tmp.begin(); 594 itr != tmp.end(); ++itr) { 595 const typename polygon_45_set_data<coord_type>::Vertex45Compact& v = *itr; 596 typename polygon_45_set_data<Unit>::Vertex45Compact v2; 597 v2.pt.x(static_cast<Unit>(v.pt.x())); 598 v2.pt.y(static_cast<Unit>(v.pt.y())); 599 v2.count = typename polygon_45_formation<Unit>::Vertex45Count(v.count[0], v.count[1], v.count[2], v.count[3]); 600 error_data_.push_back(v2); 601 } 602 if(is_hole) { 603 for(std::size_t i = count; i < data_.size(); ++i) { 604 data_[i].count = data_[i].count.invert(); 605 } 606 } 607 dirty_ = true; 608 unsorted_ = true; 609 if(polygon_set.is_manhattan() == false) is_manhattan_ = false; 610 return; 611 } 612 613 template <typename cT, typename rT> insert_rectangle_into_vector_45(cT & output,const rT & rect,bool is_hole)614 void insert_rectangle_into_vector_45(cT& output, const rT& rect, bool is_hole) { 615 point_data<typename rectangle_traits<rT>::coordinate_type> 616 llpt = ll(rect), lrpt = lr(rect), ulpt = ul(rect), urpt = ur(rect); 617 direction_1d dir = COUNTERCLOCKWISE; 618 if(is_hole) dir = CLOCKWISE; 619 insert_vertex_half_edge_45_pair_into_vector(output, llpt, lrpt, urpt, dir); 620 insert_vertex_half_edge_45_pair_into_vector(output, lrpt, urpt, ulpt, dir); 621 insert_vertex_half_edge_45_pair_into_vector(output, urpt, ulpt, llpt, dir); 622 insert_vertex_half_edge_45_pair_into_vector(output, ulpt, llpt, lrpt, dir); 623 } 624 625 template <typename Unit> 626 template <typename geometry_type> insert_dispatch(const geometry_type & geometry_object,bool is_hole,rectangle_concept)627 inline void polygon_45_set_data<Unit>::insert_dispatch(const geometry_type& geometry_object, 628 bool is_hole, rectangle_concept ) { 629 dirty_ = true; 630 unsorted_ = true; 631 insert_rectangle_into_vector_45(data_, geometry_object, is_hole); 632 } 633 634 // get the external boundary rectangle 635 template <typename Unit> 636 template <typename rectangle_type> extents(rectangle_type & rect) const637 inline bool polygon_45_set_data<Unit>::extents(rectangle_type& rect) const{ 638 clean(); 639 if(empty()) { 640 return false; 641 } 642 Unit low = (std::numeric_limits<Unit>::max)(); 643 Unit high = (std::numeric_limits<Unit>::min)(); 644 interval_data<Unit> xivl(low, high); 645 interval_data<Unit> yivl(low, high); 646 for(typename value_type::const_iterator itr = data_.begin(); 647 itr != data_.end(); ++ itr) { 648 if((*itr).pt.x() > xivl.get(HIGH)) 649 xivl.set(HIGH, (*itr).pt.x()); 650 if((*itr).pt.x() < xivl.get(LOW)) 651 xivl.set(LOW, (*itr).pt.x()); 652 if((*itr).pt.y() > yivl.get(HIGH)) 653 yivl.set(HIGH, (*itr).pt.y()); 654 if((*itr).pt.y() < yivl.get(LOW)) 655 yivl.set(LOW, (*itr).pt.y()); 656 } 657 rect = construct<rectangle_type>(xivl, yivl); 658 return true; 659 } 660 661 //this function snaps the vertex and two half edges 662 //to be both even or both odd coordinate values if one of the edges is 45 663 //and throws an excpetion if an edge is non-manhattan, non-45. 664 template <typename Unit> snap_vertex_45(typename polygon_45_set_data<Unit>::Vertex45Compact & vertex)665 inline void polygon_45_set_data<Unit>::snap_vertex_45(typename polygon_45_set_data<Unit>::Vertex45Compact& vertex) { 666 bool plus45 = vertex.count[2] != 0; 667 bool minus45 = vertex.count[0] != 0; 668 if(plus45 || minus45) { 669 if(local_abs(vertex.pt.x()) % 2 != local_abs(vertex.pt.y()) % 2) { 670 if(vertex.count[1] != 0 || 671 (plus45 && minus45)) { 672 //move right 673 vertex.pt.x(vertex.pt.x() + 1); 674 } else { 675 //assert that vertex.count[3] != 0 676 Unit modifier = plus45 ? -1 : 1; 677 vertex.pt.y(vertex.pt.y() + modifier); 678 } 679 } 680 } 681 } 682 683 template <typename Unit> snap() const684 inline void polygon_45_set_data<Unit>::snap() const { 685 for(typename value_type::iterator itr = data_.begin(); 686 itr != data_.end(); ++itr) { 687 snap_vertex_45(*itr); 688 } 689 } 690 691 // |= &= += *= -= ^= binary operators 692 template <typename Unit> operator |=(const polygon_45_set_data<Unit> & b)693 inline polygon_45_set_data<Unit>& polygon_45_set_data<Unit>::operator|=(const polygon_45_set_data<Unit>& b) { 694 insert(b); 695 return *this; 696 } 697 template <typename Unit> operator &=(const polygon_45_set_data<Unit> & b)698 inline polygon_45_set_data<Unit>& polygon_45_set_data<Unit>::operator&=(const polygon_45_set_data<Unit>& b) { 699 //b.sort(); 700 //sort(); 701 applyAdaptiveBoolean_<1>(b); 702 dirty_ = false; 703 unsorted_ = false; 704 return *this; 705 } 706 template <typename Unit> operator +=(const polygon_45_set_data<Unit> & b)707 inline polygon_45_set_data<Unit>& polygon_45_set_data<Unit>::operator+=(const polygon_45_set_data<Unit>& b) { 708 return (*this) |= b; 709 } 710 template <typename Unit> operator *=(const polygon_45_set_data<Unit> & b)711 inline polygon_45_set_data<Unit>& polygon_45_set_data<Unit>::operator*=(const polygon_45_set_data<Unit>& b) { 712 return (*this) &= b; 713 } 714 template <typename Unit> operator -=(const polygon_45_set_data<Unit> & b)715 inline polygon_45_set_data<Unit>& polygon_45_set_data<Unit>::operator-=(const polygon_45_set_data<Unit>& b) { 716 //b.sort(); 717 //sort(); 718 applyAdaptiveBoolean_<2>(b); 719 dirty_ = false; 720 unsorted_ = false; 721 return *this; 722 } 723 template <typename Unit> operator ^=(const polygon_45_set_data<Unit> & b)724 inline polygon_45_set_data<Unit>& polygon_45_set_data<Unit>::operator^=(const polygon_45_set_data<Unit>& b) { 725 //b.sort(); 726 //sort(); 727 applyAdaptiveBoolean_<3>(b); 728 dirty_ = false; 729 unsorted_ = false; 730 return *this; 731 } 732 733 template <typename Unit> operator +=(Unit delta)734 inline polygon_45_set_data<Unit>& polygon_45_set_data<Unit>::operator+=(Unit delta) { 735 return resize(delta); 736 } 737 template <typename Unit> operator -=(Unit delta)738 inline polygon_45_set_data<Unit>& polygon_45_set_data<Unit>::operator-=(Unit delta) { 739 return (*this) += -delta; 740 } 741 742 template <typename Unit> 743 inline polygon_45_set_data<Unit>& resize(Unit resizing,RoundingOption rounding,CornerOption corner)744 polygon_45_set_data<Unit>::resize(Unit resizing, RoundingOption rounding, CornerOption corner) { 745 if(resizing == 0) return *this; 746 std::list<polygon_45_with_holes_data<Unit> > pl; 747 get_polygons_with_holes(pl); 748 clear(); 749 for(typename std::list<polygon_45_with_holes_data<Unit> >::iterator itr = pl.begin(); itr != pl.end(); ++itr) { 750 insert_with_resize(*itr, resizing, rounding, corner); 751 } 752 clean(); 753 //perterb 45 edges to prevent non-integer intersection errors upon boolean op 754 //snap(); 755 return *this; 756 } 757 758 //distance is assumed to be positive roundClosest(double distance)759 inline int roundClosest(double distance) { 760 int f = (int)distance; 761 if(distance - (double)f < 0.5) return f; 762 return f+1; 763 } 764 765 //distance is assumed to be positive 766 template <typename Unit> roundWithOptions(double distance,RoundingOption rounding)767 inline Unit roundWithOptions(double distance, RoundingOption rounding) { 768 if(rounding == CLOSEST) { 769 return roundClosest(distance); 770 } else if(rounding == OVERSIZE) { 771 return (Unit)distance + 1; 772 } else { //UNDERSIZE 773 return (Unit)distance; 774 } 775 } 776 777 // 0 is east, 1 is northeast, 2 is north, 3 is northwest, 4 is west, 5 is southwest, 6 is south 778 // 7 is southwest 779 template <typename Unit> bloatVertexInDirWithOptions(const point_data<Unit> & point,unsigned int dir,Unit bloating,RoundingOption rounding)780 inline point_data<Unit> bloatVertexInDirWithOptions(const point_data<Unit>& point, unsigned int dir, 781 Unit bloating, RoundingOption rounding) { 782 const double sqrt2 = 1.4142135623730950488016887242097; 783 if(dir & 1) { 784 Unit unitDistance = (Unit)bloating; 785 if(rounding != SQRT2) { 786 //45 degree bloating 787 double distance = (double)bloating; 788 distance /= sqrt2; // multiply by 1/sqrt2 789 unitDistance = roundWithOptions<Unit>(distance, rounding); 790 } 791 int xMultiplier = 1; 792 int yMultiplier = 1; 793 if(dir == 3 || dir == 5) xMultiplier = -1; 794 if(dir == 5 || dir == 7) yMultiplier = -1; 795 return point_data<Unit>(point.x()+xMultiplier*unitDistance, 796 point.y()+yMultiplier*unitDistance); 797 } else { 798 if(dir == 0) 799 return point_data<Unit>(point.x()+bloating, point.y()); 800 if(dir == 2) 801 return point_data<Unit>(point.x(), point.y()+bloating); 802 if(dir == 4) 803 return point_data<Unit>(point.x()-bloating, point.y()); 804 if(dir == 6) 805 return point_data<Unit>(point.x(), point.y()-bloating); 806 return point_data<Unit>(); 807 } 808 } 809 810 template <typename Unit> getEdge45Direction(const point_data<Unit> & pt1,const point_data<Unit> & pt2)811 inline unsigned int getEdge45Direction(const point_data<Unit>& pt1, const point_data<Unit>& pt2) { 812 if(pt1.x() == pt2.x()) { 813 if(pt1.y() < pt2.y()) return 2; 814 return 6; 815 } 816 if(pt1.y() == pt2.y()) { 817 if(pt1.x() < pt2.x()) return 0; 818 return 4; 819 } 820 if(pt2.y() > pt1.y()) { 821 if(pt2.x() > pt1.x()) return 1; 822 return 3; 823 } 824 if(pt2.x() > pt1.x()) return 7; 825 return 5; 826 } 827 getEdge45NormalDirection(unsigned int dir,int multiplier)828 inline unsigned int getEdge45NormalDirection(unsigned int dir, int multiplier) { 829 if(multiplier < 0) 830 return (dir + 2) % 8; 831 return (dir + 4 + 2) % 8; 832 } 833 834 template <typename Unit> getIntersectionPoint(const point_data<Unit> & pt1,unsigned int slope1,const point_data<Unit> & pt2,unsigned int slope2)835 inline point_data<Unit> getIntersectionPoint(const point_data<Unit>& pt1, unsigned int slope1, 836 const point_data<Unit>& pt2, unsigned int slope2) { 837 //the intention here is to use all integer arithmetic without causing overflow 838 //turncation error or divide by zero error 839 //I don't use floating point arithmetic because its precision may not be high enough 840 //at the extremes of the integer range 841 typedef typename coordinate_traits<Unit>::area_type LongUnit; 842 const Unit rises[8] = {0, 1, 1, 1, 0, -1, -1, -1}; 843 const Unit runs[8] = {1, 1, 0, -1, -1, -1, 0, 1}; 844 LongUnit rise1 = rises[slope1]; 845 LongUnit rise2 = rises[slope2]; 846 LongUnit run1 = runs[slope1]; 847 LongUnit run2 = runs[slope2]; 848 LongUnit x1 = (LongUnit)pt1.x(); 849 LongUnit x2 = (LongUnit)pt2.x(); 850 LongUnit y1 = (LongUnit)pt1.y(); 851 LongUnit y2 = (LongUnit)pt2.y(); 852 Unit x = 0; 853 Unit y = 0; 854 if(run1 == 0) { 855 x = pt1.x(); 856 y = (Unit)(((x1 - x2) * rise2) / run2) + pt2.y(); 857 } else if(run2 == 0) { 858 x = pt2.x(); 859 y = (Unit)(((x2 - x1) * rise1) / run1) + pt1.y(); 860 } else { 861 // y - y1 = (rise1/run1)(x - x1) 862 // y - y2 = (rise2/run2)(x - x2) 863 // y = (rise1/run1)(x - x1) + y1 = (rise2/run2)(x - x2) + y2 864 // (rise1/run1 - rise2/run2)x = y2 - y1 + rise1/run1 x1 - rise2/run2 x2 865 // x = (y2 - y1 + rise1/run1 x1 - rise2/run2 x2)/(rise1/run1 - rise2/run2) 866 // x = (y2 - y1 + rise1/run1 x1 - rise2/run2 x2)(rise1 run2 - rise2 run1)/(run1 run2) 867 x = (Unit)((y2 - y1 + ((rise1 * x1) / run1) - ((rise2 * x2) / run2)) * 868 (run1 * run2) / (rise1 * run2 - rise2 * run1)); 869 if(rise1 == 0) { 870 y = pt1.y(); 871 } else if(rise2 == 0) { 872 y = pt2.y(); 873 } else { 874 // y - y1 = (rise1/run1)(x - x1) 875 // (run1/rise1)(y - y1) = x - x1 876 // x = (run1/rise1)(y - y1) + x1 = (run2/rise2)(y - y2) + x2 877 y = (Unit)((x2 - x1 + ((run1 * y1) / rise1) - ((run2 * y2) / rise2)) * 878 (rise1 * rise2) / (run1 * rise2 - run2 * rise1)); 879 } 880 } 881 return point_data<Unit>(x, y); 882 } 883 884 template <typename Unit> 885 inline handleResizingEdge45_SQRT1OVER2(polygon_45_set_data<Unit> & sizingSet,point_data<Unit> first,point_data<Unit> second,Unit resizing,CornerOption corner)886 void handleResizingEdge45_SQRT1OVER2(polygon_45_set_data<Unit>& sizingSet, point_data<Unit> first, 887 point_data<Unit> second, Unit resizing, CornerOption corner) { 888 if(first.x() == second.x()) { 889 sizingSet.insert(rectangle_data<Unit>(first.x() - resizing, first.y(), first.x() + resizing, second.y())); 890 return; 891 } 892 if(first.y() == second.y()) { 893 sizingSet.insert(rectangle_data<Unit>(first.x(), first.y() - resizing, second.x(), first.y() + resizing)); 894 return; 895 } 896 std::vector<point_data<Unit> > pts; 897 Unit bloating = resizing < 0 ? -resizing : resizing; 898 if(corner == UNFILLED) { 899 //we have to round up 900 bloating = bloating / 2 + bloating % 2 ; //round up 901 if(second.x() < first.x()) std::swap(first, second); 902 if(first.y() < second.y()) { //upward sloping 903 pts.push_back(point_data<Unit>(first.x() + bloating, first.y() - bloating)); 904 pts.push_back(point_data<Unit>(first.x() - bloating, first.y() + bloating)); 905 pts.push_back(point_data<Unit>(second.x() - bloating, second.y() + bloating)); 906 pts.push_back(point_data<Unit>(second.x() + bloating, second.y() - bloating)); 907 sizingSet.insert_vertex_sequence(pts.begin(), pts.end(), CLOCKWISE, false); 908 } else { //downward sloping 909 pts.push_back(point_data<Unit>(first.x() + bloating, first.y() + bloating)); 910 pts.push_back(point_data<Unit>(first.x() - bloating, first.y() - bloating)); 911 pts.push_back(point_data<Unit>(second.x() - bloating, second.y() - bloating)); 912 pts.push_back(point_data<Unit>(second.x() + bloating, second.y() + bloating)); 913 sizingSet.insert_vertex_sequence(pts.begin(), pts.end(), COUNTERCLOCKWISE, false); 914 } 915 return; 916 } 917 if(second.x() < first.x()) std::swap(first, second); 918 if(first.y() < second.y()) { //upward sloping 919 pts.push_back(point_data<Unit>(first.x(), first.y() - bloating)); 920 pts.push_back(point_data<Unit>(first.x() - bloating, first.y())); 921 pts.push_back(point_data<Unit>(second.x(), second.y() + bloating)); 922 pts.push_back(point_data<Unit>(second.x() + bloating, second.y())); 923 sizingSet.insert_vertex_sequence(pts.begin(), pts.end(), CLOCKWISE, false); 924 } else { //downward sloping 925 pts.push_back(point_data<Unit>(first.x() - bloating, first.y())); 926 pts.push_back(point_data<Unit>(first.x(), first.y() + bloating)); 927 pts.push_back(point_data<Unit>(second.x() + bloating, second.y())); 928 pts.push_back(point_data<Unit>(second.x(), second.y() - bloating)); 929 sizingSet.insert_vertex_sequence(pts.begin(), pts.end(), CLOCKWISE, false); 930 } 931 } 932 933 934 template <typename Unit> 935 inline handleResizingEdge45(polygon_45_set_data<Unit> & sizingSet,point_data<Unit> first,point_data<Unit> second,Unit resizing,RoundingOption rounding)936 void handleResizingEdge45(polygon_45_set_data<Unit>& sizingSet, point_data<Unit> first, 937 point_data<Unit> second, Unit resizing, RoundingOption rounding) { 938 if(first.x() == second.x()) { 939 sizingSet.insert(rectangle_data<int>(first.x() - resizing, first.y(), first.x() + resizing, second.y())); 940 return; 941 } 942 if(first.y() == second.y()) { 943 sizingSet.insert(rectangle_data<int>(first.x(), first.y() - resizing, second.x(), first.y() + resizing)); 944 return; 945 } 946 //edge is 45 947 std::vector<point_data<Unit> > pts; 948 Unit bloating = resizing < 0 ? -resizing : resizing; 949 if(second.x() < first.x()) std::swap(first, second); 950 if(first.y() < second.y()) { 951 pts.push_back(bloatVertexInDirWithOptions(first, 3, bloating, rounding)); 952 pts.push_back(bloatVertexInDirWithOptions(first, 7, bloating, rounding)); 953 pts.push_back(bloatVertexInDirWithOptions(second, 7, bloating, rounding)); 954 pts.push_back(bloatVertexInDirWithOptions(second, 3, bloating, rounding)); 955 sizingSet.insert_vertex_sequence(pts.begin(), pts.end(), HIGH, false); 956 } else { 957 pts.push_back(bloatVertexInDirWithOptions(first, 1, bloating, rounding)); 958 pts.push_back(bloatVertexInDirWithOptions(first, 5, bloating, rounding)); 959 pts.push_back(bloatVertexInDirWithOptions(second, 5, bloating, rounding)); 960 pts.push_back(bloatVertexInDirWithOptions(second, 1, bloating, rounding)); 961 sizingSet.insert_vertex_sequence(pts.begin(), pts.end(), HIGH, false); 962 } 963 } 964 965 template <typename Unit> bloatVertexInDirWithSQRT1OVER2(int edge1,int normal1,const point_data<Unit> & second,Unit bloating,bool first)966 inline point_data<Unit> bloatVertexInDirWithSQRT1OVER2(int edge1, int normal1, const point_data<Unit>& second, Unit bloating, 967 bool first) { 968 orientation_2d orient = first ? HORIZONTAL : VERTICAL; 969 orientation_2d orientp = orient.get_perpendicular(); 970 int multiplier = first ? 1 : -1; 971 point_data<Unit> pt1(second); 972 if(edge1 == 1) { 973 if(normal1 == 3) { 974 move(pt1, orient, -multiplier * bloating); 975 } else { 976 move(pt1, orientp, -multiplier * bloating); 977 } 978 } else if(edge1 == 3) { 979 if(normal1 == 1) { 980 move(pt1, orient, multiplier * bloating); 981 } else { 982 move(pt1, orientp, -multiplier * bloating); 983 } 984 } else if(edge1 == 5) { 985 if(normal1 == 3) { 986 move(pt1, orientp, multiplier * bloating); 987 } else { 988 move(pt1, orient, multiplier * bloating); 989 } 990 } else { 991 if(normal1 == 5) { 992 move(pt1, orient, -multiplier * bloating); 993 } else { 994 move(pt1, orientp, multiplier * bloating); 995 } 996 } 997 return pt1; 998 } 999 1000 template <typename Unit> 1001 inline handleResizingVertex45(polygon_45_set_data<Unit> & sizingSet,const point_data<Unit> & first,const point_data<Unit> & second,const point_data<Unit> & third,Unit resizing,RoundingOption rounding,CornerOption corner,int multiplier)1002 void handleResizingVertex45(polygon_45_set_data<Unit>& sizingSet, const point_data<Unit>& first, 1003 const point_data<Unit>& second, const point_data<Unit>& third, Unit resizing, 1004 RoundingOption rounding, CornerOption corner, 1005 int multiplier) { 1006 unsigned int edge1 = getEdge45Direction(first, second); 1007 unsigned int edge2 = getEdge45Direction(second, third); 1008 unsigned int diffAngle; 1009 if(multiplier < 0) 1010 diffAngle = (edge2 + 8 - edge1) % 8; 1011 else 1012 diffAngle = (edge1 + 8 - edge2) % 8; 1013 if(diffAngle < 4) { 1014 if(resizing > 0) return; //accute interior corner 1015 else multiplier *= -1; //make it appear to be an accute exterior angle 1016 } 1017 Unit bloating = local_abs(resizing); 1018 if(rounding == SQRT1OVER2) { 1019 if(edge1 % 2 && edge2 % 2) return; 1020 if(corner == ORTHOGONAL && edge1 % 2 == 0 && edge2 % 2 == 0) { 1021 rectangle_data<Unit> insertion_rect; 1022 set_points(insertion_rect, second, second); 1023 bloat(insertion_rect, bloating); 1024 sizingSet.insert(insertion_rect); 1025 } else if(corner != ORTHOGONAL) { 1026 point_data<Unit> pt1(0, 0); 1027 point_data<Unit> pt2(0, 0); 1028 unsigned int normal1 = getEdge45NormalDirection(edge1, multiplier); 1029 unsigned int normal2 = getEdge45NormalDirection(edge2, multiplier); 1030 if(edge1 % 2) { 1031 pt1 = bloatVertexInDirWithSQRT1OVER2(edge1, normal1, second, bloating, true); 1032 } else { 1033 pt1 = bloatVertexInDirWithOptions(second, normal1, bloating, UNDERSIZE); 1034 } 1035 if(edge2 % 2) { 1036 pt2 = bloatVertexInDirWithSQRT1OVER2(edge2, normal2, second, bloating, false); 1037 } else { 1038 pt2 = bloatVertexInDirWithOptions(second, normal2, bloating, UNDERSIZE); 1039 } 1040 std::vector<point_data<Unit> > pts; 1041 pts.push_back(pt1); 1042 pts.push_back(second); 1043 pts.push_back(pt2); 1044 pts.push_back(getIntersectionPoint(pt1, edge1, pt2, edge2)); 1045 polygon_45_data<Unit> poly(pts.begin(), pts.end()); 1046 sizingSet.insert(poly); 1047 } else { 1048 //ORTHOGONAL of a 45 degree corner 1049 int normal = 0; 1050 if(edge1 % 2) { 1051 normal = getEdge45NormalDirection(edge2, multiplier); 1052 } else { 1053 normal = getEdge45NormalDirection(edge1, multiplier); 1054 } 1055 rectangle_data<Unit> insertion_rect; 1056 point_data<Unit> edgePoint = bloatVertexInDirWithOptions(second, normal, bloating, UNDERSIZE); 1057 set_points(insertion_rect, second, edgePoint); 1058 if(normal == 0 || normal == 4) 1059 bloat(insertion_rect, VERTICAL, bloating); 1060 else 1061 bloat(insertion_rect, HORIZONTAL, bloating); 1062 sizingSet.insert(insertion_rect); 1063 } 1064 return; 1065 } 1066 unsigned int normal1 = getEdge45NormalDirection(edge1, multiplier); 1067 unsigned int normal2 = getEdge45NormalDirection(edge2, multiplier); 1068 point_data<Unit> edgePoint1 = bloatVertexInDirWithOptions(second, normal1, bloating, rounding); 1069 point_data<Unit> edgePoint2 = bloatVertexInDirWithOptions(second, normal2, bloating, rounding); 1070 //if the change in angle is 135 degrees it is an accute exterior corner 1071 if((edge1+ multiplier * 3) % 8 == edge2) { 1072 if(corner == ORTHOGONAL) { 1073 rectangle_data<Unit> insertion_rect; 1074 set_points(insertion_rect, edgePoint1, edgePoint2); 1075 sizingSet.insert(insertion_rect); 1076 return; 1077 } 1078 } 1079 std::vector<point_data<Unit> > pts; 1080 pts.push_back(edgePoint1); 1081 pts.push_back(second); 1082 pts.push_back(edgePoint2); 1083 pts.push_back(getIntersectionPoint(edgePoint1, edge1, edgePoint2, edge2)); 1084 polygon_45_data<Unit> poly(pts.begin(), pts.end()); 1085 sizingSet.insert(poly); 1086 } 1087 1088 template <typename Unit> 1089 template <typename geometry_type> 1090 inline polygon_45_set_data<Unit>& insert_with_resize_dispatch(const geometry_type & poly,coordinate_type resizing,RoundingOption rounding,CornerOption corner,bool hole,polygon_45_concept)1091 polygon_45_set_data<Unit>::insert_with_resize_dispatch(const geometry_type& poly, 1092 coordinate_type resizing, 1093 RoundingOption rounding, 1094 CornerOption corner, 1095 bool hole, polygon_45_concept ) { 1096 direction_1d wdir = winding(poly); 1097 int multiplier = wdir == LOW ? -1 : 1; 1098 if(hole) resizing *= -1; 1099 typedef typename polygon_45_data<Unit>::iterator_type piterator; 1100 piterator first, second, third, end, real_end; 1101 real_end = end_points(poly); 1102 third = begin_points(poly); 1103 first = third; 1104 if(first == real_end) return *this; 1105 ++third; 1106 if(third == real_end) return *this; 1107 second = end = third; 1108 ++third; 1109 if(third == real_end) return *this; 1110 polygon_45_set_data<Unit> sizingSet; 1111 //insert minkofski shapes on edges and corners 1112 do { 1113 if(rounding != SQRT1OVER2) { 1114 handleResizingEdge45(sizingSet, *first, *second, resizing, rounding); 1115 } else { 1116 handleResizingEdge45_SQRT1OVER2(sizingSet, *first, *second, resizing, corner); 1117 } 1118 if(corner != UNFILLED) 1119 handleResizingVertex45(sizingSet, *first, *second, *third, resizing, rounding, corner, multiplier); 1120 first = second; 1121 second = third; 1122 ++third; 1123 if(third == real_end) { 1124 third = begin_points(poly); 1125 if(*second == *third) { 1126 ++third; //skip first point if it is duplicate of last point 1127 } 1128 } 1129 } while(second != end); 1130 //sizingSet.snap(); 1131 polygon_45_set_data<Unit> tmp; 1132 //insert original shape 1133 tmp.insert_dispatch(poly, false, polygon_45_concept()); 1134 if(resizing < 0) tmp -= sizingSet; 1135 else tmp += sizingSet; 1136 tmp.clean(); 1137 insert(tmp, hole); 1138 dirty_ = true; 1139 unsorted_ = true; 1140 return (*this); 1141 } 1142 1143 // accumulate the bloated polygon with holes 1144 template <typename Unit> 1145 template <typename geometry_type> 1146 inline polygon_45_set_data<Unit>& insert_with_resize_dispatch(const geometry_type & poly,coordinate_type resizing,RoundingOption rounding,CornerOption corner,bool hole,polygon_45_with_holes_concept)1147 polygon_45_set_data<Unit>::insert_with_resize_dispatch(const geometry_type& poly, 1148 coordinate_type resizing, 1149 RoundingOption rounding, 1150 CornerOption corner, 1151 bool hole, polygon_45_with_holes_concept ) { 1152 insert_with_resize_dispatch(poly, resizing, rounding, corner, hole, polygon_45_concept()); 1153 for(typename polygon_with_holes_traits<geometry_type>::iterator_holes_type itr = 1154 begin_holes(poly); itr != end_holes(poly); 1155 ++itr) { 1156 insert_with_resize_dispatch(*itr, resizing, rounding, corner, !hole, polygon_45_concept()); 1157 } 1158 return *this; 1159 } 1160 1161 // transform set 1162 template <typename Unit> 1163 template <typename transformation_type> transform(const transformation_type & tr)1164 inline polygon_45_set_data<Unit>& polygon_45_set_data<Unit>::transform(const transformation_type& tr){ 1165 clean(); 1166 std::vector<polygon_45_with_holes_data<Unit> > polys; 1167 get(polys); 1168 for(typename std::vector<polygon_45_with_holes_data<Unit> >::iterator itr = polys.begin(); 1169 itr != polys.end(); ++itr) { 1170 ::boost::polygon::transform(*itr, tr); 1171 } 1172 clear(); 1173 insert(polys.begin(), polys.end()); 1174 dirty_ = true; 1175 unsorted_ = true; 1176 return *this; 1177 } 1178 1179 template <typename Unit> scale_up(typename coordinate_traits<Unit>::unsigned_area_type factor)1180 inline polygon_45_set_data<Unit>& polygon_45_set_data<Unit>::scale_up(typename coordinate_traits<Unit>::unsigned_area_type factor) { 1181 scale_up_vertex_45_compact_range(data_.begin(), data_.end(), factor); 1182 return *this; 1183 } 1184 1185 template <typename Unit> scale_down(typename coordinate_traits<Unit>::unsigned_area_type factor)1186 inline polygon_45_set_data<Unit>& polygon_45_set_data<Unit>::scale_down(typename coordinate_traits<Unit>::unsigned_area_type factor) { 1187 clean(); 1188 std::vector<polygon_45_with_holes_data<Unit> > polys; 1189 get_polygons_with_holes(polys); 1190 for(typename std::vector<polygon_45_with_holes_data<Unit> >::iterator itr = polys.begin(); 1191 itr != polys.end(); ++itr) { 1192 ::boost::polygon::scale_down(*itr, factor); 1193 } 1194 clear(); 1195 insert(polys.begin(), polys.end()); 1196 dirty_ = true; 1197 unsorted_ = true; 1198 return *this; 1199 } 1200 1201 template <typename Unit> scale(double factor)1202 inline polygon_45_set_data<Unit>& polygon_45_set_data<Unit>::scale(double factor) { 1203 clean(); 1204 std::vector<polygon_45_with_holes_data<Unit> > polys; 1205 get_polygons_with_holes(polys); 1206 for(typename std::vector<polygon_45_with_holes_data<Unit> >::iterator itr = polys.begin(); 1207 itr != polys.end(); ++itr) { 1208 ::boost::polygon::scale(*itr, factor); 1209 } 1210 clear(); 1211 insert(polys.begin(), polys.end()); 1212 dirty_ = true; 1213 unsorted_ = true; 1214 return *this; 1215 } 1216 1217 template <typename Unit> clean() const1218 inline bool polygon_45_set_data<Unit>::clean() const { 1219 if(unsorted_) sort(); 1220 if(dirty_) { 1221 applyAdaptiveUnary_<0>(); 1222 dirty_ = false; 1223 } 1224 return true; 1225 } 1226 1227 template <typename Unit> 1228 template <int op> applyAdaptiveBoolean_(const polygon_45_set_data<Unit> & rvalue) const1229 inline void polygon_45_set_data<Unit>::applyAdaptiveBoolean_(const polygon_45_set_data<Unit>& rvalue) const { 1230 polygon_45_set_data<Unit> tmp; 1231 applyAdaptiveBoolean_<op>(tmp, rvalue); 1232 data_.swap(tmp.data_); //swapping vectors should be constant time operation 1233 error_data_.swap(tmp.error_data_); 1234 is_manhattan_ = tmp.is_manhattan_; 1235 unsorted_ = false; 1236 dirty_ = false; 1237 } 1238 1239 template <typename Unit2, int op> applyBoolean45OpOnVectors(std::vector<typename polygon_45_formation<Unit2>::Vertex45Compact> & result_data,std::vector<typename polygon_45_formation<Unit2>::Vertex45Compact> & lvalue_data,std::vector<typename polygon_45_formation<Unit2>::Vertex45Compact> & rvalue_data)1240 bool applyBoolean45OpOnVectors(std::vector<typename polygon_45_formation<Unit2>::Vertex45Compact>& result_data, 1241 std::vector<typename polygon_45_formation<Unit2>::Vertex45Compact>& lvalue_data, 1242 std::vector<typename polygon_45_formation<Unit2>::Vertex45Compact>& rvalue_data 1243 ) { 1244 bool result_is_manhattan_ = true; 1245 typename boolean_op_45<Unit2>::template Scan45<typename boolean_op_45<Unit2>::Count2, 1246 typename boolean_op_45<Unit2>::template boolean_op_45_output_functor<op> > scan45; 1247 std::vector<typename boolean_op_45<Unit2>::Vertex45> eventOut; 1248 typedef std::pair<typename boolean_op_45<Unit2>::Point, 1249 typename boolean_op_45<Unit2>::template Scan45CountT<typename boolean_op_45<Unit2>::Count2> > Scan45Vertex; 1250 std::vector<Scan45Vertex> eventIn; 1251 typedef std::vector<typename polygon_45_formation<Unit2>::Vertex45Compact> value_type; 1252 typename value_type::const_iterator iter1 = lvalue_data.begin(); 1253 typename value_type::const_iterator iter2 = rvalue_data.begin(); 1254 typename value_type::const_iterator end1 = lvalue_data.end(); 1255 typename value_type::const_iterator end2 = rvalue_data.end(); 1256 const Unit2 UnitMax = (std::numeric_limits<Unit2>::max)(); 1257 Unit2 x = UnitMax; 1258 while(iter1 != end1 || iter2 != end2) { 1259 Unit2 currentX = UnitMax; 1260 if(iter1 != end1) currentX = iter1->pt.x(); 1261 if(iter2 != end2) currentX = (std::min)(currentX, iter2->pt.x()); 1262 if(currentX != x) { 1263 //std::cout << "SCAN " << currentX << "\n"; 1264 //scan event 1265 scan45.scan(eventOut, eventIn.begin(), eventIn.end()); 1266 polygon_sort(eventOut.begin(), eventOut.end()); 1267 std::size_t ptCount = 0; 1268 for(std::size_t i = 0; i < eventOut.size(); ++i) { 1269 if(!result_data.empty() && 1270 result_data.back().pt == eventOut[i].pt) { 1271 result_data.back().count += eventOut[i]; 1272 ++ptCount; 1273 } else { 1274 if(!result_data.empty()) { 1275 if(result_data.back().count.is_45()) { 1276 result_is_manhattan_ = false; 1277 } 1278 if(ptCount == 2 && result_data.back().count == (typename polygon_45_formation<Unit2>::Vertex45Count(0, 0, 0, 0))) { 1279 result_data.pop_back(); 1280 } 1281 } 1282 result_data.push_back(eventOut[i]); 1283 ptCount = 1; 1284 } 1285 } 1286 if(ptCount == 2 && result_data.back().count == (typename polygon_45_formation<Unit2>::Vertex45Count(0, 0, 0, 0))) { 1287 result_data.pop_back(); 1288 } 1289 eventOut.clear(); 1290 eventIn.clear(); 1291 x = currentX; 1292 } 1293 //std::cout << "get next\n"; 1294 if(iter2 != end2 && (iter1 == end1 || iter2->pt.x() < iter1->pt.x() || 1295 (iter2->pt.x() == iter1->pt.x() && 1296 iter2->pt.y() < iter1->pt.y()) )) { 1297 //std::cout << "case1 next\n"; 1298 eventIn.push_back(Scan45Vertex 1299 (iter2->pt, 1300 typename polygon_45_formation<Unit2>:: 1301 Scan45Count(typename polygon_45_formation<Unit2>::Count2(0, iter2->count[0]), 1302 typename polygon_45_formation<Unit2>::Count2(0, iter2->count[1]), 1303 typename polygon_45_formation<Unit2>::Count2(0, iter2->count[2]), 1304 typename polygon_45_formation<Unit2>::Count2(0, iter2->count[3])))); 1305 ++iter2; 1306 } else if(iter1 != end1 && (iter2 == end2 || iter1->pt.x() < iter2->pt.x() || 1307 (iter1->pt.x() == iter2->pt.x() && 1308 iter1->pt.y() < iter2->pt.y()) )) { 1309 //std::cout << "case2 next\n"; 1310 eventIn.push_back(Scan45Vertex 1311 (iter1->pt, 1312 typename polygon_45_formation<Unit2>:: 1313 Scan45Count( 1314 typename polygon_45_formation<Unit2>::Count2(iter1->count[0], 0), 1315 typename polygon_45_formation<Unit2>::Count2(iter1->count[1], 0), 1316 typename polygon_45_formation<Unit2>::Count2(iter1->count[2], 0), 1317 typename polygon_45_formation<Unit2>::Count2(iter1->count[3], 0)))); 1318 ++iter1; 1319 } else { 1320 //std::cout << "case3 next\n"; 1321 eventIn.push_back(Scan45Vertex 1322 (iter2->pt, 1323 typename polygon_45_formation<Unit2>:: 1324 Scan45Count(typename polygon_45_formation<Unit2>::Count2(iter1->count[0], 1325 iter2->count[0]), 1326 typename polygon_45_formation<Unit2>::Count2(iter1->count[1], 1327 iter2->count[1]), 1328 typename polygon_45_formation<Unit2>::Count2(iter1->count[2], 1329 iter2->count[2]), 1330 typename polygon_45_formation<Unit2>::Count2(iter1->count[3], 1331 iter2->count[3])))); 1332 ++iter1; 1333 ++iter2; 1334 } 1335 } 1336 scan45.scan(eventOut, eventIn.begin(), eventIn.end()); 1337 polygon_sort(eventOut.begin(), eventOut.end()); 1338 1339 std::size_t ptCount = 0; 1340 for(std::size_t i = 0; i < eventOut.size(); ++i) { 1341 if(!result_data.empty() && 1342 result_data.back().pt == eventOut[i].pt) { 1343 result_data.back().count += eventOut[i]; 1344 ++ptCount; 1345 } else { 1346 if(!result_data.empty()) { 1347 if(result_data.back().count.is_45()) { 1348 result_is_manhattan_ = false; 1349 } 1350 if(ptCount == 2 && result_data.back().count == (typename polygon_45_formation<Unit2>::Vertex45Count(0, 0, 0, 0))) { 1351 result_data.pop_back(); 1352 } 1353 } 1354 result_data.push_back(eventOut[i]); 1355 ptCount = 1; 1356 } 1357 } 1358 if(ptCount == 2 && result_data.back().count == (typename polygon_45_formation<Unit2>::Vertex45Count(0, 0, 0, 0))) { 1359 result_data.pop_back(); 1360 } 1361 if(!result_data.empty() && 1362 result_data.back().count.is_45()) { 1363 result_is_manhattan_ = false; 1364 } 1365 return result_is_manhattan_; 1366 } 1367 1368 template <typename Unit2, int op> applyUnary45OpOnVectors(std::vector<typename polygon_45_formation<Unit2>::Vertex45Compact> & result_data,std::vector<typename polygon_45_formation<Unit2>::Vertex45Compact> & lvalue_data)1369 bool applyUnary45OpOnVectors(std::vector<typename polygon_45_formation<Unit2>::Vertex45Compact>& result_data, 1370 std::vector<typename polygon_45_formation<Unit2>::Vertex45Compact>& lvalue_data ) { 1371 bool result_is_manhattan_ = true; 1372 typename boolean_op_45<Unit2>::template Scan45<typename boolean_op_45<Unit2>::Count1, 1373 typename boolean_op_45<Unit2>::template unary_op_45_output_functor<op> > scan45; 1374 std::vector<typename boolean_op_45<Unit2>::Vertex45> eventOut; 1375 typedef typename boolean_op_45<Unit2>::template Scan45CountT<typename boolean_op_45<Unit2>::Count1> Scan45Count; 1376 typedef std::pair<typename boolean_op_45<Unit2>::Point, Scan45Count> Scan45Vertex; 1377 std::vector<Scan45Vertex> eventIn; 1378 typedef std::vector<typename polygon_45_formation<Unit2>::Vertex45Compact> value_type; 1379 typename value_type::const_iterator iter1 = lvalue_data.begin(); 1380 typename value_type::const_iterator end1 = lvalue_data.end(); 1381 const Unit2 UnitMax = (std::numeric_limits<Unit2>::max)(); 1382 Unit2 x = UnitMax; 1383 while(iter1 != end1) { 1384 Unit2 currentX = iter1->pt.x(); 1385 if(currentX != x) { 1386 //std::cout << "SCAN " << currentX << "\n"; 1387 //scan event 1388 scan45.scan(eventOut, eventIn.begin(), eventIn.end()); 1389 polygon_sort(eventOut.begin(), eventOut.end()); 1390 std::size_t ptCount = 0; 1391 for(std::size_t i = 0; i < eventOut.size(); ++i) { 1392 if(!result_data.empty() && 1393 result_data.back().pt == eventOut[i].pt) { 1394 result_data.back().count += eventOut[i]; 1395 ++ptCount; 1396 } else { 1397 if(!result_data.empty()) { 1398 if(result_data.back().count.is_45()) { 1399 result_is_manhattan_ = false; 1400 } 1401 if(ptCount == 2 && result_data.back().count == (typename polygon_45_formation<Unit2>::Vertex45Count(0, 0, 0, 0))) { 1402 result_data.pop_back(); 1403 } 1404 } 1405 result_data.push_back(eventOut[i]); 1406 ptCount = 1; 1407 } 1408 } 1409 if(ptCount == 2 && result_data.back().count == (typename polygon_45_formation<Unit2>::Vertex45Count(0, 0, 0, 0))) { 1410 result_data.pop_back(); 1411 } 1412 eventOut.clear(); 1413 eventIn.clear(); 1414 x = currentX; 1415 } 1416 //std::cout << "get next\n"; 1417 eventIn.push_back(Scan45Vertex 1418 (iter1->pt, 1419 Scan45Count( typename boolean_op_45<Unit2>::Count1(iter1->count[0]), 1420 typename boolean_op_45<Unit2>::Count1(iter1->count[1]), 1421 typename boolean_op_45<Unit2>::Count1(iter1->count[2]), 1422 typename boolean_op_45<Unit2>::Count1(iter1->count[3])))); 1423 ++iter1; 1424 } 1425 scan45.scan(eventOut, eventIn.begin(), eventIn.end()); 1426 polygon_sort(eventOut.begin(), eventOut.end()); 1427 1428 std::size_t ptCount = 0; 1429 for(std::size_t i = 0; i < eventOut.size(); ++i) { 1430 if(!result_data.empty() && 1431 result_data.back().pt == eventOut[i].pt) { 1432 result_data.back().count += eventOut[i]; 1433 ++ptCount; 1434 } else { 1435 if(!result_data.empty()) { 1436 if(result_data.back().count.is_45()) { 1437 result_is_manhattan_ = false; 1438 } 1439 if(ptCount == 2 && result_data.back().count == (typename polygon_45_formation<Unit2>::Vertex45Count(0, 0, 0, 0))) { 1440 result_data.pop_back(); 1441 } 1442 } 1443 result_data.push_back(eventOut[i]); 1444 ptCount = 1; 1445 } 1446 } 1447 if(ptCount == 2 && result_data.back().count == (typename polygon_45_formation<Unit2>::Vertex45Count(0, 0, 0, 0))) { 1448 result_data.pop_back(); 1449 } 1450 if(!result_data.empty() && 1451 result_data.back().count.is_45()) { 1452 result_is_manhattan_ = false; 1453 } 1454 return result_is_manhattan_; 1455 } 1456 1457 template <typename cT, typename iT> get_error_rects_shell(cT & posE,cT & negE,iT beginr,iT endr)1458 void get_error_rects_shell(cT& posE, cT& negE, iT beginr, iT endr) { 1459 typedef typename std::iterator_traits<iT>::value_type Point; 1460 typedef typename point_traits<Point>::coordinate_type Unit; 1461 typedef typename coordinate_traits<Unit>::area_type area_type; 1462 Point pt1, pt2, pt3; 1463 bool i1 = true; 1464 bool i2 = true; 1465 bool not_done = beginr != endr; 1466 bool next_to_last = false; 1467 bool last = false; 1468 Point first, second; 1469 while(not_done) { 1470 if(last) { 1471 last = false; 1472 not_done = false; 1473 pt3 = second; 1474 } else if(next_to_last) { 1475 next_to_last = false; 1476 last = true; 1477 pt3 = first; 1478 } else if(i1) { 1479 const Point& pt = *beginr; 1480 first = pt1 = pt; 1481 i1 = false; 1482 i2 = true; 1483 ++beginr; 1484 if(beginr == endr) return; //too few points 1485 continue; 1486 } else if (i2) { 1487 const Point& pt = *beginr; 1488 second = pt2 = pt; 1489 i2 = false; 1490 ++beginr; 1491 if(beginr == endr) return; //too few points 1492 continue; 1493 } else { 1494 const Point& pt = *beginr; 1495 pt3 = pt; 1496 ++beginr; 1497 if(beginr == endr) { 1498 next_to_last = true; 1499 //skip last point equal to first 1500 continue; 1501 } 1502 } 1503 if(local_abs(x(pt2)) % 2) { //y % 2 should also be odd 1504 //is corner concave or convex? 1505 Point pts[] = {pt1, pt2, pt3}; 1506 area_type ar = point_sequence_area<Point*, area_type>(pts, pts+3); 1507 direction_1d dir = ar < 0 ? COUNTERCLOCKWISE : CLOCKWISE; 1508 //std::cout << pt1 << " " << pt2 << " " << pt3 << " " << ar << std::endl; 1509 if(dir == CLOCKWISE) { 1510 posE.push_back(rectangle_data<typename Point::coordinate_type> 1511 (x(pt2) - 1, y(pt2) - 1, x(pt2) + 1, y(pt2) + 1)); 1512 1513 } else { 1514 negE.push_back(rectangle_data<typename Point::coordinate_type> 1515 (x(pt2) - 1, y(pt2) - 1, x(pt2) + 1, y(pt2) + 1)); 1516 } 1517 } 1518 pt1 = pt2; 1519 pt2 = pt3; 1520 } 1521 } 1522 1523 template <typename cT, typename pT> get_error_rects(cT & posE,cT & negE,const pT & p)1524 void get_error_rects(cT& posE, cT& negE, const pT& p) { 1525 get_error_rects_shell(posE, negE, p.begin(), p.end()); 1526 for(typename pT::iterator_holes_type iHb = p.begin_holes(); 1527 iHb != p.end_holes(); ++iHb) { 1528 get_error_rects_shell(posE, negE, iHb->begin(), iHb->end()); 1529 } 1530 } 1531 1532 template <typename Unit> 1533 template <int op> applyAdaptiveBoolean_(polygon_45_set_data<Unit> & result,const polygon_45_set_data<Unit> & rvalue) const1534 inline void polygon_45_set_data<Unit>::applyAdaptiveBoolean_(polygon_45_set_data<Unit>& result, 1535 const polygon_45_set_data<Unit>& rvalue) const { 1536 result.clear(); 1537 result.error_data_ = error_data_; 1538 result.error_data_.insert(result.error_data_.end(), rvalue.error_data_.begin(), 1539 rvalue.error_data_.end()); 1540 if(is_manhattan() && rvalue.is_manhattan()) { 1541 //convert each into polygon_90_set data and call boolean operations 1542 polygon_90_set_data<Unit> l90sd(VERTICAL), r90sd(VERTICAL), output(VERTICAL); 1543 for(typename value_type::const_iterator itr = data_.begin(); itr != data_.end(); ++itr) { 1544 if((*itr).count[3] == 0) continue; //skip all non vertical edges 1545 l90sd.insert(std::make_pair((*itr).pt.x(), std::make_pair<Unit, int>((*itr).pt.y(), (*itr).count[3])), false, VERTICAL); 1546 } 1547 for(typename value_type::const_iterator itr = rvalue.data_.begin(); itr != rvalue.data_.end(); ++itr) { 1548 if((*itr).count[3] == 0) continue; //skip all non vertical edges 1549 r90sd.insert(std::make_pair((*itr).pt.x(), std::make_pair<Unit, int>((*itr).pt.y(), (*itr).count[3])), false, VERTICAL); 1550 } 1551 l90sd.sort(); 1552 r90sd.sort(); 1553 #ifdef BOOST_POLYGON_MSVC 1554 #pragma warning (push) 1555 #pragma warning (disable: 4127) 1556 #endif 1557 if(op == 0) { 1558 output.applyBooleanBinaryOp(l90sd.begin(), l90sd.end(), 1559 r90sd.begin(), r90sd.end(), boolean_op::BinaryCount<boolean_op::BinaryOr>()); 1560 } else if (op == 1) { 1561 output.applyBooleanBinaryOp(l90sd.begin(), l90sd.end(), 1562 r90sd.begin(), r90sd.end(), boolean_op::BinaryCount<boolean_op::BinaryAnd>()); 1563 } else if (op == 2) { 1564 output.applyBooleanBinaryOp(l90sd.begin(), l90sd.end(), 1565 r90sd.begin(), r90sd.end(), boolean_op::BinaryCount<boolean_op::BinaryNot>()); 1566 } else if (op == 3) { 1567 output.applyBooleanBinaryOp(l90sd.begin(), l90sd.end(), 1568 r90sd.begin(), r90sd.end(), boolean_op::BinaryCount<boolean_op::BinaryXor>()); 1569 } 1570 #ifdef BOOST_POLYGON_MSVC 1571 #pragma warning (pop) 1572 #endif 1573 result.data_.clear(); 1574 result.insert(output); 1575 result.is_manhattan_ = true; 1576 result.dirty_ = false; 1577 result.unsorted_ = false; 1578 } else { 1579 sort(); 1580 rvalue.sort(); 1581 try { 1582 result.is_manhattan_ = applyBoolean45OpOnVectors<Unit, op>(result.data_, data_, rvalue.data_); 1583 } catch (std::string str) { 1584 std::string msg = "GTL 45 Boolean error, precision insufficient to represent edge intersection coordinate value."; 1585 if(str == msg) { 1586 result.clear(); 1587 typedef typename coordinate_traits<Unit>::manhattan_area_type Unit2; 1588 typedef typename polygon_45_formation<Unit2>::Vertex45Compact Vertex45Compact2; 1589 typedef std::vector<Vertex45Compact2> Data2; 1590 Data2 rvalue_data, lvalue_data, result_data; 1591 rvalue_data.reserve(rvalue.data_.size()); 1592 lvalue_data.reserve(data_.size()); 1593 for(std::size_t i = 0 ; i < data_.size(); ++i) { 1594 const Vertex45Compact& vi = data_[i]; 1595 Vertex45Compact2 ci; 1596 ci.pt = point_data<Unit2>(x(vi.pt), y(vi.pt)); 1597 ci.count = typename polygon_45_formation<Unit2>::Vertex45Count 1598 ( vi.count[0], vi.count[1], vi.count[2], vi.count[3]); 1599 lvalue_data.push_back(ci); 1600 } 1601 for(std::size_t i = 0 ; i < rvalue.data_.size(); ++i) { 1602 const Vertex45Compact& vi = rvalue.data_[i]; 1603 Vertex45Compact2 ci; 1604 ci.pt = (point_data<Unit2>(x(vi.pt), y(vi.pt))); 1605 ci.count = typename polygon_45_formation<Unit2>::Vertex45Count 1606 ( vi.count[0], vi.count[1], vi.count[2], vi.count[3]); 1607 rvalue_data.push_back(ci); 1608 } 1609 scale_up_vertex_45_compact_range(lvalue_data.begin(), lvalue_data.end(), 2); 1610 scale_up_vertex_45_compact_range(rvalue_data.begin(), rvalue_data.end(), 2); 1611 bool result_is_manhattan = applyBoolean45OpOnVectors<Unit2, op>(result_data, 1612 lvalue_data, 1613 rvalue_data ); 1614 if(!result_is_manhattan) { 1615 typename polygon_45_formation<Unit2>::Polygon45Formation pf(false); 1616 //std::cout << "FORMING POLYGONS\n"; 1617 std::vector<polygon_45_with_holes_data<Unit2> > container; 1618 pf.scan(container, result_data.begin(), result_data.end()); 1619 Data2 error_data_out; 1620 std::vector<rectangle_data<Unit2> > pos_error_rects; 1621 std::vector<rectangle_data<Unit2> > neg_error_rects; 1622 for(std::size_t i = 0; i < container.size(); ++i) { 1623 get_error_rects(pos_error_rects, neg_error_rects, container[i]); 1624 } 1625 for(std::size_t i = 0; i < pos_error_rects.size(); ++i) { 1626 insert_rectangle_into_vector_45(result_data, pos_error_rects[i], false); 1627 insert_rectangle_into_vector_45(error_data_out, pos_error_rects[i], false); 1628 } 1629 for(std::size_t i = 0; i < neg_error_rects.size(); ++i) { 1630 insert_rectangle_into_vector_45(result_data, neg_error_rects[i], true); 1631 insert_rectangle_into_vector_45(error_data_out, neg_error_rects[i], false); 1632 } 1633 scale_down_vertex_45_compact_range_blindly(error_data_out.begin(), error_data_out.end(), 2); 1634 for(std::size_t i = 0 ; i < error_data_out.size(); ++i) { 1635 const Vertex45Compact2& vi = error_data_out[i]; 1636 Vertex45Compact ci; 1637 ci.pt.x(static_cast<Unit>(x(vi.pt))); 1638 ci.pt.y(static_cast<Unit>(y(vi.pt))); 1639 ci.count = typename polygon_45_formation<Unit>::Vertex45Count 1640 ( vi.count[0], vi.count[1], vi.count[2], vi.count[3]); 1641 result.error_data_.push_back(ci); 1642 } 1643 Data2 new_result_data; 1644 polygon_sort(result_data.begin(), result_data.end()); 1645 applyUnary45OpOnVectors<Unit2, 0>(new_result_data, result_data); //OR operation 1646 result_data.swap(new_result_data); 1647 } 1648 scale_down_vertex_45_compact_range_blindly(result_data.begin(), result_data.end(), 2); 1649 //result.data_.reserve(result_data.size()); 1650 for(std::size_t i = 0 ; i < result_data.size(); ++i) { 1651 const Vertex45Compact2& vi = result_data[i]; 1652 Vertex45Compact ci; 1653 ci.pt.x(static_cast<Unit>(x(vi.pt))); 1654 ci.pt.y(static_cast<Unit>(y(vi.pt))); 1655 ci.count = typename polygon_45_formation<Unit>::Vertex45Count 1656 ( vi.count[0], vi.count[1], vi.count[2], vi.count[3]); 1657 result.data_.push_back(ci); 1658 } 1659 result.is_manhattan_ = result_is_manhattan; 1660 result.dirty_ = false; 1661 result.unsorted_ = false; 1662 } else { throw str; } 1663 } 1664 //std::cout << "DONE SCANNING\n"; 1665 } 1666 } 1667 1668 template <typename Unit> 1669 template <int op> applyAdaptiveUnary_() const1670 inline void polygon_45_set_data<Unit>::applyAdaptiveUnary_() const { 1671 polygon_45_set_data<Unit> result; 1672 result.error_data_ = error_data_; 1673 if(is_manhattan()) { 1674 //convert each into polygon_90_set data and call boolean operations 1675 polygon_90_set_data<Unit> l90sd(VERTICAL); 1676 for(typename value_type::const_iterator itr = data_.begin(); itr != data_.end(); ++itr) { 1677 if((*itr).count[3] == 0) continue; //skip all non vertical edges 1678 l90sd.insert(std::make_pair((*itr).pt.x(), std::make_pair<Unit, int>((*itr).pt.y(), (*itr).count[3])), false, VERTICAL); 1679 } 1680 l90sd.sort(); 1681 #ifdef BOOST_POLYGON_MSVC 1682 #pragma warning (push) 1683 #pragma warning (disable: 4127) 1684 #endif 1685 if(op == 0) { 1686 l90sd.clean(); 1687 } else if (op == 1) { 1688 l90sd.self_intersect(); 1689 } else if (op == 3) { 1690 l90sd.self_xor(); 1691 } 1692 #ifdef BOOST_POLYGON_MSVC 1693 #pragma warning (pop) 1694 #endif 1695 result.data_.clear(); 1696 result.insert(l90sd); 1697 result.is_manhattan_ = true; 1698 result.dirty_ = false; 1699 result.unsorted_ = false; 1700 } else { 1701 sort(); 1702 try { 1703 result.is_manhattan_ = applyUnary45OpOnVectors<Unit, op>(result.data_, data_); 1704 } catch (std::string str) { 1705 std::string msg = "GTL 45 Boolean error, precision insufficient to represent edge intersection coordinate value."; 1706 if(str == msg) { 1707 result.clear(); 1708 typedef typename coordinate_traits<Unit>::manhattan_area_type Unit2; 1709 typedef typename polygon_45_formation<Unit2>::Vertex45Compact Vertex45Compact2; 1710 typedef std::vector<Vertex45Compact2> Data2; 1711 Data2 lvalue_data, result_data; 1712 lvalue_data.reserve(data_.size()); 1713 for(std::size_t i = 0 ; i < data_.size(); ++i) { 1714 const Vertex45Compact& vi = data_[i]; 1715 Vertex45Compact2 ci; 1716 ci.pt.x(static_cast<Unit>(x(vi.pt))); 1717 ci.pt.y(static_cast<Unit>(y(vi.pt))); 1718 ci.count = typename polygon_45_formation<Unit2>::Vertex45Count 1719 ( vi.count[0], vi.count[1], vi.count[2], vi.count[3]); 1720 lvalue_data.push_back(ci); 1721 } 1722 scale_up_vertex_45_compact_range(lvalue_data.begin(), lvalue_data.end(), 2); 1723 bool result_is_manhattan = applyUnary45OpOnVectors<Unit2, op>(result_data, 1724 lvalue_data ); 1725 if(!result_is_manhattan) { 1726 typename polygon_45_formation<Unit2>::Polygon45Formation pf(false); 1727 //std::cout << "FORMING POLYGONS\n"; 1728 std::vector<polygon_45_with_holes_data<Unit2> > container; 1729 pf.scan(container, result_data.begin(), result_data.end()); 1730 Data2 error_data_out; 1731 std::vector<rectangle_data<Unit2> > pos_error_rects; 1732 std::vector<rectangle_data<Unit2> > neg_error_rects; 1733 for(std::size_t i = 0; i < container.size(); ++i) { 1734 get_error_rects(pos_error_rects, neg_error_rects, container[i]); 1735 } 1736 for(std::size_t i = 0; i < pos_error_rects.size(); ++i) { 1737 insert_rectangle_into_vector_45(result_data, pos_error_rects[i], false); 1738 insert_rectangle_into_vector_45(error_data_out, pos_error_rects[i], false); 1739 } 1740 for(std::size_t i = 0; i < neg_error_rects.size(); ++i) { 1741 insert_rectangle_into_vector_45(result_data, neg_error_rects[i], true); 1742 insert_rectangle_into_vector_45(error_data_out, neg_error_rects[i], false); 1743 } 1744 scale_down_vertex_45_compact_range_blindly(error_data_out.begin(), error_data_out.end(), 2); 1745 for(std::size_t i = 0 ; i < error_data_out.size(); ++i) { 1746 const Vertex45Compact2& vi = error_data_out[i]; 1747 Vertex45Compact ci; 1748 ci.pt.x(static_cast<Unit>(x(vi.pt))); 1749 ci.pt.y(static_cast<Unit>(y(vi.pt))); 1750 ci.count = typename polygon_45_formation<Unit>::Vertex45Count 1751 ( vi.count[0], vi.count[1], vi.count[2], vi.count[3]); 1752 result.error_data_.push_back(ci); 1753 } 1754 Data2 new_result_data; 1755 polygon_sort(result_data.begin(), result_data.end()); 1756 applyUnary45OpOnVectors<Unit2, 0>(new_result_data, result_data); //OR operation 1757 result_data.swap(new_result_data); 1758 } 1759 scale_down_vertex_45_compact_range_blindly(result_data.begin(), result_data.end(), 2); 1760 //result.data_.reserve(result_data.size()); 1761 for(std::size_t i = 0 ; i < result_data.size(); ++i) { 1762 const Vertex45Compact2& vi = result_data[i]; 1763 Vertex45Compact ci; 1764 ci.pt.x(static_cast<Unit>(x(vi.pt))); 1765 ci.pt.y(static_cast<Unit>(y(vi.pt))); 1766 ci.count = typename polygon_45_formation<Unit>::Vertex45Count 1767 ( vi.count[0], vi.count[1], vi.count[2], vi.count[3]); 1768 result.data_.push_back(ci); 1769 } 1770 result.is_manhattan_ = result_is_manhattan; 1771 result.dirty_ = false; 1772 result.unsorted_ = false; 1773 } else { throw str; } 1774 } 1775 //std::cout << "DONE SCANNING\n"; 1776 } 1777 data_.swap(result.data_); 1778 error_data_.swap(result.error_data_); 1779 dirty_ = result.dirty_; 1780 unsorted_ = result.unsorted_; 1781 is_manhattan_ = result.is_manhattan_; 1782 } 1783 1784 template <typename coordinate_type, typename property_type> 1785 class property_merge_45 { 1786 private: 1787 typedef typename coordinate_traits<coordinate_type>::manhattan_area_type big_coord; 1788 typedef typename polygon_45_property_merge<big_coord, property_type>::MergeSetData tsd; 1789 tsd tsd_; 1790 public: property_merge_45()1791 inline property_merge_45() : tsd_() {} property_merge_45(const property_merge_45 & that)1792 inline property_merge_45(const property_merge_45& that) : tsd_(that.tsd_) {} operator =(const property_merge_45 & that)1793 inline property_merge_45& operator=(const property_merge_45& that) { 1794 tsd_ = that.tsd_; 1795 return *this; 1796 } 1797 insert(const polygon_45_set_data<coordinate_type> & ps,property_type property)1798 inline void insert(const polygon_45_set_data<coordinate_type>& ps, property_type property) { 1799 ps.clean(); 1800 polygon_45_property_merge<big_coord, property_type>::populateMergeSetData(tsd_, ps.begin(), ps.end(), property); 1801 } 1802 template <class GeoObjT> insert(const GeoObjT & geoObj,property_type property)1803 inline void insert(const GeoObjT& geoObj, property_type property) { 1804 polygon_45_set_data<coordinate_type> ps; 1805 ps.insert(geoObj); 1806 insert(ps, property); 1807 } 1808 1809 //merge properties of input geometries and store the resulting geometries of regions 1810 //with unique sets of merged properties to polygons sets in a map keyed by sets of properties 1811 // T = std::map<std::set<property_type>, polygon_45_set_data<coordiante_type> > or 1812 // T = std::map<std::vector<property_type>, polygon_45_set_data<coordiante_type> > 1813 template <class result_type> merge(result_type & result)1814 inline void merge(result_type& result) { 1815 typedef typename result_type::key_type keytype; 1816 typedef std::map<keytype, polygon_45_set_data<big_coord> > bigtype; 1817 bigtype result_big; 1818 polygon_45_property_merge<big_coord, property_type>::performMerge(result_big, tsd_); 1819 std::vector<polygon_45_with_holes_data<big_coord> > polys; 1820 std::vector<rectangle_data<big_coord> > pos_error_rects; 1821 std::vector<rectangle_data<big_coord> > neg_error_rects; 1822 for(typename std::map<keytype, polygon_45_set_data<big_coord> >::iterator itr = result_big.begin(); 1823 itr != result_big.end(); ++itr) { 1824 polys.clear(); 1825 (*itr).second.get(polys); 1826 for(std::size_t i = 0; i < polys.size(); ++i) { 1827 get_error_rects(pos_error_rects, neg_error_rects, polys[i]); 1828 } 1829 (*itr).second += pos_error_rects; 1830 (*itr).second -= neg_error_rects; 1831 (*itr).second.scale_down(2); 1832 result[(*itr).first].insert((*itr).second); 1833 } 1834 } 1835 }; 1836 1837 //ConnectivityExtraction computes the graph of connectivity between rectangle, polygon and 1838 //polygon set graph nodes where an edge is created whenever the geometry in two nodes overlap 1839 template <typename coordinate_type> 1840 class connectivity_extraction_45 { 1841 private: 1842 typedef typename coordinate_traits<coordinate_type>::manhattan_area_type big_coord; 1843 typedef typename polygon_45_touch<big_coord>::TouchSetData tsd; 1844 tsd tsd_; 1845 unsigned int nodeCount_; 1846 public: connectivity_extraction_45()1847 inline connectivity_extraction_45() : tsd_(), nodeCount_(0) {} connectivity_extraction_45(const connectivity_extraction_45 & that)1848 inline connectivity_extraction_45(const connectivity_extraction_45& that) : tsd_(that.tsd_), 1849 nodeCount_(that.nodeCount_) {} operator =(const connectivity_extraction_45 & that)1850 inline connectivity_extraction_45& operator=(const connectivity_extraction_45& that) { 1851 tsd_ = that.tsd_; 1852 nodeCount_ = that.nodeCount_; {} 1853 return *this; 1854 } 1855 1856 //insert a polygon set graph node, the value returned is the id of the graph node insert(const polygon_45_set_data<coordinate_type> & ps)1857 inline unsigned int insert(const polygon_45_set_data<coordinate_type>& ps) { 1858 ps.clean(); 1859 polygon_45_touch<big_coord>::populateTouchSetData(tsd_, ps.begin(), ps.end(), nodeCount_); 1860 return nodeCount_++; 1861 } 1862 template <class GeoObjT> insert(const GeoObjT & geoObj)1863 inline unsigned int insert(const GeoObjT& geoObj) { 1864 polygon_45_set_data<coordinate_type> ps; 1865 ps.insert(geoObj); 1866 return insert(ps); 1867 } 1868 1869 //extract connectivity and store the edges in the graph 1870 //graph must be indexable by graph node id and the indexed value must be a std::set of 1871 //graph node id 1872 template <class GraphT> extract(GraphT & graph)1873 inline void extract(GraphT& graph) { 1874 polygon_45_touch<big_coord>::performTouch(graph, tsd_); 1875 } 1876 }; 1877 } 1878 } 1879 #endif 1880 1881