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
15namespace 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>
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>
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
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>
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
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
67 inline ~polygon_set_data() {}
68
69 // assignement operator
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>
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>
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
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>
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>
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>
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
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>
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>
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>
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>
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>
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>
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>
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>
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
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
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>
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(edge: elem);
225 }
226 ++vertex0;
227 ++vertex1;
228 if (vertex1 == end_vertex) {
229 vertex1 = begin_vertex;
230 }
231 }
232 }
233
234 template <typename output_container>
235 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>
242 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>
258 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
277 inline bool operator!=(const polygon_set_data& p) const {
278 return !((*this) == p);
279 }
280
281 // get iterator to begin vertex data
282 inline iterator_type begin() const {
283 return data_.begin();
284 }
285
286 // get iterator to end vertex data
287 inline iterator_type end() const {
288 return data_.end();
289 }
290
291 const value_type& value() const {
292 return data_;
293 }
294
295 // clear the contents of the polygon_set_data
296 inline void clear() { data_.clear(); dirty_ = unsorted_ = false; }
297
298 // find out if Polygon set is empty
299 inline bool empty() const { return data_.empty(); }
300
301 // get the Polygon set size in vertices
302 inline std::size_t size() const { clean(); return data_.size(); }
303
304 // get the current Polygon set capacity in vertices
305 inline std::size_t capacity() const { return data_.capacity(); }
306
307 // reserve size of polygon set in vertices
308 inline void reserve(std::size_t size) { return data_.reserve(size); }
309
310 // find out if Polygon set is sorted
311 inline bool sorted() const { return !unsorted_; }
312
313 // find out if Polygon set is clean
314 inline bool dirty() const { return dirty_; }
315
316 void clean() const;
317
318 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>
326 void set(input_iterator_type input_begin, input_iterator_type input_end) {
327 clear();
328 reserve(size: std::distance(input_begin,input_end));
329 insert(input_begin, input_end);
330 dirty_ = true;
331 unsorted_ = true;
332 }
333
334 void set(const value_type& value) {
335 data_ = value;
336 dirty_ = true;
337 unsorted_ = true;
338 }
339
340 template <typename rectangle_type>
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&
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&
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&
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>
402 inline polygon_set_data& scale(polygon_set_data&,
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
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(x: 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(value: prev_pt.x() + (long double)dnx * (long double)multiplier);
430 pt2.x(value: current_pt.x() + (long double)dnx * (long double)multiplier);
431 pt1.y(value: prev_pt.y() + (long double)dny * (long double)multiplier);
432 pt2.y(value: current_pt.y() + (long double)dny * (long double)multiplier);
433 }
434
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(value: (long double)(prev_pt.x()));
440 he1.first.y(value: (long double)(prev_pt.y()));
441 he1.second.x(value: (long double)(current_pt.x()));
442 he1.second.y(value: (long double)(current_pt.y()));
443 he2.first.x(value: (long double)(current_pt.x()));
444 he2.first.y(value: (long double)(current_pt.y()));
445 he2.second.x(value: (long double)(next_pt.x()));
446 he2.second.y(value: (long double)(next_pt.y()));
447 compute_offset_edge(pt1&: he1.first, pt2&: he1.second, prev_pt, current_pt, distance, multiplier);
448 compute_offset_edge(pt1&: he2.first, pt2&: he2.second, prev_pt: current_pt, 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(point1: bisectorpt, point2: orig_pt) < distance/2) {
455 if(!pack::compute_lazy_intersection(intersection&: rpt, he1, he2, projected: true, round_closest: false)) {
456 rpt = he1.second; //colinear offset edges use shared point
457 }
458 } else {
459 if(!pack::compute_lazy_intersection(intersection&: rpt, he1, he2: std::pair<point_data<long double>, point_data<long double> >(orig_pt, bisectorpt), projected: true, round_closest: false)) {
460 rpt = he1.second; //colinear offset edges use shared point
461 }
462 }
463 pt.x((coordinate_type)(std::floor(x: rpt.x()+0.5)));
464 pt.y((coordinate_type)(std::floor(x: rpt.y()+0.5)));
465 }
466
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(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(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(pt&: poly[0], prev_pt, current_pt, next_pt, distance, multiplier);
484 poly.back() = poly.front();
485 }
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(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(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(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&
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(poly&: (*itr).self_.coords_, distance: (coordinate_type)distance, multiplier: (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(poly&: (*itrh).coords_, distance: (coordinate_type)distance, multiplier: (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&
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(poly&: (*itr).self_.coords_, distance: (coordinate_type)distance, multiplier: (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(poly&: (*itrh).coords_, distance: (coordinate_type)distance, multiplier: (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&
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&
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) {
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&
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) {
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(x: 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
733 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
756 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>
783 void get_dispatch(output_container& output, polygon_concept tag) const {
784 get_fracture(output, true, tag);
785 }
786 template <typename output_container>
787 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>
791 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>
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( x: 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( x: 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>
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(y: start.y()-center.y(), x: start.x()-center.x());
898 double pe = atan2(y: end.y()-center.y(), x: 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(x: ps);
914 y = center.y() + r * sin(x: 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( x: curr_angle);
925 double y = center.y() + r * sin( x: 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
938namespace 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:
948 inline connectivity_extraction() : ce_(), nodeCount_(0) {}
949 inline connectivity_extraction(const connectivity_extraction& that) : ce_(that.ce_),
950 nodeCount_(that.nodeCount_) {}
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
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>
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>
974 inline void extract(GraphT& graph) {
975 ce_.execute(graph);
976 }
977 };
978
979 template <typename T>
980 polygon_set_data<T>&
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

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