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