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_SET_DATA_HPP 9 #define BOOST_POLYGON_POLYGON_SET_DATA_HPP 10 #include "polygon_45_set_data.hpp" 11 #include "polygon_45_set_concept.hpp" 12 #include "polygon_traits.hpp" 13 #include "detail/polygon_arbitrary_formation.hpp" 14 15 namespace boost { namespace polygon { 16 17 18 // utility function to round coordinate types down 19 // rounds down for both negative and positive numbers 20 // intended really for integer type T (does not make sense for float) 21 template <typename T> round_down(double val)22 static inline T round_down(double val) { 23 T rounded_val = (T)(val); 24 if(val < (double)rounded_val) 25 --rounded_val; 26 return rounded_val; 27 } 28 template <typename T> round_down(point_data<double> v)29 static inline point_data<T> round_down(point_data<double> v) { 30 return point_data<T>(round_down<T>(v.x()),round_down<T>(v.y())); 31 } 32 33 34 35 //foward declare view 36 template <typename ltype, typename rtype, int op_type> class polygon_set_view; 37 38 template <typename T> 39 class polygon_set_data { 40 public: 41 typedef T coordinate_type; 42 typedef point_data<T> point_type; 43 typedef std::pair<point_type, point_type> edge_type; 44 typedef std::pair<edge_type, int> element_type; 45 typedef std::vector<element_type> value_type; 46 typedef typename value_type::const_iterator iterator_type; 47 typedef polygon_set_data operator_arg_type; 48 49 // default constructor polygon_set_data()50 inline polygon_set_data() : data_(), dirty_(false), unsorted_(false), is_45_(true) {} 51 52 // constructor from an iterator pair over edge data 53 template <typename iT> polygon_set_data(iT input_begin,iT input_end)54 inline polygon_set_data(iT input_begin, iT input_end) : data_(), dirty_(false), unsorted_(false), is_45_(true) { 55 for( ; input_begin != input_end; ++input_begin) { insert(*input_begin); } 56 } 57 58 // copy constructor polygon_set_data(const polygon_set_data & that)59 inline polygon_set_data(const polygon_set_data& that) : 60 data_(that.data_), dirty_(that.dirty_), unsorted_(that.unsorted_), is_45_(that.is_45_) {} 61 62 // copy constructor 63 template <typename ltype, typename rtype, int op_type> 64 inline polygon_set_data(const polygon_set_view<ltype, rtype, op_type>& that); 65 66 // destructor ~polygon_set_data()67 inline ~polygon_set_data() {} 68 69 // assignement operator operator =(const polygon_set_data & that)70 inline polygon_set_data& operator=(const polygon_set_data& that) { 71 if(this == &that) return *this; 72 data_ = that.data_; 73 dirty_ = that.dirty_; 74 unsorted_ = that.unsorted_; 75 is_45_ = that.is_45_; 76 return *this; 77 } 78 79 template <typename ltype, typename rtype, int op_type> operator =(const polygon_set_view<ltype,rtype,op_type> & geometry)80 inline polygon_set_data& operator=(const polygon_set_view<ltype, rtype, op_type>& geometry) { 81 (*this) = geometry.value(); 82 dirty_ = false; 83 unsorted_ = false; 84 return *this; 85 } 86 87 template <typename geometry_object> operator =(const geometry_object & geometry)88 inline polygon_set_data& operator=(const geometry_object& geometry) { 89 data_.clear(); 90 insert(geometry); 91 return *this; 92 } 93 94 95 // insert iterator range insert(iterator_type input_begin,iterator_type input_end,bool is_hole=false)96 inline void insert(iterator_type input_begin, iterator_type input_end, bool is_hole = false) { 97 if(input_begin == input_end || (!data_.empty() && &(*input_begin) == &(*(data_.begin())))) 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 // insert iterator range 107 template <typename iT> insert(iT input_begin,iT input_end,bool is_hole=false)108 inline void insert(iT input_begin, iT input_end, bool is_hole = false) { 109 if(input_begin == input_end) return; 110 for(; input_begin != input_end; ++input_begin) { 111 insert(*input_begin, is_hole); 112 } 113 } 114 115 template <typename geometry_type> insert(const geometry_type & geometry_object,bool is_hole=false)116 inline void insert(const geometry_type& geometry_object, bool is_hole = false) { 117 insert(geometry_object, is_hole, typename geometry_concept<geometry_type>::type()); 118 } 119 120 template <typename polygon_type> insert(const polygon_type & polygon_object,bool is_hole,polygon_concept)121 inline void insert(const polygon_type& polygon_object, bool is_hole, polygon_concept ) { 122 insert_vertex_sequence(begin_points(polygon_object), end_points(polygon_object), winding(polygon_object), is_hole); 123 } 124 insert(const polygon_set_data & ps,bool is_hole=false)125 inline void insert(const polygon_set_data& ps, bool is_hole = false) { 126 insert(ps.data_.begin(), ps.data_.end(), is_hole); 127 } 128 129 template <typename polygon_45_set_type> insert(const polygon_45_set_type & ps,bool is_hole,polygon_45_set_concept)130 inline void insert(const polygon_45_set_type& ps, bool is_hole, polygon_45_set_concept) { 131 std::vector<polygon_45_with_holes_data<typename polygon_45_set_traits<polygon_45_set_type>::coordinate_type> > polys; 132 assign(polys, ps); 133 insert(polys.begin(), polys.end(), is_hole); 134 } 135 136 template <typename polygon_90_set_type> insert(const polygon_90_set_type & ps,bool is_hole,polygon_90_set_concept)137 inline void insert(const polygon_90_set_type& ps, bool is_hole, polygon_90_set_concept) { 138 std::vector<polygon_90_with_holes_data<typename polygon_90_set_traits<polygon_90_set_type>::coordinate_type> > polys; 139 assign(polys, ps); 140 insert(polys.begin(), polys.end(), is_hole); 141 } 142 143 template <typename polygon_type> insert(const polygon_type & polygon_object,bool is_hole,polygon_45_concept)144 inline void insert(const polygon_type& polygon_object, bool is_hole, polygon_45_concept ) { 145 insert(polygon_object, is_hole, polygon_concept()); } 146 147 template <typename polygon_type> insert(const polygon_type & polygon_object,bool is_hole,polygon_90_concept)148 inline void insert(const polygon_type& polygon_object, bool is_hole, polygon_90_concept ) { 149 insert(polygon_object, is_hole, polygon_concept()); } 150 151 template <typename polygon_with_holes_type> insert(const polygon_with_holes_type & polygon_with_holes_object,bool is_hole,polygon_with_holes_concept)152 inline void insert(const polygon_with_holes_type& polygon_with_holes_object, bool is_hole, 153 polygon_with_holes_concept ) { 154 insert(polygon_with_holes_object, is_hole, polygon_concept()); 155 for(typename polygon_with_holes_traits<polygon_with_holes_type>::iterator_holes_type itr = 156 begin_holes(polygon_with_holes_object); 157 itr != end_holes(polygon_with_holes_object); ++itr) { 158 insert(*itr, !is_hole, polygon_concept()); 159 } 160 } 161 162 template <typename polygon_with_holes_type> insert(const polygon_with_holes_type & polygon_with_holes_object,bool is_hole,polygon_45_with_holes_concept)163 inline void insert(const polygon_with_holes_type& polygon_with_holes_object, bool is_hole, 164 polygon_45_with_holes_concept ) { 165 insert(polygon_with_holes_object, is_hole, polygon_with_holes_concept()); } 166 167 template <typename polygon_with_holes_type> insert(const polygon_with_holes_type & polygon_with_holes_object,bool is_hole,polygon_90_with_holes_concept)168 inline void insert(const polygon_with_holes_type& polygon_with_holes_object, bool is_hole, 169 polygon_90_with_holes_concept ) { 170 insert(polygon_with_holes_object, is_hole, polygon_with_holes_concept()); } 171 172 template <typename rectangle_type> insert(const rectangle_type & rectangle_object,bool is_hole,rectangle_concept)173 inline void insert(const rectangle_type& rectangle_object, bool is_hole, rectangle_concept ) { 174 polygon_90_data<coordinate_type> poly; 175 assign(poly, rectangle_object); 176 insert(poly, is_hole, polygon_concept()); 177 } 178 insert_clean(const element_type & edge,bool is_hole=false)179 inline void insert_clean(const element_type& edge, bool is_hole = false) { 180 if( ! scanline_base<coordinate_type>::is_45_degree(edge.first) && 181 ! scanline_base<coordinate_type>::is_horizontal(edge.first) && 182 ! scanline_base<coordinate_type>::is_vertical(edge.first) ) is_45_ = false; 183 data_.push_back(edge); 184 if(data_.back().first.second < data_.back().first.first) { 185 std::swap(data_.back().first.second, data_.back().first.first); 186 data_.back().second *= -1; 187 } 188 if(is_hole) 189 data_.back().second *= -1; 190 } 191 insert(const element_type & edge,bool is_hole=false)192 inline void insert(const element_type& edge, bool is_hole = false) { 193 insert_clean(edge, is_hole); 194 dirty_ = true; 195 unsorted_ = true; 196 } 197 198 template <class iT> insert_vertex_sequence(iT begin_vertex,iT end_vertex,direction_1d winding,bool is_hole)199 inline void insert_vertex_sequence(iT begin_vertex, iT end_vertex, direction_1d winding, bool is_hole) { 200 if (begin_vertex == end_vertex) { 201 // No edges to insert. 202 return; 203 } 204 // Current edge endpoints. 205 iT vertex0 = begin_vertex; 206 iT vertex1 = begin_vertex; 207 if (++vertex1 == end_vertex) { 208 // No edges to insert. 209 return; 210 } 211 int wmultiplier = (winding == COUNTERCLOCKWISE) ? 1 : -1; 212 if (is_hole) { 213 wmultiplier = -wmultiplier; 214 } 215 dirty_ = true; 216 unsorted_ = true; 217 while (vertex0 != end_vertex) { 218 point_type p0, p1; 219 assign(p0, *vertex0); 220 assign(p1, *vertex1); 221 if (p0 != p1) { 222 int hmultiplier = (p0.get(HORIZONTAL) == p1.get(HORIZONTAL)) ? -1 : 1; 223 element_type elem(edge_type(p0, p1), hmultiplier * wmultiplier); 224 insert_clean(elem); 225 } 226 ++vertex0; 227 ++vertex1; 228 if (vertex1 == end_vertex) { 229 vertex1 = begin_vertex; 230 } 231 } 232 } 233 234 template <typename output_container> get(output_container & output) const235 inline void get(output_container& output) const { 236 get_dispatch(output, typename geometry_concept<typename output_container::value_type>::type()); 237 } 238 239 // append to the container cT with polygons of three or four verticies 240 // slicing orientation is vertical 241 template <class cT> get_trapezoids(cT & container) const242 void get_trapezoids(cT& container) const { 243 clean(); 244 trapezoid_arbitrary_formation<coordinate_type> pf; 245 typedef typename polygon_arbitrary_formation<coordinate_type>::vertex_half_edge vertex_half_edge; 246 std::vector<vertex_half_edge> data; 247 for(iterator_type itr = data_.begin(); itr != data_.end(); ++itr){ 248 data.push_back(vertex_half_edge((*itr).first.first, (*itr).first.second, (*itr).second)); 249 data.push_back(vertex_half_edge((*itr).first.second, (*itr).first.first, -1 * (*itr).second)); 250 } 251 polygon_sort(data.begin(), data.end()); 252 pf.scan(container, data.begin(), data.end()); 253 //std::cout << "DONE FORMING POLYGONS\n"; 254 } 255 256 // append to the container cT with polygons of three or four verticies 257 template <class cT> get_trapezoids(cT & container,orientation_2d slicing_orientation) const258 void get_trapezoids(cT& container, orientation_2d slicing_orientation) const { 259 if(slicing_orientation == VERTICAL) { 260 get_trapezoids(container); 261 } else { 262 polygon_set_data<T> ps(*this); 263 ps.transform(axis_transformation(axis_transformation::SWAP_XY)); 264 cT result; 265 ps.get_trapezoids(result); 266 for(typename cT::iterator itr = result.begin(); itr != result.end(); ++itr) { 267 ::boost::polygon::transform(*itr, axis_transformation(axis_transformation::SWAP_XY)); 268 } 269 container.insert(container.end(), result.begin(), result.end()); 270 } 271 } 272 273 // equivalence operator 274 inline bool operator==(const polygon_set_data& p) const; 275 276 // inequivalence operator operator !=(const polygon_set_data & p) const277 inline bool operator!=(const polygon_set_data& p) const { 278 return !((*this) == p); 279 } 280 281 // get iterator to begin vertex data begin() const282 inline iterator_type begin() const { 283 return data_.begin(); 284 } 285 286 // get iterator to end vertex data end() const287 inline iterator_type end() const { 288 return data_.end(); 289 } 290 value() const291 const value_type& value() const { 292 return data_; 293 } 294 295 // clear the contents of the polygon_set_data clear()296 inline void clear() { data_.clear(); dirty_ = unsorted_ = false; } 297 298 // find out if Polygon set is empty empty() const299 inline bool empty() const { return data_.empty(); } 300 301 // get the Polygon set size in vertices size() const302 inline std::size_t size() const { clean(); return data_.size(); } 303 304 // get the current Polygon set capacity in vertices capacity() const305 inline std::size_t capacity() const { return data_.capacity(); } 306 307 // reserve size of polygon set in vertices reserve(std::size_t size)308 inline void reserve(std::size_t size) { return data_.reserve(size); } 309 310 // find out if Polygon set is sorted sorted() const311 inline bool sorted() const { return !unsorted_; } 312 313 // find out if Polygon set is clean dirty() const314 inline bool dirty() const { return dirty_; } 315 316 void clean() const; 317 sort() const318 void sort() const{ 319 if(unsorted_) { 320 polygon_sort(data_.begin(), data_.end()); 321 unsorted_ = false; 322 } 323 } 324 325 template <typename input_iterator_type> set(input_iterator_type input_begin,input_iterator_type input_end)326 void set(input_iterator_type input_begin, input_iterator_type input_end) { 327 clear(); 328 reserve(std::distance(input_begin,input_end)); 329 insert(input_begin, input_end); 330 dirty_ = true; 331 unsorted_ = true; 332 } 333 set(const value_type & value)334 void set(const value_type& value) { 335 data_ = value; 336 dirty_ = true; 337 unsorted_ = true; 338 } 339 340 template <typename rectangle_type> extents(rectangle_type & rect)341 bool extents(rectangle_type& rect) { 342 clean(); 343 if(empty()) return false; 344 bool first_iteration = true; 345 for(iterator_type itr = begin(); 346 itr != end(); ++itr) { 347 rectangle_type edge_box; 348 set_points(edge_box, (*itr).first.first, (*itr).first.second); 349 if(first_iteration) 350 rect = edge_box; 351 else 352 encompass(rect, edge_box); 353 first_iteration = false; 354 } 355 return true; 356 } 357 358 inline polygon_set_data& 359 resize(coordinate_type resizing, bool corner_fill_arc = false, unsigned int num_circle_segments=0); 360 361 template <typename transform_type> 362 inline polygon_set_data& transform(const transform_type & tr)363 transform(const transform_type& tr) { 364 std::vector<polygon_with_holes_data<T> > polys; 365 get(polys); 366 clear(); 367 for(std::size_t i = 0 ; i < polys.size(); ++i) { 368 ::boost::polygon::transform(polys[i], tr); 369 insert(polys[i]); 370 } 371 unsorted_ = true; 372 dirty_ = true; 373 return *this; 374 } 375 376 inline polygon_set_data& scale_up(typename coordinate_traits<coordinate_type>::unsigned_area_type factor)377 scale_up(typename coordinate_traits<coordinate_type>::unsigned_area_type factor) { 378 for(typename value_type::iterator itr = data_.begin(); itr != data_.end(); ++itr) { 379 ::boost::polygon::scale_up((*itr).first.first, factor); 380 ::boost::polygon::scale_up((*itr).first.second, factor); 381 } 382 return *this; 383 } 384 385 inline polygon_set_data& scale_down(typename coordinate_traits<coordinate_type>::unsigned_area_type factor)386 scale_down(typename coordinate_traits<coordinate_type>::unsigned_area_type factor) { 387 for(typename value_type::iterator itr = data_.begin(); itr != data_.end(); ++itr) { 388 bool vb = (*itr).first.first.x() == (*itr).first.second.x(); 389 ::boost::polygon::scale_down((*itr).first.first, factor); 390 ::boost::polygon::scale_down((*itr).first.second, factor); 391 bool va = (*itr).first.first.x() == (*itr).first.second.x(); 392 if(!vb && va) { 393 (*itr).second *= -1; 394 } 395 } 396 unsorted_ = true; 397 dirty_ = true; 398 return *this; 399 } 400 401 template <typename scaling_type> scale(polygon_set_data & polygon_set,const scaling_type & scaling)402 inline polygon_set_data& scale(polygon_set_data& polygon_set, 403 const scaling_type& scaling) { 404 for(typename value_type::iterator itr = begin(); itr != end(); ++itr) { 405 bool vb = (*itr).first.first.x() == (*itr).first.second.x(); 406 ::boost::polygon::scale((*itr).first.first, scaling); 407 ::boost::polygon::scale((*itr).first.second, scaling); 408 bool va = (*itr).first.first.x() == (*itr).first.second.x(); 409 if(!vb && va) { 410 (*itr).second *= -1; 411 } 412 } 413 unsorted_ = true; 414 dirty_ = true; 415 return *this; 416 } 417 compute_offset_edge(point_data<long double> & pt1,point_data<long double> & pt2,const point_data<long double> & prev_pt,const point_data<long double> & current_pt,long double distance,int multiplier)418 static inline void compute_offset_edge(point_data<long double>& pt1, point_data<long double>& pt2, 419 const point_data<long double>& prev_pt, 420 const point_data<long double>& current_pt, 421 long double distance, int multiplier) { 422 long double dx = current_pt.x() - prev_pt.x(); 423 long double dy = current_pt.y() - prev_pt.y(); 424 long double edge_length = std::sqrt(dx*dx + dy*dy); 425 long double dnx = dy; 426 long double dny = -dx; 427 dnx = dnx * (long double)distance / edge_length; 428 dny = dny * (long double)distance / edge_length; 429 pt1.x(prev_pt.x() + (long double)dnx * (long double)multiplier); 430 pt2.x(current_pt.x() + (long double)dnx * (long double)multiplier); 431 pt1.y(prev_pt.y() + (long double)dny * (long double)multiplier); 432 pt2.y(current_pt.y() + (long double)dny * (long double)multiplier); 433 } 434 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 distance,coordinate_type multiplier)435 static inline void modify_pt(point_data<coordinate_type>& pt, const point_data<coordinate_type>& prev_pt, 436 const point_data<coordinate_type>& current_pt, const point_data<coordinate_type>& next_pt, 437 coordinate_type distance, coordinate_type multiplier) { 438 std::pair<point_data<long double>, point_data<long double> > he1, he2; 439 he1.first.x((long double)(prev_pt.x())); 440 he1.first.y((long double)(prev_pt.y())); 441 he1.second.x((long double)(current_pt.x())); 442 he1.second.y((long double)(current_pt.y())); 443 he2.first.x((long double)(current_pt.x())); 444 he2.first.y((long double)(current_pt.y())); 445 he2.second.x((long double)(next_pt.x())); 446 he2.second.y((long double)(next_pt.y())); 447 compute_offset_edge(he1.first, he1.second, prev_pt, current_pt, distance, multiplier); 448 compute_offset_edge(he2.first, he2.second, current_pt, next_pt, distance, multiplier); 449 typedef scanline_base<long double>::compute_intersection_pack pack; 450 point_data<long double> rpt; 451 point_data<long double> bisectorpt((he1.second.x()+he2.first.x())/2, 452 (he1.second.y()+he2.first.y())/2); 453 point_data<long double> orig_pt((long double)pt.x(), (long double)pt.y()); 454 if(euclidean_distance(bisectorpt, orig_pt) < distance/2) { 455 if(!pack::compute_lazy_intersection(rpt, he1, he2, true, false)) { 456 rpt = he1.second; //colinear offset edges use shared point 457 } 458 } else { 459 if(!pack::compute_lazy_intersection(rpt, he1, std::pair<point_data<long double>, point_data<long double> >(orig_pt, bisectorpt), true, false)) { 460 rpt = he1.second; //colinear offset edges use shared point 461 } 462 } 463 pt.x((coordinate_type)(std::floor(rpt.x()+0.5))); 464 pt.y((coordinate_type)(std::floor(rpt.y()+0.5))); 465 } 466 resize_poly_up(std::vector<point_data<coordinate_type>> & poly,coordinate_type distance,coordinate_type multiplier)467 static void resize_poly_up(std::vector<point_data<coordinate_type> >& poly, coordinate_type distance, coordinate_type multiplier) { 468 point_data<coordinate_type> first_pt = poly[0]; 469 point_data<coordinate_type> second_pt = poly[1]; 470 point_data<coordinate_type> prev_pt = poly[0]; 471 point_data<coordinate_type> current_pt = poly[1]; 472 for(std::size_t i = 2; i < poly.size()-1; ++i) { 473 point_data<coordinate_type> next_pt = poly[i]; 474 modify_pt(poly[i-1], prev_pt, current_pt, next_pt, distance, multiplier); 475 prev_pt = current_pt; 476 current_pt = next_pt; 477 } 478 point_data<coordinate_type> next_pt = first_pt; 479 modify_pt(poly[poly.size()-2], prev_pt, current_pt, next_pt, distance, multiplier); 480 prev_pt = current_pt; 481 current_pt = next_pt; 482 next_pt = second_pt; 483 modify_pt(poly[0], prev_pt, current_pt, next_pt, distance, multiplier); 484 poly.back() = poly.front(); 485 } resize_poly_down(std::vector<point_data<coordinate_type>> & poly,coordinate_type distance,coordinate_type multiplier)486 static bool resize_poly_down(std::vector<point_data<coordinate_type> >& poly, coordinate_type distance, coordinate_type multiplier) { 487 std::vector<point_data<coordinate_type> > orig_poly(poly); 488 rectangle_data<coordinate_type> extents_rectangle; 489 set_points(extents_rectangle, poly[0], poly[0]); 490 point_data<coordinate_type> first_pt = poly[0]; 491 point_data<coordinate_type> second_pt = poly[1]; 492 point_data<coordinate_type> prev_pt = poly[0]; 493 point_data<coordinate_type> current_pt = poly[1]; 494 encompass(extents_rectangle, current_pt); 495 for(std::size_t i = 2; i < poly.size()-1; ++i) { 496 point_data<coordinate_type> next_pt = poly[i]; 497 encompass(extents_rectangle, next_pt); 498 modify_pt(poly[i-1], prev_pt, current_pt, next_pt, distance, multiplier); 499 prev_pt = current_pt; 500 current_pt = next_pt; 501 } 502 if(delta(extents_rectangle, HORIZONTAL) <= std::abs(2*distance)) 503 return false; 504 if(delta(extents_rectangle, VERTICAL) <= std::abs(2*distance)) 505 return false; 506 point_data<coordinate_type> next_pt = first_pt; 507 modify_pt(poly[poly.size()-2], prev_pt, current_pt, next_pt, distance, multiplier); 508 prev_pt = current_pt; 509 current_pt = next_pt; 510 next_pt = second_pt; 511 modify_pt(poly[0], prev_pt, current_pt, next_pt, distance, multiplier); 512 poly.back() = poly.front(); 513 //if the line segments formed between orignial and new points cross for an edge that edge inverts 514 //if all edges invert the polygon should be discarded 515 //if even one edge does not invert return true because the polygon is valid 516 bool non_inverting_edge = false; 517 for(std::size_t i = 1; i < poly.size(); ++i) { 518 std::pair<point_data<coordinate_type>, point_data<coordinate_type> > 519 he1(poly[i], orig_poly[i]), 520 he2(poly[i-1], orig_poly[i-1]); 521 if(!scanline_base<coordinate_type>::intersects(he1, he2)) { 522 non_inverting_edge = true; 523 break; 524 } 525 } 526 return non_inverting_edge; 527 } 528 529 polygon_set_data& bloat(typename coordinate_traits<coordinate_type>::unsigned_area_type distance)530 bloat(typename coordinate_traits<coordinate_type>::unsigned_area_type distance) { 531 std::list<polygon_with_holes_data<coordinate_type> > polys; 532 get(polys); 533 clear(); 534 for(typename std::list<polygon_with_holes_data<coordinate_type> >::iterator itr = polys.begin(); 535 itr != polys.end(); ++itr) { 536 resize_poly_up((*itr).self_.coords_, (coordinate_type)distance, (coordinate_type)1); 537 insert_vertex_sequence((*itr).self_.begin(), (*itr).self_.end(), COUNTERCLOCKWISE, false); //inserts without holes 538 for(typename std::list<polygon_data<coordinate_type> >::iterator itrh = (*itr).holes_.begin(); 539 itrh != (*itr).holes_.end(); ++itrh) { 540 if(resize_poly_down((*itrh).coords_, (coordinate_type)distance, (coordinate_type)1)) { 541 insert_vertex_sequence((*itrh).coords_.begin(), (*itrh).coords_.end(), CLOCKWISE, true); 542 } 543 } 544 } 545 return *this; 546 } 547 548 polygon_set_data& shrink(typename coordinate_traits<coordinate_type>::unsigned_area_type distance)549 shrink(typename coordinate_traits<coordinate_type>::unsigned_area_type distance) { 550 std::list<polygon_with_holes_data<coordinate_type> > polys; 551 get(polys); 552 clear(); 553 for(typename std::list<polygon_with_holes_data<coordinate_type> >::iterator itr = polys.begin(); 554 itr != polys.end(); ++itr) { 555 if(resize_poly_down((*itr).self_.coords_, (coordinate_type)distance, (coordinate_type)-1)) { 556 insert_vertex_sequence((*itr).self_.begin(), (*itr).self_.end(), COUNTERCLOCKWISE, false); //inserts without holes 557 for(typename std::list<polygon_data<coordinate_type> >::iterator itrh = (*itr).holes_.begin(); 558 itrh != (*itr).holes_.end(); ++itrh) { 559 resize_poly_up((*itrh).coords_, (coordinate_type)distance, (coordinate_type)-1); 560 insert_vertex_sequence((*itrh).coords_.begin(), (*itrh).coords_.end(), CLOCKWISE, true); 561 } 562 } 563 } 564 return *this; 565 } 566 567 // TODO:: should be private 568 template <typename geometry_type> 569 inline polygon_set_data& insert_with_resize(const geometry_type & poly,coordinate_type resizing,bool corner_fill_arc=false,unsigned int num_circle_segments=0,bool hole=false)570 insert_with_resize(const geometry_type& poly, coordinate_type resizing, bool corner_fill_arc=false, unsigned int num_circle_segments=0, bool hole = false) { 571 return insert_with_resize_dispatch(poly, resizing, corner_fill_arc, num_circle_segments, hole, typename geometry_concept<geometry_type>::type()); 572 } 573 574 template <typename geometry_type> 575 inline polygon_set_data& insert_with_resize_dispatch(const geometry_type & poly,coordinate_type resizing,bool corner_fill_arc,unsigned int num_circle_segments,bool hole,polygon_with_holes_concept tag)576 insert_with_resize_dispatch(const geometry_type& poly, coordinate_type resizing, bool corner_fill_arc, unsigned int num_circle_segments, bool hole, 577 polygon_with_holes_concept tag) { 578 insert_with_resize_dispatch(poly, resizing, corner_fill_arc, num_circle_segments, hole, polygon_concept()); 579 for(typename polygon_with_holes_traits<geometry_type>::iterator_holes_type itr = 580 begin_holes(poly); itr != end_holes(poly); 581 ++itr) { 582 insert_with_resize_dispatch(*itr, resizing, corner_fill_arc, num_circle_segments, !hole, polygon_concept()); 583 } 584 return *this; 585 } 586 587 template <typename geometry_type> 588 inline polygon_set_data& insert_with_resize_dispatch(const geometry_type & poly,coordinate_type resizing,bool corner_fill_arc,unsigned int num_circle_segments,bool hole,polygon_concept tag)589 insert_with_resize_dispatch(const geometry_type& poly, coordinate_type resizing, bool corner_fill_arc, unsigned int num_circle_segments, bool hole, 590 polygon_concept tag) { 591 592 if (resizing==0) 593 return *this; 594 595 596 // one dimensional used to store CCW/CW flag 597 //direction_1d wdir = winding(poly); 598 // LOW==CLOCKWISE just faster to type 599 // so > 0 is CCW 600 //int multiplier = wdir == LOW ? -1 : 1; 601 //std::cout<<" multiplier : "<<multiplier<<std::endl; 602 //if(hole) resizing *= -1; 603 direction_1d resize_wdir = resizing>0?COUNTERCLOCKWISE:CLOCKWISE; 604 605 typedef typename polygon_data<T>::iterator_type piterator; 606 piterator first, second, third, end, real_end; 607 real_end = end_points(poly); 608 third = begin_points(poly); 609 first = third; 610 if(first == real_end) return *this; 611 ++third; 612 if(third == real_end) return *this; 613 second = end = third; 614 ++third; 615 if(third == real_end) return *this; 616 617 // for 1st corner 618 std::vector<point_data<T> > first_pts; 619 std::vector<point_data<T> > all_pts; 620 direction_1d first_wdir = CLOCKWISE; 621 622 // for all corners 623 polygon_set_data<T> sizingSet; 624 bool sizing_sign = resizing<0; 625 bool prev_concave = true; 626 point_data<T> prev_point; 627 //int iCtr=0; 628 629 630 //insert minkofski shapes on edges and corners 631 do { // REAL WORK IS HERE 632 633 634 //first, second and third point to points in correct CCW order 635 // check if convex or concave case 636 point_data<coordinate_type> normal1( second->y()-first->y(), first->x()-second->x()); 637 point_data<coordinate_type> normal2( third->y()-second->y(), second->x()-third->x()); 638 double direction = normal1.x()*normal2.y()- normal2.x()*normal1.y(); 639 bool convex = direction>0; 640 641 bool treat_as_concave = !convex; 642 if(sizing_sign) 643 treat_as_concave = convex; 644 point_data<double> v; 645 assign(v, normal1); 646 double s2 = (v.x()*v.x()+v.y()*v.y()); 647 double s = std::sqrt(s2)/resizing; 648 v = point_data<double>(v.x()/s,v.y()/s); 649 point_data<T> curr_prev; 650 if (prev_concave) 651 //TODO missing round_down() 652 curr_prev = point_data<T>(first->x()+v.x(),first->y()+v.y()); 653 else 654 curr_prev = prev_point; 655 656 // around concave corners - insert rectangle 657 // if previous corner is concave it's point info may be ignored 658 if ( treat_as_concave) { 659 std::vector<point_data<T> > pts; 660 661 pts.push_back(point_data<T>(second->x()+v.x(),second->y()+v.y())); 662 pts.push_back(*second); 663 pts.push_back(*first); 664 pts.push_back(point_data<T>(curr_prev)); 665 if (first_pts.size()){ 666 sizingSet.insert_vertex_sequence(pts.begin(),pts.end(), resize_wdir,false); 667 }else { 668 first_pts=pts; 669 first_wdir = resize_wdir; 670 } 671 } else { 672 673 // add either intersection_quad or pie_shape, based on corner_fill_arc option 674 // for convex corner (convexity depends on sign of resizing, whether we shrink or grow) 675 std::vector< std::vector<point_data<T> > > pts; 676 direction_1d winding; 677 winding = convex?COUNTERCLOCKWISE:CLOCKWISE; 678 if (make_resizing_vertex_list(pts, curr_prev, prev_concave, *first, *second, *third, resizing 679 , num_circle_segments, corner_fill_arc)) 680 { 681 if (first_pts.size()) { 682 for (int i=0; i<pts.size(); i++) { 683 sizingSet.insert_vertex_sequence(pts[i].begin(),pts[i].end(),winding,false); 684 } 685 686 } else { 687 first_pts = pts[0]; 688 first_wdir = resize_wdir; 689 for (int i=1; i<pts.size(); i++) { 690 sizingSet.insert_vertex_sequence(pts[i].begin(),pts[i].end(),winding,false); 691 } 692 } 693 prev_point = curr_prev; 694 695 } else { 696 treat_as_concave = true; 697 } 698 } 699 700 prev_concave = treat_as_concave; 701 first = second; 702 second = third; 703 ++third; 704 if(third == real_end) { 705 third = begin_points(poly); 706 if(*second == *third) { 707 ++third; //skip first point if it is duplicate of last point 708 } 709 } 710 } while(second != end); 711 712 // handle insertion of first point 713 if (!prev_concave) { 714 first_pts[first_pts.size()-1]=prev_point; 715 } 716 sizingSet.insert_vertex_sequence(first_pts.begin(),first_pts.end(),first_wdir,false); 717 718 polygon_set_data<coordinate_type> tmp; 719 720 //insert original shape 721 tmp.insert(poly, false, polygon_concept()); 722 if((resizing < 0) ^ hole) tmp -= sizingSet; 723 else tmp += sizingSet; 724 //tmp.clean(); 725 insert(tmp, hole); 726 return (*this); 727 } 728 729 730 inline polygon_set_data& 731 interact(const polygon_set_data& that); 732 downcast(polygon_45_set_data<coordinate_type> & result) const733 inline bool downcast(polygon_45_set_data<coordinate_type>& result) const { 734 if(!is_45_) return false; 735 for(iterator_type itr = begin(); itr != end(); ++itr) { 736 const element_type& elem = *itr; 737 int count = elem.second; 738 int rise = 1; //up sloping 45 739 if(scanline_base<coordinate_type>::is_horizontal(elem.first)) rise = 0; 740 else if(scanline_base<coordinate_type>::is_vertical(elem.first)) rise = 2; 741 else { 742 if(!scanline_base<coordinate_type>::is_45_degree(elem.first)) { 743 is_45_ = false; 744 return false; //consider throwing because is_45_ has be be wrong 745 } 746 if(elem.first.first.y() > elem.first.second.y()) rise = -1; //down sloping 45 747 } 748 typename polygon_45_set_data<coordinate_type>::Vertex45Compact vertex(elem.first.first, rise, count); 749 result.insert(vertex); 750 typename polygon_45_set_data<coordinate_type>::Vertex45Compact vertex2(elem.first.second, rise, -count); 751 result.insert(vertex2); 752 } 753 return true; 754 } 755 concept_downcast() const756 inline GEOMETRY_CONCEPT_ID concept_downcast() const { 757 typedef typename coordinate_traits<coordinate_type>::coordinate_difference delta_type; 758 bool is_45 = false; 759 for(iterator_type itr = begin(); itr != end(); ++itr) { 760 const element_type& elem = *itr; 761 delta_type h_delta = euclidean_distance(elem.first.first, elem.first.second, HORIZONTAL); 762 delta_type v_delta = euclidean_distance(elem.first.first, elem.first.second, VERTICAL); 763 if(h_delta != 0 || v_delta != 0) { 764 //neither delta is zero and the edge is not MANHATTAN 765 if(v_delta != h_delta && v_delta != -h_delta) return POLYGON_SET_CONCEPT; 766 else is_45 = true; 767 } 768 } 769 if(is_45) return POLYGON_45_SET_CONCEPT; 770 return POLYGON_90_SET_CONCEPT; 771 } 772 773 private: 774 mutable value_type data_; 775 mutable bool dirty_; 776 mutable bool unsorted_; 777 mutable bool is_45_; 778 779 private: 780 //functions 781 782 template <typename output_container> get_dispatch(output_container & output,polygon_concept tag) const783 void get_dispatch(output_container& output, polygon_concept tag) const { 784 get_fracture(output, true, tag); 785 } 786 template <typename output_container> get_dispatch(output_container & output,polygon_with_holes_concept tag) const787 void get_dispatch(output_container& output, polygon_with_holes_concept tag) const { 788 get_fracture(output, false, tag); 789 } 790 template <typename output_container, typename concept_type> get_fracture(output_container & container,bool fracture_holes,concept_type) const791 void get_fracture(output_container& container, bool fracture_holes, concept_type ) const { 792 clean(); 793 polygon_arbitrary_formation<coordinate_type> pf(fracture_holes); 794 typedef typename polygon_arbitrary_formation<coordinate_type>::vertex_half_edge vertex_half_edge; 795 std::vector<vertex_half_edge> data; 796 for(iterator_type itr = data_.begin(); itr != data_.end(); ++itr){ 797 data.push_back(vertex_half_edge((*itr).first.first, (*itr).first.second, (*itr).second)); 798 data.push_back(vertex_half_edge((*itr).first.second, (*itr).first.first, -1 * (*itr).second)); 799 } 800 polygon_sort(data.begin(), data.end()); 801 pf.scan(container, data.begin(), data.end()); 802 } 803 }; 804 805 struct polygon_set_concept; 806 template <typename T> 807 struct geometry_concept<polygon_set_data<T> > { 808 typedef polygon_set_concept type; 809 }; 810 811 // template <typename T> 812 // inline double compute_area(point_data<T>& a, point_data<T>& b, point_data<T>& c) { 813 814 // return (double)(b.x()-a.x())*(double)(c.y()-a.y())- (double)(c.x()-a.x())*(double)(b.y()-a.y()); 815 816 817 // } 818 819 template <typename T> make_resizing_vertex_list(std::vector<std::vector<point_data<T>>> & return_points,point_data<T> & curr_prev,bool ignore_prev_point,point_data<T> start,point_data<T> middle,point_data<T> end,double sizing_distance,unsigned int num_circle_segments,bool corner_fill_arc)820 inline int make_resizing_vertex_list(std::vector<std::vector<point_data< T> > >& return_points, 821 point_data<T>& curr_prev, bool ignore_prev_point, 822 point_data< T> start, point_data<T> middle, point_data< T> end, 823 double sizing_distance, unsigned int num_circle_segments, bool corner_fill_arc) { 824 825 // handle the case of adding an intersection point 826 point_data<double> dn1( middle.y()-start.y(), start.x()-middle.x()); 827 double size = sizing_distance/std::sqrt( dn1.x()*dn1.x()+dn1.y()*dn1.y()); 828 dn1 = point_data<double>( dn1.x()*size, dn1.y()* size); 829 point_data<double> dn2( end.y()-middle.y(), middle.x()-end.x()); 830 size = sizing_distance/std::sqrt( dn2.x()*dn2.x()+dn2.y()*dn2.y()); 831 dn2 = point_data<double>( dn2.x()*size, dn2.y()* size); 832 point_data<double> start_offset((start.x()+dn1.x()),(start.y()+dn1.y())); 833 point_data<double> mid1_offset((middle.x()+dn1.x()),(middle.y()+dn1.y())); 834 point_data<double> end_offset((end.x()+dn2.x()),(end.y()+dn2.y())); 835 point_data<double> mid2_offset((middle.x()+dn2.x()),(middle.y()+dn2.y())); 836 if (ignore_prev_point) 837 curr_prev = round_down<T>(start_offset); 838 839 840 if (corner_fill_arc) { 841 std::vector<point_data< T> > return_points1; 842 return_points.push_back(return_points1); 843 std::vector<point_data< T> >& return_points_back = return_points[return_points.size()-1]; 844 return_points_back.push_back(round_down<T>(mid1_offset)); 845 return_points_back.push_back(middle); 846 return_points_back.push_back(start); 847 return_points_back.push_back(curr_prev); 848 point_data<double> dmid(middle.x(),middle.y()); 849 return_points.push_back(return_points1); 850 int num = make_arc(return_points[return_points.size()-1],mid1_offset,mid2_offset,dmid,sizing_distance,num_circle_segments); 851 curr_prev = round_down<T>(mid2_offset); 852 return num; 853 854 } 855 856 std::pair<point_data<double>,point_data<double> > he1(start_offset,mid1_offset); 857 std::pair<point_data<double>,point_data<double> > he2(mid2_offset ,end_offset); 858 //typedef typename high_precision_type<double>::type high_precision; 859 860 point_data<T> intersect; 861 typename scanline_base<T>::compute_intersection_pack pack; 862 bool res = pack.compute_intersection(intersect,he1,he2,true); 863 if( res ) { 864 std::vector<point_data< T> > return_points1; 865 return_points.push_back(return_points1); 866 std::vector<point_data< T> >& return_points_back = return_points[return_points.size()-1]; 867 return_points_back.push_back(intersect); 868 return_points_back.push_back(middle); 869 return_points_back.push_back(start); 870 return_points_back.push_back(curr_prev); 871 872 //double d1= compute_area(intersect,middle,start); 873 //double d2= compute_area(start,curr_prev,intersect); 874 875 curr_prev = intersect; 876 877 878 return return_points.size(); 879 } 880 return 0; 881 882 } 883 884 // this routine should take in start and end point s.t. end point is CCW from start 885 // it sould make a pie slice polygon that is an intersection of that arc 886 // with an ngon segments approximation of the circle centered at center with radius r 887 // point start is gauaranteed to be on the segmentation 888 // returnPoints will start with the first point after start 889 // returnPoints vector may be empty 890 template <typename T> make_arc(std::vector<point_data<T>> & return_points,point_data<double> start,point_data<double> end,point_data<double> center,double r,unsigned int num_circle_segments)891 inline int make_arc(std::vector<point_data< T> >& return_points, 892 point_data< double> start, point_data< double> end, 893 point_data< double> center, double r, unsigned int num_circle_segments) { 894 const double our_pi=3.1415926535897932384626433832795028841971; 895 896 // derive start and end angles 897 double ps = atan2(start.y()-center.y(), start.x()-center.x()); 898 double pe = atan2(end.y()-center.y(), end.x()-center.x()); 899 if (ps < 0.0) 900 ps += 2.0 * our_pi; 901 if (pe <= 0.0) 902 pe += 2.0 * our_pi; 903 if (ps >= 2.0 * our_pi) 904 ps -= 2.0 * our_pi; 905 while (pe <= ps) 906 pe += 2.0 * our_pi; 907 double delta_angle = (2.0 * our_pi) / (double)num_circle_segments; 908 if ( start==end) // full circle? 909 { 910 ps = delta_angle*0.5; 911 pe = ps + our_pi * 2.0; 912 double x,y; 913 x = center.x() + r * cos(ps); 914 y = center.y() + r * sin(ps); 915 start = point_data<double>(x,y); 916 end = start; 917 } 918 return_points.push_back(round_down<T>(center)); 919 return_points.push_back(round_down<T>(start)); 920 unsigned int i=0; 921 double curr_angle = ps+delta_angle; 922 while( curr_angle < pe - 0.01 && i < 2 * num_circle_segments) { 923 i++; 924 double x = center.x() + r * cos( curr_angle); 925 double y = center.y() + r * sin( curr_angle); 926 return_points.push_back( round_down<T>((point_data<double>(x,y)))); 927 curr_angle+=delta_angle; 928 } 929 return_points.push_back(round_down<T>(end)); 930 return return_points.size(); 931 } 932 933 }// close namespace 934 }// close name space 935 936 #include "detail/scan_arbitrary.hpp" 937 938 namespace boost { namespace polygon { 939 //ConnectivityExtraction computes the graph of connectivity between rectangle, polygon and 940 //polygon set graph nodes where an edge is created whenever the geometry in two nodes overlap 941 template <typename coordinate_type> 942 class connectivity_extraction{ 943 private: 944 typedef arbitrary_connectivity_extraction<coordinate_type, int> ce; 945 ce ce_; 946 unsigned int nodeCount_; 947 public: connectivity_extraction()948 inline connectivity_extraction() : ce_(), nodeCount_(0) {} connectivity_extraction(const connectivity_extraction & that)949 inline connectivity_extraction(const connectivity_extraction& that) : ce_(that.ce_), 950 nodeCount_(that.nodeCount_) {} operator =(const connectivity_extraction & that)951 inline connectivity_extraction& operator=(const connectivity_extraction& that) { 952 ce_ = that.ce_; 953 nodeCount_ = that.nodeCount_; {} 954 return *this; 955 } 956 957 //insert a polygon set graph node, the value returned is the id of the graph node insert(const polygon_set_data<coordinate_type> & ps)958 inline unsigned int insert(const polygon_set_data<coordinate_type>& ps) { 959 ps.clean(); 960 ce_.populateTouchSetData(ps.begin(), ps.end(), nodeCount_); 961 return nodeCount_++; 962 } 963 template <class GeoObjT> insert(const GeoObjT & geoObj)964 inline unsigned int insert(const GeoObjT& geoObj) { 965 polygon_set_data<coordinate_type> ps; 966 ps.insert(geoObj); 967 return insert(ps); 968 } 969 970 //extract connectivity and store the edges in the graph 971 //graph must be indexable by graph node id and the indexed value must be a std::set of 972 //graph node id 973 template <class GraphT> extract(GraphT & graph)974 inline void extract(GraphT& graph) { 975 ce_.execute(graph); 976 } 977 }; 978 979 template <typename T> 980 polygon_set_data<T>& interact(const polygon_set_data<T> & that)981 polygon_set_data<T>::interact(const polygon_set_data<T>& that) { 982 connectivity_extraction<coordinate_type> ce; 983 std::vector<polygon_with_holes_data<T> > polys; 984 get(polys); 985 clear(); 986 for(std::size_t i = 0; i < polys.size(); ++i) { 987 ce.insert(polys[i]); 988 } 989 int id = ce.insert(that); 990 std::vector<std::set<int> > graph(id+1); 991 ce.extract(graph); 992 for(std::set<int>::iterator itr = graph[id].begin(); 993 itr != graph[id].end(); ++itr) { 994 insert(polys[*itr]); 995 } 996 return *this; 997 } 998 } 999 } 1000 1001 #include "polygon_set_traits.hpp" 1002 #include "detail/polygon_set_view.hpp" 1003 1004 #include "polygon_set_concept.hpp" 1005 #include "detail/minkowski.hpp" 1006 #endif 1007