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> |
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 | |
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 { |
943 | private: |
944 | typedef arbitrary_connectivity_extraction<coordinate_type, int> ; |
945 | ce ; |
946 | unsigned int ; |
947 | public: |
948 | inline () : ce_(), nodeCount_(0) {} |
949 | inline (const connectivity_extraction& that) : ce_(that.ce_), |
950 | nodeCount_(that.nodeCount_) {} |
951 | inline connectivity_extraction& (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 (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 (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 (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 | |