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