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_TRAITS_HPP
9	#define BOOST_POLYGON_POLYGON_TRAITS_HPP
10	namespace boost { namespace polygon{
11
12	template <typename T, typename enable = gtl_yes>
13	struct polygon_90_traits {
14	typedef typename T::coordinate_type coordinate_type;
15	typedef typename T::compact_iterator_type compact_iterator_type;
16
17	// Get the begin iterator
18	static inline compact_iterator_type begin_compact(const T& t) {
19	return t.begin_compact();
20	}
21
22	// Get the end iterator
23	static inline compact_iterator_type end_compact(const T& t) {
24	return t.end_compact();
25	}
26
27	// Get the number of sides of the polygon
28	static inline std::size_t size(const T& t) {
29	return t.size();
30	}
31
32	// Get the winding direction of the polygon
33	static inline winding_direction winding(const T&) {
34	return unknown_winding;
35	}
36	};
37
38	template <typename T>
39	struct polygon_traits_general {
40	typedef typename T::coordinate_type coordinate_type;
41	typedef typename T::iterator_type iterator_type;
42	typedef typename T::point_type point_type;
43
44	// Get the begin iterator
45	static inline iterator_type begin_points(const T& t) {
46	return t.begin();
47	}
48
49	// Get the end iterator
50	static inline iterator_type end_points(const T& t) {
51	return t.end();
52	}
53
54	// Get the number of sides of the polygon
55	static inline std::size_t size(const T& t) {
56	return t.size();
57	}
58
59	// Get the winding direction of the polygon
60	static inline winding_direction winding(const T&) {
61	return unknown_winding;
62	}
63	};
64
65	template <typename T>
66	struct polygon_traits_90 {
67	typedef typename polygon_90_traits<T>::coordinate_type coordinate_type;
68	typedef iterator_compact_to_points<typename polygon_90_traits<T>::compact_iterator_type, point_data<coordinate_type> > iterator_type;
69	typedef point_data<coordinate_type> point_type;
70
71	// Get the begin iterator
72	static inline iterator_type begin_points(const T& t) {
73	return iterator_type(polygon_90_traits<T>::begin_compact(t),
74	polygon_90_traits<T>::end_compact(t));
75	}
76
77	// Get the end iterator
78	static inline iterator_type end_points(const T& t) {
79	return iterator_type(polygon_90_traits<T>::end_compact(t),
80	polygon_90_traits<T>::end_compact(t));
81	}
82
83	// Get the number of sides of the polygon
84	static inline std::size_t size(const T& t) {
85	return polygon_90_traits<T>::size(t);
86	}
87
88	// Get the winding direction of the polygon
89	static inline winding_direction winding(const T& t) {
90	return polygon_90_traits<T>::winding(t);
91	}
92	};
93
94	#ifndef BOOST_VERY_LITTLE_SFINAE
95
96	template <typename T, typename enable = gtl_yes>
97	struct polygon_traits {};
98
99	template <typename T>
100	struct polygon_traits<T,
101	typename gtl_or_4<
102	typename gtl_same_type<typename geometry_concept<T>::type, polygon_concept>::type,
103	typename gtl_same_type<typename geometry_concept<T>::type, polygon_45_concept>::type,
104	typename gtl_same_type<typename geometry_concept<T>::type, polygon_with_holes_concept>::type,
105	typename gtl_same_type<typename geometry_concept<T>::type, polygon_45_with_holes_concept>::type
106	>::type> : public polygon_traits_general<T> {};
107
108	template <typename T>
109	struct polygon_traits< T,
110	typename gtl_or<
111	typename gtl_same_type<typename geometry_concept<T>::type, polygon_90_concept>::type,
112	typename gtl_same_type<typename geometry_concept<T>::type, polygon_90_with_holes_concept>::type
113	>::type > : public polygon_traits_90<T> {};
114
115	#else
116
117	template <typename T, typename T_IF, typename T_ELSE>
118	struct gtl_ifelse {};
119	template <typename T_IF, typename T_ELSE>
120	struct gtl_ifelse<gtl_no, T_IF, T_ELSE> {
121	typedef T_ELSE type;
122	};
123	template <typename T_IF, typename T_ELSE>
124	struct gtl_ifelse<gtl_yes, T_IF, T_ELSE> {
125	typedef T_IF type;
126	};
127
128	template <typename T, typename enable = gtl_yes>
129	struct polygon_traits {};
130
131	template <typename T>
132	struct polygon_traits<T, typename gtl_or<typename gtl_or_4<
133	typename gtl_same_type<typename geometry_concept<T>::type, polygon_concept>::type,
134	typename gtl_same_type<typename geometry_concept<T>::type, polygon_45_concept>::type,
135	typename gtl_same_type<typename geometry_concept<T>::type, polygon_with_holes_concept>::type,
136	typename gtl_same_type<typename geometry_concept<T>::type, polygon_45_with_holes_concept>::type
137	>::type, typename gtl_or<
138	typename gtl_same_type<typename geometry_concept<T>::type, polygon_90_concept>::type,
139	typename gtl_same_type<typename geometry_concept<T>::type, polygon_90_with_holes_concept>::type
140	>::type>::type > : public gtl_ifelse<typename gtl_or<
141	typename gtl_same_type<typename geometry_concept<T>::type, polygon_90_concept>::type,
142	typename gtl_same_type<typename geometry_concept<T>::type, polygon_90_with_holes_concept>::type >::type,
143	polygon_traits_90<T>,
144	polygon_traits_general<T> >::type {
145	};
146
147	#endif
148
149	template <typename T, typename enable = void>
150	struct polygon_with_holes_traits {
151	typedef typename T::iterator_holes_type iterator_holes_type;
152	typedef typename T::hole_type hole_type;
153
154	// Get the begin iterator
155	static inline iterator_holes_type begin_holes(const T& t) {
156	return t.begin_holes();
157	}
158
159	// Get the end iterator
160	static inline iterator_holes_type end_holes(const T& t) {
161	return t.end_holes();
162	}
163
164	// Get the number of holes
165	static inline std::size_t size_holes(const T& t) {
166	return t.size_holes();
167	}
168	};
169
170	template <typename T, typename enable = void>
171	struct polygon_90_mutable_traits {
172
173	// Set the data of a polygon with the unique coordinates in an iterator, starting with an x
174	template <typename iT>
175	static inline T& set_compact(T& t, iT input_begin, iT input_end) {
176	t.set_compact(input_begin, input_end);
177	return t;
178	}
179
180	};
181
182	template <typename T, typename enable = void>
183	struct polygon_mutable_traits {
184
185	// Set the data of a polygon with the unique coordinates in an iterator, starting with an x
186	template <typename iT>
187	static inline T& set_points(T& t, iT input_begin, iT input_end) {
188	t.set(input_begin, input_end);
189	return t;
190	}
191
192	};
193
194	template <typename T, typename enable = void>
195	struct polygon_with_holes_mutable_traits {
196
197	// Set the data of a polygon with the unique coordinates in an iterator, starting with an x
198	template <typename iT>
199	static inline T& set_holes(T& t, iT inputBegin, iT inputEnd) {
200	t.set_holes(inputBegin, inputEnd);
201	return t;
202	}
203
204	};
205	}
206	}
207	#include "isotropy.hpp"
208
209	//point
210	#include "point_data.hpp"
211	#include "point_traits.hpp"
212	#include "point_concept.hpp"
213
214	//interval
215	#include "interval_data.hpp"
216	#include "interval_traits.hpp"
217	#include "interval_concept.hpp"
218
219	//rectangle
220	#include "rectangle_data.hpp"
221	#include "rectangle_traits.hpp"
222	#include "rectangle_concept.hpp"
223
224	//algorithms needed by polygon types
225	#include "detail/iterator_points_to_compact.hpp"
226	#include "detail/iterator_compact_to_points.hpp"
227
228	//polygons
229	#include "polygon_45_data.hpp"
230	#include "polygon_data.hpp"
231	#include "polygon_90_data.hpp"
232	#include "polygon_90_with_holes_data.hpp"
233	#include "polygon_45_with_holes_data.hpp"
234	#include "polygon_with_holes_data.hpp"
235
236	namespace boost { namespace polygon{
237	struct polygon_concept {};
238	struct polygon_with_holes_concept {};
239	struct polygon_45_concept {};
240	struct polygon_45_with_holes_concept {};
241	struct polygon_90_concept {};
242	struct polygon_90_with_holes_concept {};
243
244
245	template <typename T>
246	struct is_polygon_90_type {
247	typedef typename geometry_concept<T>::type GC;
248	typedef typename gtl_same_type<polygon_90_concept, GC>::type type;
249	};
250
251	template <typename T>
252	struct is_polygon_45_type {
253	typedef typename geometry_concept<T>::type GC;
254	typedef typename gtl_or<typename is_polygon_90_type<T>::type,
255	typename gtl_same_type<polygon_45_concept, GC>::type>::type type;
256	};
257
258	template <typename T>
259	struct is_polygon_type {
260	typedef typename geometry_concept<T>::type GC;
261	typedef typename gtl_or<typename is_polygon_45_type<T>::type,
262	typename gtl_same_type<polygon_concept, GC>::type>::type type;
263	};
264
265	template <typename T>
266	struct is_polygon_90_with_holes_type {
267	typedef typename geometry_concept<T>::type GC;
268	typedef typename gtl_or<typename is_polygon_90_type<T>::type,
269	typename gtl_same_type<polygon_90_with_holes_concept, GC>::type>::type type;
270	};
271
272	template <typename T>
273	struct is_polygon_45_with_holes_type {
274	typedef typename geometry_concept<T>::type GC;
275	typedef typename gtl_or_3<typename is_polygon_90_with_holes_type<T>::type,
276	typename is_polygon_45_type<T>::type,
277	typename gtl_same_type<polygon_45_with_holes_concept, GC>::type>::type type;
278	};
279
280	template <typename T>
281	struct is_polygon_with_holes_type {
282	typedef typename geometry_concept<T>::type GC;
283	typedef typename gtl_or_3<typename is_polygon_45_with_holes_type<T>::type,
284	typename is_polygon_type<T>::type,
285	typename gtl_same_type<polygon_with_holes_concept, GC>::type>::type type;
286	};
287
288	template <typename T>
289	struct is_mutable_polygon_90_type {
290	typedef typename geometry_concept<T>::type GC;
291	typedef typename gtl_same_type<polygon_90_concept, GC>::type type;
292	};
293
294	template <typename T>
295	struct is_mutable_polygon_45_type {
296	typedef typename geometry_concept<T>::type GC;
297	typedef typename gtl_same_type<polygon_45_concept, GC>::type type;
298	};
299
300	template <typename T>
301	struct is_mutable_polygon_type {
302	typedef typename geometry_concept<T>::type GC;
303	typedef typename gtl_same_type<polygon_concept, GC>::type type;
304	};
305
306	template <typename T>
307	struct is_mutable_polygon_90_with_holes_type {
308	typedef typename geometry_concept<T>::type GC;
309	typedef typename gtl_same_type<polygon_90_with_holes_concept, GC>::type type;
310	};
311
312	template <typename T>
313	struct is_mutable_polygon_45_with_holes_type {
314	typedef typename geometry_concept<T>::type GC;
315	typedef typename gtl_same_type<polygon_45_with_holes_concept, GC>::type type;
316	};
317
318	template <typename T>
319	struct is_mutable_polygon_with_holes_type {
320	typedef typename geometry_concept<T>::type GC;
321	typedef typename gtl_same_type<polygon_with_holes_concept, GC>::type type;
322	};
323
324	template <typename T>
325	struct is_any_mutable_polygon_with_holes_type {
326	typedef typename gtl_or_3<typename is_mutable_polygon_90_with_holes_type<T>::type,
327	typename is_mutable_polygon_45_with_holes_type<T>::type,
328	typename is_mutable_polygon_with_holes_type<T>::type>::type type;
329	};
330	template <typename T>
331	struct is_any_mutable_polygon_without_holes_type {
332	typedef typename gtl_or_3<
333	typename is_mutable_polygon_90_type<T>::type,
334	typename is_mutable_polygon_45_type<T>::type,
335	typename is_mutable_polygon_type<T>::type>::type type; };
336
337	template <typename T>
338	struct is_any_mutable_polygon_type {
339	typedef typename gtl_or<typename is_any_mutable_polygon_with_holes_type<T>::type,
340	typename is_any_mutable_polygon_without_holes_type<T>::type>::type type;
341	};
342
343	template <typename T>
344	struct polygon_from_polygon_with_holes_type {};
345	template <>
346	struct polygon_from_polygon_with_holes_type<polygon_with_holes_concept> { typedef polygon_concept type; };
347	template <>
348	struct polygon_from_polygon_with_holes_type<polygon_45_with_holes_concept> { typedef polygon_45_concept type; };
349	template <>
350	struct polygon_from_polygon_with_holes_type<polygon_90_with_holes_concept> { typedef polygon_90_concept type; };
351
352	template <>
353	struct geometry_domain<polygon_45_concept> { typedef forty_five_domain type; };
354	template <>
355	struct geometry_domain<polygon_45_with_holes_concept> { typedef forty_five_domain type; };
356	template <>
357	struct geometry_domain<polygon_90_concept> { typedef manhattan_domain type; };
358	template <>
359	struct geometry_domain<polygon_90_with_holes_concept> { typedef manhattan_domain type; };
360
361	template <typename domain_type, typename coordinate_type>
362	struct distance_type_by_domain { typedef typename coordinate_traits<coordinate_type>::coordinate_distance type; };
363	template <typename coordinate_type>
364	struct distance_type_by_domain<manhattan_domain, coordinate_type> {
365	typedef typename coordinate_traits<coordinate_type>::coordinate_difference type; };
366
367	// \brief Sets the boundary of the polygon to the points in the iterator range
368	// \tparam T A type that models polygon_concept
369	// \tparam iT Iterator type over objects that model point_concept
370	// \param t The polygon to set
371	// \param begin_points The start of the range of points
372	// \param end_points The end of the range of points
373
374	/// \relatesalso polygon_concept
375	template <typename T, typename iT>
376	typename enable_if <typename is_any_mutable_polygon_type<T>::type, T>::type &
377	set_points(T& t, iT begin_points, iT end_points) {
378	polygon_mutable_traits<T>::set_points(t, begin_points, end_points);
379	return t;
380	}
381
382	// \brief Sets the boundary of the polygon to the non-redundant coordinates in the iterator range
383	// \tparam T A type that models polygon_90_concept
384	// \tparam iT Iterator type over objects that model coordinate_concept
385	// \param t The polygon to set
386	// \param begin_compact_coordinates The start of the range of coordinates
387	// \param end_compact_coordinates The end of the range of coordinates
388
389	/// \relatesalso polygon_90_concept
390	template <typename T, typename iT>
391	typename enable_if <typename gtl_or<
392	typename is_mutable_polygon_90_type<T>::type,
393	typename is_mutable_polygon_90_with_holes_type<T>::type>::type, T>::type &
394	set_compact(T& t, iT begin_compact_coordinates, iT end_compact_coordinates) {
395	polygon_90_mutable_traits<T>::set_compact(t, begin_compact_coordinates, end_compact_coordinates);
396	return t;
397	}
398
399	/// \relatesalso polygon_with_holes_concept
400	template <typename T, typename iT>
401	typename enable_if< typename gtl_and <
402	typename is_any_mutable_polygon_with_holes_type<T>::type,
403	typename gtl_different_type<typename geometry_domain<typename geometry_concept<T>::type>::type,
404	manhattan_domain>::type>::type,
405	T>::type &
406	set_compact(T& t, iT begin_compact_coordinates, iT end_compact_coordinates) {
407	iterator_compact_to_points<iT, point_data<typename polygon_traits<T>::coordinate_type> >
408	itrb(begin_compact_coordinates, end_compact_coordinates),
409	itre(end_compact_coordinates, end_compact_coordinates);
410	return set_points(t, itrb, itre);
411	}
412
413	/// \relatesalso polygon_with_holes_concept
414	template <typename T, typename iT>
415	typename enable_if <typename is_any_mutable_polygon_with_holes_type<T>::type, T>::type &
416	set_holes(T& t, iT begin_holes, iT end_holes) {
417	polygon_with_holes_mutable_traits<T>::set_holes(t, begin_holes, end_holes);
418	return t;
419	}
420
421	/// \relatesalso polygon_90_concept
422	template <typename T>
423	typename polygon_90_traits<T>::compact_iterator_type
424	begin_compact(const T& polygon,
425	typename enable_if<
426	typename gtl_and <typename is_polygon_with_holes_type<T>::type,
427	typename gtl_same_type<typename geometry_domain<typename geometry_concept<T>::type>::type,
428	manhattan_domain>::type>::type>::type * = 0
429	) {
430	return polygon_90_traits<T>::begin_compact(polygon);
431	}
432
433	/// \relatesalso polygon_90_concept
434	template <typename T>
435	typename polygon_90_traits<T>::compact_iterator_type
436	end_compact(const T& polygon,
437	typename enable_if<
438	typename gtl_and <typename is_polygon_with_holes_type<T>::type,
439	typename gtl_same_type<typename geometry_domain<typename geometry_concept<T>::type>::type,
440	manhattan_domain>::type>::type>::type * = 0
441	) {
442	return polygon_90_traits<T>::end_compact(polygon);
443	}
444
445	/// \relatesalso polygon_concept
446	template <typename T>
447	typename enable_if < typename gtl_if<
448	typename is_polygon_with_holes_type<T>::type>::type,
449	typename polygon_traits<T>::iterator_type>::type
450	begin_points(const T& polygon) {
451	return polygon_traits<T>::begin_points(polygon);
452	}
453
454	/// \relatesalso polygon_concept
455	template <typename T>
456	typename enable_if < typename gtl_if<
457	typename is_polygon_with_holes_type<T>::type>::type,
458	typename polygon_traits<T>::iterator_type>::type
459	end_points(const T& polygon) {
460	return polygon_traits<T>::end_points(polygon);
461	}
462
463	/// \relatesalso polygon_concept
464	template <typename T>
465	typename enable_if <typename is_polygon_with_holes_type<T>::type,
466	std::size_t>::type
467	size(const T& polygon) {
468	return polygon_traits<T>::size(polygon);
469	}
470
471	/// \relatesalso polygon_with_holes_concept
472	template <typename T>
473	typename enable_if < typename gtl_if<
474	typename is_polygon_with_holes_type<T>::type>::type,
475	typename polygon_with_holes_traits<T>::iterator_holes_type>::type
476	begin_holes(const T& polygon) {
477	return polygon_with_holes_traits<T>::begin_holes(polygon);
478	}
479
480	/// \relatesalso polygon_with_holes_concept
481	template <typename T>
482	typename enable_if < typename gtl_if<
483	typename is_polygon_with_holes_type<T>::type>::type,
484	typename polygon_with_holes_traits<T>::iterator_holes_type>::type
485	end_holes(const T& polygon) {
486	return polygon_with_holes_traits<T>::end_holes(polygon);
487	}
488
489	/// \relatesalso polygon_with_holes_concept
490	template <typename T>
491	typename enable_if <typename is_polygon_with_holes_type<T>::type,
492	std::size_t>::type
493	size_holes(const T& polygon) {
494	return polygon_with_holes_traits<T>::size_holes(polygon);
495	}
496
497	// \relatesalso polygon_concept
498	template <typename T1, typename T2>
499	typename enable_if<
500	typename gtl_and< typename is_mutable_polygon_type<T1>::type,
501	typename is_polygon_type<T2>::type>::type, T1>::type &
502	assign(T1& lvalue, const T2& rvalue) {
503	polygon_mutable_traits<T1>::set_points(lvalue, polygon_traits<T2>::begin_points(rvalue),
504	polygon_traits<T2>::end_points(rvalue));
505	return lvalue;
506	}
507
508	// \relatesalso polygon_with_holes_concept
509	template <typename T1, typename T2>
510	typename enable_if<
511	typename gtl_and< typename is_mutable_polygon_with_holes_type<T1>::type,
512	typename is_polygon_with_holes_type<T2>::type>::type, T1>::type &
513	assign(T1& lvalue, const T2& rvalue) {
514	polygon_mutable_traits<T1>::set_points(lvalue, polygon_traits<T2>::begin_points(rvalue),
515	polygon_traits<T2>::end_points(rvalue));
516	polygon_with_holes_mutable_traits<T1>::set_holes(lvalue, polygon_with_holes_traits<T2>::begin_holes(rvalue),
517	polygon_with_holes_traits<T2>::end_holes(rvalue));
518	return lvalue;
519	}
520
521	// \relatesalso polygon_45_concept
522	template <typename T1, typename T2>
523	typename enable_if< typename gtl_and< typename is_mutable_polygon_45_type<T1>::type, typename is_polygon_45_type<T2>::type>::type, T1>::type &
524	assign(T1& lvalue, const T2& rvalue) {
525	polygon_mutable_traits<T1>::set_points(lvalue, polygon_traits<T2>::begin_points(rvalue),
526	polygon_traits<T2>::end_points(rvalue));
527	return lvalue;
528	}
529
530	// \relatesalso polygon_45_with_holes_concept
531	template <typename T1, typename T2>
532	typename enable_if<
533	typename gtl_and< typename is_mutable_polygon_45_with_holes_type<T1>::type,
534	typename is_polygon_45_with_holes_type<T2>::type>::type, T1>::type &
535	assign(T1& lvalue, const T2& rvalue) {
536	polygon_mutable_traits<T1>::set_points(lvalue, polygon_traits<T2>::begin_points(rvalue),
537	polygon_traits<T2>::end_points(rvalue));
538	polygon_with_holes_mutable_traits<T1>::set_holes(lvalue, polygon_with_holes_traits<T2>::begin_holes(rvalue),
539	polygon_with_holes_traits<T2>::end_holes(rvalue));
540	return lvalue;
541	}
542
543	// \relatesalso polygon_90_concept
544	template <typename T1, typename T2>
545	typename enable_if<
546	typename gtl_and< typename is_mutable_polygon_90_type<T1>::type,
547	typename is_polygon_90_type<T2>::type>::type, T1>::type &
548	assign(T1& lvalue, const T2& rvalue) {
549	polygon_90_mutable_traits<T1>::set_compact(lvalue, polygon_90_traits<T2>::begin_compact(rvalue),
550	polygon_90_traits<T2>::end_compact(rvalue));
551	return lvalue;
552	}
553
554	// \relatesalso polygon_90_with_holes_concept
555	template <typename T1, typename T2>
556	typename enable_if<
557	typename gtl_and< typename is_mutable_polygon_90_with_holes_type<T1>::type,
558	typename is_polygon_90_with_holes_type<T2>::type>::type, T1>::type &
559	assign(T1& lvalue, const T2& rvalue) {
560	polygon_90_mutable_traits<T1>::set_compact(lvalue, polygon_90_traits<T2>::begin_compact(rvalue),
561	polygon_90_traits<T2>::end_compact(rvalue));
562	polygon_with_holes_mutable_traits<T1>::set_holes(lvalue, polygon_with_holes_traits<T2>::begin_holes(rvalue),
563	polygon_with_holes_traits<T2>::end_holes(rvalue));
564	return lvalue;
565	}
566
567	// \relatesalso polygon_90_concept
568	template <typename T1, typename T2>
569	typename enable_if<
570	typename gtl_and< typename is_any_mutable_polygon_type<T1>::type,
571	typename is_rectangle_concept<typename geometry_concept<T2>::type>::type>::type, T1>::type &
572	assign(T1& polygon, const T2& rect) {
573	typedef point_data<typename polygon_traits<T1>::coordinate_type> PT;
574	PT points[4] = {PT(xl(rect), yl(rect)), PT(xh(rect), yl(rect)), PT(xh(rect), yh(rect)), PT(xl(rect), yh(rect))};
575	set_points(polygon, points, points+4);
576	return polygon;
577	}
578
579	/// \relatesalso polygon_90_concept
580	template <typename polygon_type, typename point_type>
581	typename enable_if< typename gtl_and< typename is_mutable_polygon_90_type<polygon_type>::type,
582	typename is_point_concept<typename geometry_concept<point_type>::type>::type>::type,
583	polygon_type>::type &
584	convolve(polygon_type& polygon, const point_type& point) {
585	std::vector<typename polygon_90_traits<polygon_type>::coordinate_type> coords;
586	coords.reserve(size(polygon));
587	bool pingpong = true;
588	for(typename polygon_90_traits<polygon_type>::compact_iterator_type iter = begin_compact(polygon);
589	iter != end_compact(polygon); ++iter) {
590	coords.push_back((*iter) + (pingpong ? x(point) : y(point)));
591	pingpong = !pingpong;
592	}
593	polygon_90_mutable_traits<polygon_type>::set_compact(polygon, coords.begin(), coords.end());
594	return polygon;
595	}
596
597	/// \relatesalso polygon_concept
598	template <typename polygon_type, typename point_type>
599	typename enable_if< typename gtl_and< typename gtl_or<
600	typename is_mutable_polygon_45_type<polygon_type>::type,
601	typename is_mutable_polygon_type<polygon_type>::type>::type,
602	typename is_point_concept<typename geometry_concept<point_type>::type>::type>::type,
603	polygon_type>::type &
604	convolve(polygon_type& polygon, const point_type& point) {
605	std::vector<typename std::iterator_traits<typename polygon_traits<polygon_type>::iterator_type>::value_type> points;
606	points.reserve(size(polygon));
607	for(typename polygon_traits<polygon_type>::iterator_type iter = begin_points(polygon);
608	iter != end_points(polygon); ++iter) {
609	points.push_back(*iter);
610	convolve(points.back(), point);
611	}
612	polygon_mutable_traits<polygon_type>::set_points(polygon, points.begin(), points.end());
613	return polygon;
614	}
615
616	/// \relatesalso polygon_with_holes_concept
617	template <typename polygon_type, typename point_type>
618	typename enable_if<
619	typename gtl_and< typename is_any_mutable_polygon_with_holes_type<polygon_type>::type,
620	typename is_point_concept<typename geometry_concept<point_type>::type>::type>::type,
621	polygon_type>::type &
622	convolve(polygon_type& polygon, const point_type& point) {
623	typedef typename polygon_with_holes_traits<polygon_type>::hole_type hole_type;
624	hole_type h;
625	set_points(h, begin_points(polygon), end_points(polygon));
626	convolve(h, point);
627	std::vector<hole_type> holes;
628	holes.reserve(size_holes(polygon));
629	for(typename polygon_with_holes_traits<polygon_type>::iterator_holes_type itr = begin_holes(polygon);
630	itr != end_holes(polygon); ++itr) {
631	holes.push_back(*itr);
632	convolve(holes.back(), point);
633	}
634	assign(polygon, h);
635	set_holes(polygon, holes.begin(), holes.end());
636	return polygon;
637	}
638
639	/// \relatesalso polygon_concept
640	template <typename T>
641	typename enable_if< typename is_any_mutable_polygon_type<T>::type, T>::type &
642	move(T& polygon, orientation_2d orient, typename polygon_traits<T>::coordinate_type displacement) {
643	typedef typename polygon_traits<T>::coordinate_type Unit;
644	if(orient == HORIZONTAL) return convolve(polygon, point_data<Unit>(displacement, Unit(0)));
645	return convolve(polygon, point_data<Unit>(Unit(0), displacement));
646	}
647
648	/// \relatesalso polygon_concept
649	/// \brief Applies a transformation to the polygon.
650	/// \tparam polygon_type A type that models polygon_concept
651	/// \tparam transform_type A type that may be either axis_transformation or transformation or that overloads point_concept::transform
652	/// \param polygon The polygon to transform
653	/// \param tr The transformation to apply
654	template <typename polygon_type, typename transform_type>
655	typename enable_if< typename is_any_mutable_polygon_without_holes_type<polygon_type>::type, polygon_type>::type &
656	transform(polygon_type& polygon, const transform_type& tr) {
657	std::vector<typename std::iterator_traits<typename polygon_traits<polygon_type>::iterator_type>::value_type> points;
658	points.reserve(size(polygon));
659	for(typename polygon_traits<polygon_type>::iterator_type iter = begin_points(polygon);
660	iter != end_points(polygon); ++iter) {
661	points.push_back(*iter);
662	transform(points.back(), tr);
663	}
664	polygon_mutable_traits<polygon_type>::set_points(polygon, points.begin(), points.end());
665	return polygon;
666	}
667
668	/// \relatesalso polygon_with_holes_concept
669	template <typename T, typename transform_type>
670	typename enable_if< typename is_any_mutable_polygon_with_holes_type<T>::type, T>::type &
671	transform(T& polygon, const transform_type& tr) {
672	typedef typename polygon_with_holes_traits<T>::hole_type hole_type;
673	hole_type h;
674	set_points(h, begin_points(polygon), end_points(polygon));
675	transform(h, tr);
676	std::vector<hole_type> holes;
677	holes.reserve(size_holes(polygon));
678	for(typename polygon_with_holes_traits<T>::iterator_holes_type itr = begin_holes(polygon);
679	itr != end_holes(polygon); ++itr) {
680	holes.push_back(*itr);
681	transform(holes.back(), tr);
682	}
683	assign(polygon, h);
684	set_holes(polygon, holes.begin(), holes.end());
685	return polygon;
686	}
687
688	template <typename polygon_type>
689	typename enable_if< typename is_any_mutable_polygon_without_holes_type<polygon_type>::type, polygon_type>::type &
690	scale_up(polygon_type& polygon, typename coordinate_traits<typename polygon_traits<polygon_type>::coordinate_type>::unsigned_area_type factor) {
691	std::vector<typename std::iterator_traits<typename polygon_traits<polygon_type>::iterator_type>::value_type> points;
692	points.reserve(size(polygon));
693	for(typename polygon_traits<polygon_type>::iterator_type iter = begin_points(polygon);
694	iter != end_points(polygon); ++iter) {
695	points.push_back(*iter);
696	scale_up(points.back(), factor);
697	}
698	polygon_mutable_traits<polygon_type>::set_points(polygon, points.begin(), points.end());
699	return polygon;
700	}
701
702	template <typename T>
703	typename enable_if< typename is_any_mutable_polygon_with_holes_type<T>::type, T>::type &
704	scale_up(T& polygon, typename coordinate_traits<typename polygon_traits<T>::coordinate_type>::unsigned_area_type factor) {
705	typedef typename polygon_with_holes_traits<T>::hole_type hole_type;
706	hole_type h;
707	set_points(h, begin_points(polygon), end_points(polygon));
708	scale_up(h, factor);
709	std::vector<hole_type> holes;
710	holes.reserve(size_holes(polygon));
711	for(typename polygon_with_holes_traits<T>::iterator_holes_type itr = begin_holes(polygon);
712	itr != end_holes(polygon); ++itr) {
713	holes.push_back(*itr);
714	scale_up(holes.back(), factor);
715	}
716	assign(polygon, h);
717	set_holes(polygon, holes.begin(), holes.end());
718	return polygon;
719	}
720
721	//scale non-45 down
722	template <typename polygon_type>
723	typename enable_if<
724	typename gtl_and< typename is_any_mutable_polygon_without_holes_type<polygon_type>::type,
725	typename gtl_not<typename gtl_same_type
726	< forty_five_domain,
727	typename geometry_domain<typename geometry_concept<polygon_type>::type>::type>::type>::type>::type,
728	polygon_type>::type &
729	scale_down(polygon_type& polygon, typename coordinate_traits<typename polygon_traits<polygon_type>::coordinate_type>::unsigned_area_type factor) {
730	std::vector<typename std::iterator_traits<typename polygon_traits<polygon_type>::iterator_type>::value_type> points;
731	points.reserve(size(polygon));
732	for(typename polygon_traits<polygon_type>::iterator_type iter = begin_points(polygon);
733	iter != end_points(polygon); ++iter) {
734	points.push_back(*iter);
735	scale_down(points.back(), factor);
736	}
737	polygon_mutable_traits<polygon_type>::set_points(polygon, points.begin(), points.end());
738	return polygon;
739	}
740
741	template <typename Unit>
742	Unit local_abs(Unit value) { return value < 0 ? (Unit)-value : value; }
743
744	template <typename Unit>
745	void snap_point_vector_to_45(std::vector<point_data<Unit> >& pts) {
746	typedef point_data<Unit> Point;
747	if(pts.size() < 3) { pts.clear(); return; }
748	typename std::vector<point_data<Unit> >::iterator endLocation = std::unique(pts.begin(), pts.end());
749	if(endLocation != pts.end()){
750	pts.resize(endLocation - pts.begin());
751	}
752	if(pts.back() == pts[0]) pts.pop_back();
753	//iterate over point triplets
754	int numPts = pts.size();
755	bool wrap_around = false;
756	for(int i = 0; i < numPts; ++i) {
757	Point& pt1 = pts[i];
758	Point& pt2 = pts[(i + 1) % numPts];
759	Point& pt3 = pts[(i + 2) % numPts];
760	//check if non-45 edge
761	Unit deltax = x(pt2) - x(pt1);
762	Unit deltay = y(pt2) - y(pt1);
763	if(deltax && deltay &&
764	local_abs(deltax) != local_abs(deltay)) {
765	//adjust the middle point
766	Unit ndx = x(pt3) - x(pt2);
767	Unit ndy = y(pt3) - y(pt2);
768	if(ndx && ndy) {
769	Unit diff = local_abs(local_abs(deltax) - local_abs(deltay));
770	Unit halfdiff = diff/2;
771	if((deltax > 0 && deltay > 0) ||
772	(deltax < 0 && deltay < 0)) {
773	//previous edge is rising slope
774	if(local_abs(deltax + halfdiff + (diff % 2)) ==
775	local_abs(deltay - halfdiff)) {
776	x(pt2, x(pt2) + halfdiff + (diff % 2));
777	y(pt2, y(pt2) - halfdiff);
778	} else if(local_abs(deltax - halfdiff - (diff % 2)) ==
779	local_abs(deltay + halfdiff)) {
780	x(pt2, x(pt2) - halfdiff - (diff % 2));
781	y(pt2, y(pt2) + halfdiff);
782	} else{
783	//std::cout << "fail1\n";
784	}
785	} else {
786	//previous edge is falling slope
787	if(local_abs(deltax + halfdiff + (diff % 2)) ==
788	local_abs(deltay + halfdiff)) {
789	x(pt2, x(pt2) + halfdiff + (diff % 2));
790	y(pt2, y(pt2) + halfdiff);
791	} else if(local_abs(deltax - halfdiff - (diff % 2)) ==
792	local_abs(deltay - halfdiff)) {
793	x(pt2, x(pt2) - halfdiff - (diff % 2));
794	y(pt2, y(pt2) - halfdiff);
795	} else {
796	//std::cout << "fail2\n";
797	}
798	}
799	if(i == numPts - 1 && (diff % 2)) {
800	//we have a wrap around effect
801	if(!wrap_around) {
802	wrap_around = true;
803	i = -1;
804	}
805	}
806	} else if(ndx) {
807	//next edge is horizontal
808	//find the x value for pt1 that would make the abs(deltax) == abs(deltay)
809	Unit newDeltaX = local_abs(deltay);
810	if(deltax < 0) newDeltaX *= -1;
811	x(pt2, x(pt1) + newDeltaX);
812	} else { //ndy
813	//next edge is vertical
814	//find the y value for pt1 that would make the abs(deltax) == abs(deltay)
815	Unit newDeltaY = local_abs(deltax);
816	if(deltay < 0) newDeltaY *= -1;
817	y(pt2, y(pt1) + newDeltaY);
818	}
819	}
820	}
821	}
822
823	template <typename polygon_type>
824	typename enable_if< typename is_any_mutable_polygon_without_holes_type<polygon_type>::type, polygon_type>::type &
825	snap_to_45(polygon_type& polygon) {
826	std::vector<typename std::iterator_traits<typename polygon_traits<polygon_type>::iterator_type>::value_type> points;
827	points.reserve(size(polygon));
828	for(typename polygon_traits<polygon_type>::iterator_type iter = begin_points(polygon);
829	iter != end_points(polygon); ++iter) {
830	points.push_back(*iter);
831	}
832	snap_point_vector_to_45(points);
833	polygon_mutable_traits<polygon_type>::set_points(polygon, points.begin(), points.end());
834	return polygon;
835	}
836
837	template <typename polygon_type>
838	typename enable_if< typename is_any_mutable_polygon_with_holes_type<polygon_type>::type, polygon_type>::type &
839	snap_to_45(polygon_type& polygon) {
840	typedef typename polygon_with_holes_traits<polygon_type>::hole_type hole_type;
841	hole_type h;
842	set_points(h, begin_points(polygon), end_points(polygon));
843	snap_to_45(h);
844	std::vector<hole_type> holes;
845	holes.reserve(size_holes(polygon));
846	for(typename polygon_with_holes_traits<polygon_type>::iterator_holes_type itr = begin_holes(polygon);
847	itr != end_holes(polygon); ++itr) {
848	holes.push_back(*itr);
849	snap_to_45(holes.back());
850	}
851	assign(polygon, h);
852	set_holes(polygon, holes.begin(), holes.end());
853	return polygon;
854	}
855
856	//scale specifically 45 down
857	template <typename polygon_type>
858	typename enable_if<
859	typename gtl_and< typename is_any_mutable_polygon_without_holes_type<polygon_type>::type,
860	typename gtl_same_type
861	< forty_five_domain,
862	typename geometry_domain<typename geometry_concept<polygon_type>::type>::type>::type>::type,
863	polygon_type>::type &
864	scale_down(polygon_type& polygon, typename coordinate_traits<typename polygon_traits<polygon_type>::coordinate_type>::unsigned_area_type factor) {
865	std::vector<typename std::iterator_traits<typename polygon_traits<polygon_type>::iterator_type>::value_type> points;
866	points.reserve(size(polygon));
867	for(typename polygon_traits<polygon_type>::iterator_type iter = begin_points(polygon);
868	iter != end_points(polygon); ++iter) {
869	points.push_back(*iter);
870	scale_down(points.back(), factor);
871	}
872	snap_point_vector_to_45(points);
873	polygon_mutable_traits<polygon_type>::set_points(polygon, points.begin(), points.end());
874	return polygon;
875	}
876
877	template <typename T>
878	typename enable_if< typename is_any_mutable_polygon_with_holes_type<T>::type, T>::type &
879	scale_down(T& polygon, typename coordinate_traits<typename polygon_traits<T>::coordinate_type>::unsigned_area_type factor) {
880	typedef typename polygon_with_holes_traits<T>::hole_type hole_type;
881	hole_type h;
882	set_points(h, begin_points(polygon), end_points(polygon));
883	scale_down(h, factor);
884	std::vector<hole_type> holes;
885	holes.reserve(size_holes(polygon));
886	for(typename polygon_with_holes_traits<T>::iterator_holes_type itr = begin_holes(polygon);
887	itr != end_holes(polygon); ++itr) {
888	holes.push_back(*itr);
889	scale_down(holes.back(), factor);
890	}
891	assign(polygon, h);
892	set_holes(polygon, holes.begin(), holes.end());
893	return polygon;
894	}
895
896	//scale non-45
897	template <typename polygon_type>
898	typename enable_if<
899	typename gtl_and< typename is_any_mutable_polygon_without_holes_type<polygon_type>::type,
900	typename gtl_not<typename gtl_same_type
901	< forty_five_domain,
902	typename geometry_domain<typename geometry_concept<polygon_type>::type>::type>::type>::type>::type,
903	polygon_type>::type &
904	scale(polygon_type& polygon, double factor) {
905	std::vector<typename std::iterator_traits<typename polygon_traits<polygon_type>::iterator_type>::value_type> points;
906	points.reserve(size(polygon));
907	for(typename polygon_traits<polygon_type>::iterator_type iter = begin_points(polygon);
908	iter != end_points(polygon); ++iter) {
909	points.push_back(*iter);
910	scale(points.back(), anisotropic_scale_factor<double>(factor, factor));
911	}
912	polygon_mutable_traits<polygon_type>::set_points(polygon, points.begin(), points.end());
913	return polygon;
914	}
915
916	//scale specifically 45
917	template <typename polygon_type>
918	polygon_type&
919	scale(polygon_type& polygon, double factor,
920	typename enable_if<
921	typename gtl_and< typename is_any_mutable_polygon_without_holes_type<polygon_type>::type,
922	typename gtl_same_type
923	< forty_five_domain,
924	typename geometry_domain<typename geometry_concept<polygon_type>::type>::type>::type>::type>::type * = 0
925	) {
926	std::vector<typename std::iterator_traits<typename polygon_traits<polygon_type>::iterator_type>::value_type> points;
927	points.reserve(size(polygon));
928	for(typename polygon_traits<polygon_type>::iterator_type iter = begin_points(polygon);
929	iter != end_points(polygon); ++iter) {
930	points.push_back(*iter);
931	scale(points.back(), anisotropic_scale_factor<double>(factor, factor));
932	}
933	snap_point_vector_to_45(points);
934	polygon_mutable_traits<polygon_type>::set_points(polygon, points.begin(), points.end());
935	return polygon;
936	}
937
938	template <typename T>
939	T&
940	scale(T& polygon, double factor,
941	typename enable_if< typename is_any_mutable_polygon_with_holes_type<T>::type>::type * = 0
942	) {
943	typedef typename polygon_with_holes_traits<T>::hole_type hole_type;
944	hole_type h;
945	set_points(h, begin_points(polygon), end_points(polygon));
946	scale(h, factor);
947	std::vector<hole_type> holes;
948	holes.reserve(size_holes(polygon));
949	for(typename polygon_with_holes_traits<T>::iterator_holes_type itr = begin_holes(polygon);
950	itr != end_holes(polygon); ++itr) {
951	holes.push_back(*itr);
952	scale(holes.back(), factor);
953	}
954	assign(polygon, h);
955	set_holes(polygon, holes.begin(), holes.end());
956	return polygon;
957	}
958
959	template <typename iterator_type, typename area_type>
960	static area_type
961	point_sequence_area(iterator_type begin_range, iterator_type end_range) {
962	typedef typename std::iterator_traits<iterator_type>::value_type point_type;
963	if(begin_range == end_range) return area_type(0);
964	point_type first = *begin_range;
965	point_type previous = first;
966	++begin_range;
967	// Initialize trapezoid base line
968	area_type y_base = (area_type)y(first);
969	// Initialize area accumulator
970
971	area_type area(0);
972	while (begin_range != end_range) {
973	area_type x1 = (area_type)x(previous);
974	area_type x2 = (area_type)x(*begin_range);
975	#ifdef BOOST_POLYGON_ICC
976	#pragma warning (push)
977	#pragma warning (disable:1572)
978	#endif
979	if(x1 != x2) {
980	#ifdef BOOST_POLYGON_ICC
981	#pragma warning (pop)
982	#endif
983	// do trapezoid area accumulation
984	area += (x2 - x1) * (((area_type)y(*begin_range) - y_base) +
985	((area_type)y(previous) - y_base)) / 2;
986	}
987	previous = *begin_range;
988	// go to next point
989	++begin_range;
990	}
991	//wrap around to evaluate the edge between first and last if not closed
992	if(!equivalence(first, previous)) {
993	area_type x1 = (area_type)x(previous);
994	area_type x2 = (area_type)x(first);
995	area += (x2 - x1) * (((area_type)y(first) - y_base) +
996	((area_type)y(previous) - y_base)) / 2;
997	}
998	return area;
999	}
1000
1001	template <typename T>
1002	typename enable_if<
1003	typename is_polygon_with_holes_type<T>::type,
1004	typename area_type_by_domain< typename geometry_domain<typename geometry_concept<T>::type>::type,
1005	typename polygon_traits<T>::coordinate_type>::type>::type
1006	area(const T& polygon) {
1007	typedef typename area_type_by_domain< typename geometry_domain<typename geometry_concept<T>::type>::type,
1008	typename polygon_traits<T>::coordinate_type>::type area_type;
1009	area_type retval = point_sequence_area<typename polygon_traits<T>::iterator_type, area_type>
1010	(begin_points(polygon), end_points(polygon));
1011	if(retval < 0) retval *= -1;
1012	for(typename polygon_with_holes_traits<T>::iterator_holes_type itr =
1013	polygon_with_holes_traits<T>::begin_holes(polygon);
1014	itr != polygon_with_holes_traits<T>::end_holes(polygon); ++itr) {
1015	area_type tmp_area = point_sequence_area
1016	<typename polygon_traits<typename polygon_with_holes_traits<T>::hole_type>::iterator_type, area_type>
1017	(begin_points(*itr), end_points(*itr));
1018	if(tmp_area < 0) tmp_area *= -1;
1019	retval -= tmp_area;
1020	}
1021	return retval;
1022	}
1023
1024	template <typename iT>
1025	bool point_sequence_is_45(iT itr, iT itr_end) {
1026	typedef typename std::iterator_traits<iT>::value_type Point;
1027	typedef typename point_traits<Point>::coordinate_type Unit;
1028	if(itr == itr_end) return true;
1029	Point firstPt = *itr;
1030	Point prevPt = firstPt;
1031	++itr;
1032	while(itr != itr_end) {
1033	Point pt = *itr;
1034	Unit deltax = x(pt) - x(prevPt);
1035	Unit deltay = y(pt) - y(prevPt);
1036	if(deltax && deltay &&
1037	local_abs(deltax) != local_abs(deltay))
1038	return false;
1039	prevPt = pt;
1040	++itr;
1041	}
1042	Unit deltax = x(firstPt) - x(prevPt);
1043	Unit deltay = y(firstPt) - y(prevPt);
1044	if(deltax && deltay &&
1045	local_abs(deltax) != local_abs(deltay))
1046	return false;
1047	return true;
1048	}
1049
1050	template <typename polygon_type>
1051	typename enable_if< typename is_polygon_with_holes_type<polygon_type>::type, bool>::type
1052	is_45(const polygon_type& polygon) {
1053	typename polygon_traits<polygon_type>::iterator_type itr = begin_points(polygon), itr_end = end_points(polygon);
1054	if(!point_sequence_is_45(itr, itr_end)) return false;
1055	typename polygon_with_holes_traits<polygon_type>::iterator_holes_type itrh = begin_holes(polygon), itrh_end = end_holes(polygon);
1056	typedef typename polygon_with_holes_traits<polygon_type>::hole_type hole_type;
1057	for(; itrh != itrh_end; ++ itrh) {
1058	typename polygon_traits<hole_type>::iterator_type itr1 = begin_points(polygon), itr1_end = end_points(polygon);
1059	if(!point_sequence_is_45(itr1, itr1_end)) return false;
1060	}
1061	return true;
1062	}
1063
1064	template <typename distance_type, typename iterator_type>
1065	distance_type point_sequence_distance(iterator_type itr, iterator_type itr_end) {
1066	typedef distance_type Unit;
1067	typedef iterator_type iterator;
1068	typedef typename std::iterator_traits<iterator>::value_type point_type;
1069	Unit return_value = Unit(0);
1070	point_type previous_point, first_point;
1071	if(itr == itr_end) return return_value;
1072	previous_point = first_point = *itr;
1073	++itr;
1074	for( ; itr != itr_end; ++itr) {
1075	point_type current_point = *itr;
1076	return_value += (Unit)euclidean_distance(current_point, previous_point);
1077	previous_point = current_point;
1078	}
1079	return_value += (Unit)euclidean_distance(previous_point, first_point);
1080	return return_value;
1081	}
1082
1083	template <typename T>
1084	typename distance_type_by_domain
1085	<typename geometry_domain<typename geometry_concept<T>::type>::type, typename polygon_traits<T>::coordinate_type>::type
1086	perimeter(const T& polygon,
1087	typename enable_if<
1088	typename is_polygon_with_holes_type<T>::type>::type * = 0
1089	) {
1090	typedef typename distance_type_by_domain
1091	<typename geometry_domain<typename geometry_concept<T>::type>::type, typename polygon_traits<T>::coordinate_type>::type Unit;
1092	typedef typename polygon_traits<T>::iterator_type iterator;
1093	iterator itr = begin_points(polygon);
1094	iterator itr_end = end_points(polygon);
1095	Unit return_value = point_sequence_distance<Unit, iterator>(itr, itr_end);
1096	for(typename polygon_with_holes_traits<T>::iterator_holes_type itr_holes = begin_holes(polygon);
1097	itr_holes != end_holes(polygon); ++itr_holes) {
1098	typedef typename polygon_traits<typename polygon_with_holes_traits<T>::hole_type>::iterator_type hitertype;
1099	return_value += point_sequence_distance<Unit, hitertype>(begin_points(*itr_holes), end_points(*itr_holes));
1100	}
1101	return return_value;
1102	}
1103
1104	template <typename T>
1105	typename enable_if <typename is_polygon_with_holes_type<T>::type,
1106	direction_1d>::type
1107	winding(const T& polygon) {
1108	winding_direction wd = polygon_traits<T>::winding(polygon);
1109	if(wd != unknown_winding) {
1110	return wd == clockwise_winding ? CLOCKWISE: COUNTERCLOCKWISE;
1111	}
1112	typedef typename area_type_by_domain< typename geometry_domain<typename geometry_concept<T>::type>::type,
1113	typename polygon_traits<T>::coordinate_type>::type area_type;
1114	return point_sequence_area<typename polygon_traits<T>::iterator_type, area_type>(begin_points(polygon), end_points(polygon)) < 0 ?
1115	COUNTERCLOCKWISE : CLOCKWISE;
1116	}
1117
1118	template <typename T, typename input_point_type>
1119	typename enable_if<
1120	typename gtl_and<
1121	typename is_polygon_90_type<T>::type,
1122	typename gtl_same_type<
1123	typename geometry_concept<input_point_type>::type,
1124	point_concept
1125	>::type
1126	>::type,
1127	bool
1128	>::type contains(
1129	const T& polygon,
1130	const input_point_type& point,
1131	bool consider_touch = true) {
1132	typedef T polygon_type;
1133	typedef typename polygon_traits<polygon_type>::coordinate_type coordinate_type;
1134	typedef typename polygon_traits<polygon_type>::iterator_type iterator;
1135	typedef typename std::iterator_traits<iterator>::value_type point_type;
1136	coordinate_type point_x = x(point);
1137	coordinate_type point_y = y(point);
1138	// Check how many intersections has the ray extended from the given
1139	// point in the x-axis negative direction with the polygon edges.
1140	// If the number is odd the point is within the polygon, otherwise not.
1141	// We can safely ignore horizontal edges, however intersections with
1142	// end points of the vertical edges require special handling. We should
1143	// add one intersection in case horizontal edges that extend vertical edge
1144	// point in the same direction.
1145	int num_full_intersections = 0;
1146	int num_half_intersections = 0;
1147	for (iterator iter = begin_points(polygon); iter != end_points(polygon);) {
1148	point_type curr_point = *iter;
1149	++iter;
1150	point_type next_point = (iter == end_points(polygon)) ? *begin_points(polygon) : *iter;
1151	if (x(curr_point) == x(next_point)) {
1152	if (x(curr_point) > point_x) {
1153	continue;
1154	}
1155	coordinate_type min_y = (std::min)(y(curr_point), y(next_point));
1156	coordinate_type max_y = (std::max)(y(curr_point), y(next_point));
1157	if (point_y > min_y && point_y < max_y) {
1158	if (x(curr_point) == point_x) {
1159	return consider_touch;
1160	}
1161	++num_full_intersections;
1162	}
1163	if (point_y == min_y || point_y == max_y) {
1164	num_half_intersections += (y(curr_point) < y(next_point) ? 1 : -1);
1165	}
1166	} else {
1167	coordinate_type min_x = (std::min)(x(curr_point), x(next_point));
1168	coordinate_type max_x = (std::max)(x(curr_point), x(next_point));
1169	if (point_x >= min_x && point_x <= max_x) {
1170	if (y(curr_point) == point_y) {
1171	return consider_touch;
1172	}
1173	}
1174	}
1175	}
1176	int total_intersections = num_full_intersections + (num_half_intersections >> 1);
1177	return total_intersections & 1;
1178	}
1179
1180	//TODO: refactor to expose as user APIs
1181	template <typename Unit>
1182	struct edge_utils {
1183	typedef point_data<Unit> Point;
1184	typedef std::pair<Point, Point> half_edge;
1185
1186	class less_point : public std::binary_function<Point, Point, bool> {
1187	public:
1188	inline less_point() {}
1189	inline bool operator () (const Point& pt1, const Point& pt2) const {
1190	if(pt1.get(HORIZONTAL) < pt2.get(HORIZONTAL)) return true;
1191	if(pt1.get(HORIZONTAL) == pt2.get(HORIZONTAL)) {
1192	if(pt1.get(VERTICAL) < pt2.get(VERTICAL)) return true;
1193	}
1194	return false;
1195	}
1196	};
1197
1198	static inline bool between(Point pt, Point pt1, Point pt2) {
1199	less_point lp;
1200	if(lp(pt1, pt2))
1201	return lp(pt, pt2) && lp(pt1, pt);
1202	return lp(pt, pt1) && lp(pt2, pt);
1203	}
1204
1205	template <typename area_type>
1206	static inline bool equal_slope(area_type dx1, area_type dy1, area_type dx2, area_type dy2) {
1207	typedef typename coordinate_traits<Unit>::unsigned_area_type unsigned_product_type;
1208	unsigned_product_type cross_1 = (unsigned_product_type)(dx2 < 0 ? -dx2 :dx2) * (unsigned_product_type)(dy1 < 0 ? -dy1 : dy1);
1209	unsigned_product_type cross_2 = (unsigned_product_type)(dx1 < 0 ? -dx1 :dx1) * (unsigned_product_type)(dy2 < 0 ? -dy2 : dy2);
1210	int dx1_sign = dx1 < 0 ? -1 : 1;
1211	int dx2_sign = dx2 < 0 ? -1 : 1;
1212	int dy1_sign = dy1 < 0 ? -1 : 1;
1213	int dy2_sign = dy2 < 0 ? -1 : 1;
1214	int cross_1_sign = dx2_sign * dy1_sign;
1215	int cross_2_sign = dx1_sign * dy2_sign;
1216	return cross_1 == cross_2 && (cross_1_sign == cross_2_sign || cross_1 == 0);
1217	}
1218
1219	static inline bool equal_slope(const Unit& x, const Unit& y,
1220	const Point& pt1, const Point& pt2) {
1221	const Point* pts[2] = {&pt1, &pt2};
1222	typedef typename coordinate_traits<Unit>::manhattan_area_type at;
1223	at dy2 = (at)pts[1]->get(VERTICAL) - (at)y;
1224	at dy1 = (at)pts[0]->get(VERTICAL) - (at)y;
1225	at dx2 = (at)pts[1]->get(HORIZONTAL) - (at)x;
1226	at dx1 = (at)pts[0]->get(HORIZONTAL) - (at)x;
1227	return equal_slope(dx1, dy1, dx2, dy2);
1228	}
1229
1230	template <typename area_type>
1231	static inline bool less_slope(area_type dx1, area_type dy1, area_type dx2, area_type dy2) {
1232	//reflext x and y slopes to right hand side half plane
1233	if(dx1 < 0) {
1234	dy1 *= -1;
1235	dx1 *= -1;
1236	} else if(dx1 == 0) {
1237	//if the first slope is vertical the first cannot be less
1238	return false;
1239	}
1240	if(dx2 < 0) {
1241	dy2 *= -1;
1242	dx2 *= -1;
1243	} else if(dx2 == 0) {
1244	//if the second slope is vertical the first is always less unless it is also vertical, in which case they are equal
1245	return dx1 != 0;
1246	}
1247	typedef typename coordinate_traits<Unit>::unsigned_area_type unsigned_product_type;
1248	unsigned_product_type cross_1 = (unsigned_product_type)(dx2 < 0 ? -dx2 :dx2) * (unsigned_product_type)(dy1 < 0 ? -dy1 : dy1);
1249	unsigned_product_type cross_2 = (unsigned_product_type)(dx1 < 0 ? -dx1 :dx1) * (unsigned_product_type)(dy2 < 0 ? -dy2 : dy2);
1250	int dx1_sign = dx1 < 0 ? -1 : 1;
1251	int dx2_sign = dx2 < 0 ? -1 : 1;
1252	int dy1_sign = dy1 < 0 ? -1 : 1;
1253	int dy2_sign = dy2 < 0 ? -1 : 1;
1254	int cross_1_sign = dx2_sign * dy1_sign;
1255	int cross_2_sign = dx1_sign * dy2_sign;
1256	if(cross_1_sign < cross_2_sign) return true;
1257	if(cross_2_sign < cross_1_sign) return false;
1258	if(cross_1_sign == -1) return cross_2 < cross_1;
1259	return cross_1 < cross_2;
1260	}
1261
1262	static inline bool less_slope(const Unit& x, const Unit& y,
1263	const Point& pt1, const Point& pt2) {
1264	const Point* pts[2] = {&pt1, &pt2};
1265	//compute y value on edge from pt_ to pts[1] at the x value of pts[0]
1266	typedef typename coordinate_traits<Unit>::manhattan_area_type at;
1267	at dy2 = (at)pts[1]->get(VERTICAL) - (at)y;
1268	at dy1 = (at)pts[0]->get(VERTICAL) - (at)y;
1269	at dx2 = (at)pts[1]->get(HORIZONTAL) - (at)x;
1270	at dx1 = (at)pts[0]->get(HORIZONTAL) - (at)x;
1271	return less_slope(dx1, dy1, dx2, dy2);
1272	}
1273
1274	//return -1 below, 0 on and 1 above line
1275	//assumes point is on x interval of segment
1276	static inline int on_above_or_below(Point pt, const half_edge& he) {
1277	if(pt == he.first || pt == he.second) return 0;
1278	if(equal_slope(pt.get(HORIZONTAL), pt.get(VERTICAL), he.first, he.second)) return 0;
1279	bool less_result = less_slope(pt.get(HORIZONTAL), pt.get(VERTICAL), he.first, he.second);
1280	int retval = less_result ? -1 : 1;
1281	less_point lp;
1282	if(lp(he.second, he.first)) retval *= -1;
1283	if(!between(pt, pt1: he.first, pt2: he.second)) retval *= -1;
1284	return retval;
1285	}
1286	};
1287
1288	template <typename T, typename input_point_type>
1289	typename enable_if<
1290	typename gtl_and< typename is_any_mutable_polygon_with_holes_type<T>::type,
1291	typename gtl_same_type<typename geometry_concept<input_point_type>::type, point_concept>::type>::type,
1292	bool>::type
1293	contains(const T& polygon, const input_point_type& point, bool consider_touch = true) {
1294	typedef typename polygon_with_holes_traits<T>::iterator_holes_type holes_iterator;
1295	bool isInside = contains( view_as< typename polygon_from_polygon_with_holes_type<
1296	typename geometry_concept<T>::type>::type>( polygon ), point, consider_touch );
1297	if(!isInside) return false; //no need to check holes
1298	holes_iterator itH = begin_holes( polygon );
1299	while( itH != end_holes( polygon ) ) {
1300	if( contains( *itH, point, !consider_touch ) ) {
1301	isInside = false;
1302	break;
1303	}
1304	++itH;
1305	}
1306	return isInside;
1307	}
1308
1309	template <typename T, typename input_point_type>
1310	typename enable_if<
1311	typename gtl_and_3<
1312	typename is_polygon_type<T>::type,
1313	typename gtl_different_type<typename geometry_domain<typename geometry_concept<T>::type>::type, manhattan_domain>::type,
1314	typename gtl_same_type<typename geometry_concept<input_point_type>::type, point_concept>::type>::type,
1315	bool>::type
1316	contains(const T& polygon, const input_point_type& point, bool consider_touch = true) {
1317	typedef typename point_traits<input_point_type>::coordinate_type Unit;
1318	typedef point_data<Unit> Point;
1319	typedef std::pair<Point, Point> half_edge;
1320	typedef typename polygon_traits<T>::iterator_type iterator;
1321	iterator itr = begin_points(polygon);
1322	iterator itrEnd = end_points(polygon);
1323	half_edge he;
1324	if(itr == itrEnd) return false;
1325	assign(he.first, *itr);
1326	Point firstPt;
1327	assign(firstPt, *itr);
1328	++itr;
1329	if(itr == itrEnd) return false;
1330	bool done = false;
1331	int above = 0;
1332	while(!done) {
1333	Point currentPt;
1334	if(itr == itrEnd) {
1335	done = true;
1336	currentPt = firstPt;
1337	} else {
1338	assign(currentPt, *itr);
1339	++itr;
1340	}
1341	if(currentPt == he.first) {
1342	continue;
1343	} else {
1344	he.second = currentPt;
1345	if(equivalence(point, currentPt)) return consider_touch;
1346	Unit xmin = (std::min)(x(he.first), x(he.second));
1347	Unit xmax = (std::max)(x(he.first), x(he.second));
1348	if(x(point) >= xmin && x(point) < xmax) { //double counts if <= xmax
1349	Point tmppt;
1350	assign(tmppt, point);
1351	int oabedge = edge_utils<Unit>::on_above_or_below(tmppt, he);
1352	if(oabedge == 0) return consider_touch;
1353	if(oabedge == 1) ++above;
1354	} else if(x(point) == xmax) {
1355	if(x(point) == xmin) {
1356	Unit ymin = (std::min)(y(he.first), y(he.second));
1357	Unit ymax = (std::max)(y(he.first), y(he.second));
1358	Unit ypt = y(point);
1359	if(ypt <= ymax && ypt >= ymin)
1360	return consider_touch;
1361	} else {
1362	Point tmppt;
1363	assign(tmppt, point);
1364	if( edge_utils<Unit>::on_above_or_below(tmppt, he) == 0 ) {
1365	return consider_touch;
1366	}
1367	}
1368	}
1369	}
1370	he.first = he.second;
1371	}
1372	return above % 2 != 0; //if the point is above an odd number of edges is must be inside polygon
1373	}
1374
1375	/*
1376	template <typename T, typename input_point_type>
1377	typename enable_if<
1378	typename gtl_and_3<
1379	typename is_polygon_with_holes_type<T>::type,
1380	typename gtl_different_type<typename geometry_domain<typename geometry_concept<T>::type>::type, manhattan_domain>::type,
1381	typename gtl_same_type<typename geometry_concept<input_point_type>::type, point_concept>::type>::type,
1382	bool>::type
1383	contains(const T& polygon, const input_point_type& point, bool consider_touch = true) {
1384	typedef typename point_traits<input_point_type>::coordinate_type Unit;
1385	typedef point_data<Unit> Point;
1386	typedef std::pair<Point, Point> half_edge;
1387	typedef typename polygon_traits<T>::iterator_type iterator;
1388	iterator itr = begin_points(polygon);
1389	iterator itrEnd = end_points(polygon);
1390	half_edge he;
1391	if(itr == itrEnd) return false;
1392	assign(he.first, *itr);
1393	Point firstPt;
1394	assign(firstPt, *itr);
1395	++itr;
1396	if(itr == itrEnd) return false;
1397	bool done = false;
1398	int above = 0;
1399	while(!done) {
1400	Point currentPt;
1401	if(itr == itrEnd) {
1402	done = true;
1403	currentPt = firstPt;
1404	} else {
1405	assign(currentPt, *itr);
1406	++itr;
1407	}
1408	if(currentPt == he.first) {
1409	continue;
1410	} else {
1411	he.second = currentPt;
1412	if(equivalence(point, currentPt)) return consider_touch;
1413	Unit xmin = (std::min)(x(he.first), x(he.second));
1414	Unit xmax = (std::max)(x(he.first), x(he.second));
1415	if(x(point) >= xmin && x(point) < xmax) { //double counts if <= xmax
1416	Point tmppt;
1417	assign(tmppt, point);
1418	int oabedge = edge_utils<Unit>::on_above_or_below(tmppt, he);
1419	if(oabedge == 0) return consider_touch;
1420	if(oabedge == 1) ++above;
1421	}
1422	}
1423	he.first = he.second;
1424	}
1425	return above % 2 != 0; //if the point is above an odd number of edges is must be inside polygon
1426	}
1427	*/
1428
1429	template <typename T1, typename T2>
1430	typename enable_if<
1431	typename gtl_and< typename is_mutable_rectangle_concept<typename geometry_concept<T1>::type>::type,
1432	typename is_polygon_with_holes_type<T2>::type>::type,
1433	bool>::type
1434	extents(T1& bounding_box, const T2& polygon) {
1435	typedef typename polygon_traits<T2>::iterator_type iterator;
1436	bool first_iteration = true;
1437	iterator itr_end = end_points(polygon);
1438	for(iterator itr = begin_points(polygon); itr != itr_end; ++itr) {
1439	if(first_iteration) {
1440	set_points(bounding_box, *itr, *itr);
1441	first_iteration = false;
1442	} else {
1443	encompass(bounding_box, *itr);
1444	}
1445	}
1446	if(first_iteration) return false;
1447	return true;
1448	}
1449
1450	template <typename T1, typename T2>
1451	typename enable_if<
1452	typename gtl_and< typename is_mutable_point_concept<typename geometry_concept<T1>::type>::type,
1453	typename is_polygon_with_holes_type<T2>::type>::type,
1454	bool>::type
1455	center(T1& center_point, const T2& polygon) {
1456	typedef typename polygon_traits<T2>::coordinate_type coordinate_type;
1457	rectangle_data<coordinate_type> bbox;
1458	extents(bbox, polygon);
1459	return center(center_point, bbox);
1460	}
1461
1462	template <class T>
1463	template <class T2>
1464	polygon_90_data<T>& polygon_90_data<T>::operator=(const T2& rvalue) {
1465	assign(*this, rvalue);
1466	return *this;
1467	}
1468
1469	template <class T>
1470	template <class T2>
1471	polygon_45_data<T>& polygon_45_data<T>::operator=(const T2& rvalue) {
1472	assign(*this, rvalue);
1473	return *this;
1474	}
1475
1476	template <class T>
1477	template <class T2>
1478	polygon_data<T>& polygon_data<T>::operator=(const T2& rvalue) {
1479	assign(*this, rvalue);
1480	return *this;
1481	}
1482
1483	template <class T>
1484	template <class T2>
1485	polygon_90_with_holes_data<T>& polygon_90_with_holes_data<T>::operator=(const T2& rvalue) {
1486	assign(*this, rvalue);
1487	return *this;
1488	}
1489
1490	template <class T>
1491	template <class T2>
1492	polygon_45_with_holes_data<T>& polygon_45_with_holes_data<T>::operator=(const T2& rvalue) {
1493	assign(*this, rvalue);
1494	return *this;
1495	}
1496
1497	template <class T>
1498	template <class T2>
1499	polygon_with_holes_data<T>& polygon_with_holes_data<T>::operator=(const T2& rvalue) {
1500	assign(*this, rvalue);
1501	return *this;
1502	}
1503
1504	template <typename T>
1505	struct geometry_concept<polygon_data<T> > {
1506	typedef polygon_concept type;
1507	};
1508	template <typename T>
1509	struct geometry_concept<polygon_45_data<T> > {
1510	typedef polygon_45_concept type;
1511	};
1512	template <typename T>
1513	struct geometry_concept<polygon_90_data<T> > {
1514	typedef polygon_90_concept type;
1515	};
1516	template <typename T>
1517	struct geometry_concept<polygon_with_holes_data<T> > {
1518	typedef polygon_with_holes_concept type;
1519	};
1520	template <typename T>
1521	struct geometry_concept<polygon_45_with_holes_data<T> > {
1522	typedef polygon_45_with_holes_concept type;
1523	};
1524	template <typename T>
1525	struct geometry_concept<polygon_90_with_holes_data<T> > {
1526	typedef polygon_90_with_holes_concept type;
1527	};
1528
1529	// template <typename T> struct polygon_with_holes_traits<polygon_90_data<T> > {
1530	// typedef polygon_90_data<T> hole_type;
1531	// typedef const hole_type* iterator_holes_type;
1532	// static inline iterator_holes_type begin_holes(const hole_type& t) { return &t; }
1533	// static inline iterator_holes_type end_holes(const hole_type& t) { return &t; }
1534	// static inline std::size_t size_holes(const hole_type& t) { return 0; }
1535	// };
1536	// template <typename T> struct polygon_with_holes_traits<polygon_45_data<T> > {
1537	// typedef polygon_45_data<T> hole_type;
1538	// typedef const hole_type* iterator_holes_type;
1539	// static inline iterator_holes_type begin_holes(const hole_type& t) { return &t; }
1540	// static inline iterator_holes_type end_holes(const hole_type& t) { return &t; }
1541	// static inline std::size_t size_holes(const hole_type& t) { return 0; }
1542	// };
1543	// template <typename T> struct polygon_with_holes_traits<polygon_data<T> > {
1544	// typedef polygon_data<T> hole_type;
1545	// typedef const hole_type* iterator_holes_type;
1546	// static inline iterator_holes_type begin_holes(const hole_type& t) { return &t; }
1547	// static inline iterator_holes_type end_holes(const hole_type& t) { return &t; }
1548	// static inline std::size_t size_holes(const hole_type& t) { return 0; }
1549	// };
1550	template <typename T> struct get_void {};
1551	template <> struct get_void<gtl_yes> { typedef void type; };
1552
1553	template <typename T> struct polygon_with_holes_traits<
1554	T, typename get_void<typename is_any_mutable_polygon_without_holes_type<T>::type>::type > {
1555	typedef T hole_type;
1556	typedef const hole_type* iterator_holes_type;
1557	static inline iterator_holes_type begin_holes(const hole_type& t) { return &t; }
1558	static inline iterator_holes_type end_holes(const hole_type& t) { return &t; }
1559	};
1560
1561	template <typename T>
1562	struct view_of<rectangle_concept, T> {
1563	typedef typename polygon_traits<T>::coordinate_type coordinate_type;
1564	typedef interval_data<coordinate_type> interval_type;
1565	rectangle_data<coordinate_type> rect;
1566	view_of(const T& obj) : rect() {
1567	point_data<coordinate_type> pts[2];
1568	typename polygon_traits<T>::iterator_type itr =
1569	begin_points(obj), itre = end_points(obj);
1570	if(itr == itre) return;
1571	assign(pts[0], *itr);
1572	++itr;
1573	if(itr == itre) return;
1574	++itr;
1575	if(itr == itre) return;
1576	assign(pts[1], *itr);
1577	set_points(rect, pts[0], pts[1]);
1578	}
1579	inline interval_type get(orientation_2d orient) const {
1580	return rect.get(orient); }
1581	};
1582
1583	template <typename T>
1584	struct geometry_concept<view_of<rectangle_concept, T> > {
1585	typedef rectangle_concept type;
1586	};
1587
1588	template <typename T>
1589	struct view_of<polygon_45_concept, T> {
1590	const T* t;
1591	view_of(const T& obj) : t(&obj) {}
1592	typedef typename polygon_traits<T>::coordinate_type coordinate_type;
1593	typedef typename polygon_traits<T>::iterator_type iterator_type;
1594	typedef typename polygon_traits<T>::point_type point_type;
1595
1596	/// Get the begin iterator
1597	inline iterator_type begin() const {
1598	return polygon_traits<T>::begin_points(*t);
1599	}
1600
1601	/// Get the end iterator
1602	inline iterator_type end() const {
1603	return polygon_traits<T>::end_points(*t);
1604	}
1605
1606	/// Get the number of sides of the polygon
1607	inline std::size_t size() const {
1608	return polygon_traits<T>::size(*t);
1609	}
1610
1611	/// Get the winding direction of the polygon
1612	inline winding_direction winding() const {
1613	return polygon_traits<T>::winding(*t);
1614	}
1615	};
1616
1617	template <typename T>
1618	struct geometry_concept<view_of<polygon_45_concept, T> > {
1619	typedef polygon_45_concept type;
1620	};
1621
1622	template <typename T>
1623	struct view_of<polygon_90_concept, T> {
1624	const T* t;
1625	view_of(const T& obj) : t(&obj) {}
1626	typedef typename polygon_traits<T>::coordinate_type coordinate_type;
1627	typedef typename polygon_traits<T>::iterator_type iterator_type;
1628	typedef typename polygon_traits<T>::point_type point_type;
1629	typedef iterator_points_to_compact<iterator_type, point_type> compact_iterator_type;
1630
1631	/// Get the begin iterator
1632	inline compact_iterator_type begin_compact() const {
1633	return compact_iterator_type(polygon_traits<T>::begin_points(*t),
1634	polygon_traits<T>::end_points(*t));
1635	}
1636
1637	/// Get the end iterator
1638	inline compact_iterator_type end_compact() const {
1639	return compact_iterator_type(polygon_traits<T>::end_points(*t),
1640	polygon_traits<T>::end_points(*t));
1641	}
1642
1643	/// Get the number of sides of the polygon
1644	inline std::size_t size() const {
1645	return polygon_traits<T>::size(*t);
1646	}
1647
1648	/// Get the winding direction of the polygon
1649	inline winding_direction winding() const {
1650	return polygon_traits<T>::winding(*t);
1651	}
1652	};
1653
1654	template <typename T>
1655	struct geometry_concept<view_of<polygon_90_concept, T> > {
1656	typedef polygon_90_concept type;
1657	};
1658
1659	template <typename T>
1660	struct view_of<polygon_45_with_holes_concept, T> {
1661	const T* t;
1662	view_of(const T& obj) : t(&obj) {}
1663	typedef typename polygon_traits<T>::coordinate_type coordinate_type;
1664	typedef typename polygon_traits<T>::iterator_type iterator_type;
1665	typedef typename polygon_traits<T>::point_type point_type;
1666	typedef view_of<polygon_45_concept, typename polygon_with_holes_traits<T>::hole_type> hole_type;
1667	struct iterator_holes_type {
1668	typedef std::forward_iterator_tag iterator_category;
1669	typedef hole_type value_type;
1670	typedef std::ptrdiff_t difference_type;
1671	typedef const hole_type* pointer; //immutable
1672	typedef const hole_type& reference; //immutable
1673	typedef typename polygon_with_holes_traits<T>::iterator_holes_type iht;
1674	iht internal_itr;
1675	iterator_holes_type() : internal_itr() {}
1676	iterator_holes_type(iht iht_in) : internal_itr(iht_in) {}
1677	inline iterator_holes_type& operator++() {
1678	++internal_itr;
1679	return *this;
1680	}
1681	inline const iterator_holes_type operator++(int) {
1682	iterator_holes_type tmp(*this);
1683	++(*this);
1684	return tmp;
1685	}
1686	inline bool operator==(const iterator_holes_type& that) const {
1687	return (internal_itr == that.internal_itr);
1688	}
1689	inline bool operator!=(const iterator_holes_type& that) const {
1690	return (internal_itr != that.internal_itr);
1691	}
1692	inline value_type operator*() const {
1693	return view_as<polygon_45_concept>(*internal_itr);
1694	}
1695	};
1696
1697	/// Get the begin iterator
1698	inline iterator_type begin() const {
1699	return polygon_traits<T>::begin_points(*t);
1700	}
1701
1702	/// Get the end iterator
1703	inline iterator_type end() const {
1704	return polygon_traits<T>::end_points(*t);
1705	}
1706
1707	/// Get the number of sides of the polygon
1708	inline std::size_t size() const {
1709	return polygon_traits<T>::size(*t);
1710	}
1711
1712	/// Get the winding direction of the polygon
1713	inline winding_direction winding() const {
1714	return polygon_traits<T>::winding(*t);
1715	}
1716
1717	/// Get the begin iterator
1718	inline iterator_holes_type begin_holes() const {
1719	return polygon_with_holes_traits<T>::begin_holes(*t);
1720	}
1721
1722	/// Get the end iterator
1723	inline iterator_holes_type end_holes() const {
1724	return polygon_with_holes_traits<T>::end_holes(*t);
1725	}
1726
1727	/// Get the number of sides of the polygon
1728	inline std::size_t size_holes() const {
1729	return polygon_with_holes_traits<T>::size_holes(*t);
1730	}
1731
1732	};
1733
1734	template <typename T>
1735	struct geometry_concept<view_of<polygon_45_with_holes_concept, T> > {
1736	typedef polygon_45_with_holes_concept type;
1737	};
1738
1739	template <typename T>
1740	struct view_of<polygon_90_with_holes_concept, T> {
1741	const T* t;
1742	view_of(const T& obj) : t(&obj) {}
1743	typedef typename polygon_traits<T>::coordinate_type coordinate_type;
1744	typedef typename polygon_traits<T>::iterator_type iterator_type;
1745	typedef typename polygon_traits<T>::point_type point_type;
1746	typedef iterator_points_to_compact<iterator_type, point_type> compact_iterator_type;
1747	typedef view_of<polygon_90_concept, typename polygon_with_holes_traits<T>::hole_type> hole_type;
1748	struct iterator_holes_type {
1749	typedef std::forward_iterator_tag iterator_category;
1750	typedef hole_type value_type;
1751	typedef std::ptrdiff_t difference_type;
1752	typedef const hole_type* pointer; //immutable
1753	typedef const hole_type& reference; //immutable
1754	typedef typename polygon_with_holes_traits<T>::iterator_holes_type iht;
1755	iht internal_itr;
1756	iterator_holes_type() : internal_itr() {}
1757	iterator_holes_type(iht iht_in) : internal_itr(iht_in) {}
1758	inline iterator_holes_type& operator++() {
1759	++internal_itr;
1760	return *this;
1761	}
1762	inline const iterator_holes_type operator++(int) {
1763	iterator_holes_type tmp(*this);
1764	++(*this);
1765	return tmp;
1766	}
1767	inline bool operator==(const iterator_holes_type& that) const {
1768	return (internal_itr == that.internal_itr);
1769	}
1770	inline bool operator!=(const iterator_holes_type& that) const {
1771	return (internal_itr != that.internal_itr);
1772	}
1773	inline value_type operator*() const {
1774	return view_as<polygon_90_concept>(*internal_itr);
1775	}
1776	};
1777
1778	/// Get the begin iterator
1779	inline compact_iterator_type begin_compact() const {
1780	return compact_iterator_type(polygon_traits<T>::begin_points(*t),
1781	polygon_traits<T>::end_points(*t));
1782	}
1783
1784	/// Get the end iterator
1785	inline compact_iterator_type end_compact() const {
1786	return compact_iterator_type(polygon_traits<T>::end_points(*t),
1787	polygon_traits<T>::end_points(*t));
1788	}
1789
1790	/// Get the number of sides of the polygon
1791	inline std::size_t size() const {
1792	return polygon_traits<T>::size(*t);
1793	}
1794
1795	/// Get the winding direction of the polygon
1796	inline winding_direction winding() const {
1797	return polygon_traits<T>::winding(*t);
1798	}
1799
1800	/// Get the begin iterator
1801	inline iterator_holes_type begin_holes() const {
1802	return polygon_with_holes_traits<T>::begin_holes(*t);
1803	}
1804
1805	/// Get the end iterator
1806	inline iterator_holes_type end_holes() const {
1807	return polygon_with_holes_traits<T>::end_holes(*t);
1808	}
1809
1810	/// Get the number of sides of the polygon
1811	inline std::size_t size_holes() const {
1812	return polygon_with_holes_traits<T>::size_holes(*t);
1813	}
1814
1815	};
1816
1817	template <typename T>
1818	struct geometry_concept<view_of<polygon_90_with_holes_concept, T> > {
1819	typedef polygon_90_with_holes_concept type;
1820	};
1821
1822	template <typename T>
1823	struct view_of<polygon_concept, T> {
1824	const T* t;
1825	view_of(const T& obj) : t(&obj) {}
1826	typedef typename polygon_traits<T>::coordinate_type coordinate_type;
1827	typedef typename polygon_traits<T>::iterator_type iterator_type;
1828	typedef typename polygon_traits<T>::point_type point_type;
1829
1830	/// Get the begin iterator
1831	inline iterator_type begin() const {
1832	return polygon_traits<T>::begin_points(*t);
1833	}
1834
1835	/// Get the end iterator
1836	inline iterator_type end() const {
1837	return polygon_traits<T>::end_points(*t);
1838	}
1839
1840	/// Get the number of sides of the polygon
1841	inline std::size_t size() const {
1842	return polygon_traits<T>::size(*t);
1843	}
1844
1845	/// Get the winding direction of the polygon
1846	inline winding_direction winding() const {
1847	return polygon_traits<T>::winding(*t);
1848	}
1849	};
1850
1851	template <typename T>
1852	struct geometry_concept<view_of<polygon_concept, T> > {
1853	typedef polygon_concept type;
1854	};
1855	}
1856	}
1857
1858	#endif
1859