1 /*
2 Copyright 2010 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 #include <iostream>
9 #include <boost/polygon/polygon.hpp>
10
11 typedef boost::polygon::point_data<int> point;
12 typedef boost::polygon::polygon_set_data<int> polygon_set;
13 typedef boost::polygon::polygon_with_holes_data<int> polygon;
14 typedef std::pair<point, point> edge;
15 using namespace boost::polygon::operators;
16
convolve_two_segments(std::vector<point> & figure,const edge & a,const edge & b)17 void convolve_two_segments(std::vector<point>& figure, const edge& a, const edge& b) {
18 using namespace boost::polygon;
19 figure.clear();
20 figure.push_back(point(a.first));
21 figure.push_back(point(a.first));
22 figure.push_back(point(a.second));
23 figure.push_back(point(a.second));
24 convolve(figure[0], b.second);
25 convolve(figure[1], b.first);
26 convolve(figure[2], b.first);
27 convolve(figure[3], b.second);
28 }
29
30 template <typename itrT1, typename itrT2>
convolve_two_point_sequences(polygon_set & result,itrT1 ab,itrT1 ae,itrT2 bb,itrT2 be)31 void convolve_two_point_sequences(polygon_set& result, itrT1 ab, itrT1 ae, itrT2 bb, itrT2 be) {
32 using namespace boost::polygon;
33 if(ab == ae || bb == be)
34 return;
35 point first_a = *ab;
36 point prev_a = *ab;
37 std::vector<point> vec;
38 polygon poly;
39 ++ab;
40 for( ; ab != ae; ++ab) {
41 point first_b = *bb;
42 point prev_b = *bb;
43 itrT2 tmpb = bb;
44 ++tmpb;
45 for( ; tmpb != be; ++tmpb) {
46 convolve_two_segments(vec, std::make_pair(prev_b, *tmpb), std::make_pair(prev_a, *ab));
47 set_points(poly, vec.begin(), vec.end());
48 result.insert(poly);
49 prev_b = *tmpb;
50 }
51 prev_a = *ab;
52 }
53 }
54
55 template <typename itrT>
convolve_point_sequence_with_polygons(polygon_set & result,itrT b,itrT e,const std::vector<polygon> & polygons)56 void convolve_point_sequence_with_polygons(polygon_set& result, itrT b, itrT e, const std::vector<polygon>& polygons) {
57 using namespace boost::polygon;
58 for(std::size_t i = 0; i < polygons.size(); ++i) {
59 convolve_two_point_sequences(result, b, e, begin_points(polygons[i]), end_points(polygons[i]));
60 for(polygon_with_holes_traits<polygon>::iterator_holes_type itrh = begin_holes(polygons[i]);
61 itrh != end_holes(polygons[i]); ++itrh) {
62 convolve_two_point_sequences(result, b, e, begin_points(*itrh), end_points(*itrh));
63 }
64 }
65 }
66
convolve_two_polygon_sets(polygon_set & result,const polygon_set & a,const polygon_set & b)67 void convolve_two_polygon_sets(polygon_set& result, const polygon_set& a, const polygon_set& b) {
68 using namespace boost::polygon;
69 result.clear();
70 std::vector<polygon> a_polygons;
71 std::vector<polygon> b_polygons;
72 a.get(a_polygons);
73 b.get(b_polygons);
74 for(std::size_t ai = 0; ai < a_polygons.size(); ++ai) {
75 convolve_point_sequence_with_polygons(result, begin_points(a_polygons[ai]),
76 end_points(a_polygons[ai]), b_polygons);
77 for(polygon_with_holes_traits<polygon>::iterator_holes_type itrh = begin_holes(a_polygons[ai]);
78 itrh != end_holes(a_polygons[ai]); ++itrh) {
79 convolve_point_sequence_with_polygons(result, begin_points(*itrh),
80 end_points(*itrh), b_polygons);
81 }
82 for(std::size_t bi = 0; bi < b_polygons.size(); ++bi) {
83 polygon tmp_poly = a_polygons[ai];
84 result.insert(convolve(tmp_poly, *(begin_points(b_polygons[bi]))));
85 tmp_poly = b_polygons[bi];
86 result.insert(convolve(tmp_poly, *(begin_points(a_polygons[ai]))));
87 }
88 }
89 }
90
91 namespace boost { namespace polygon{
92
93 template <typename T>
operator <<(std::ostream & o,const polygon_data<T> & poly)94 std::ostream& operator<<(std::ostream& o, const polygon_data<T>& poly) {
95 o << "Polygon { ";
96 for(typename polygon_data<T>::iterator_type itr = poly.begin();
97 itr != poly.end(); ++itr) {
98 if(itr != poly.begin()) o << ", ";
99 o << (*itr).get(HORIZONTAL) << " " << (*itr).get(VERTICAL);
100 }
101 o << " } ";
102 return o;
103 }
104
105 template <typename T>
operator <<(std::ostream & o,const polygon_with_holes_data<T> & poly)106 std::ostream& operator<<(std::ostream& o, const polygon_with_holes_data<T>& poly) {
107 o << "Polygon With Holes { ";
108 for(typename polygon_with_holes_data<T>::iterator_type itr = poly.begin();
109 itr != poly.end(); ++itr) {
110 if(itr != poly.begin()) o << ", ";
111 o << (*itr).get(HORIZONTAL) << " " << (*itr).get(VERTICAL);
112 } o << " { ";
113 for(typename polygon_with_holes_data<T>::iterator_holes_type itr = poly.begin_holes();
114 itr != poly.end_holes(); ++itr) {
115 o << (*itr);
116 }
117 o << " } } ";
118 return o;
119 }
120 }}
121
main(int argc,char ** argv)122 int main(int argc, char **argv) {
123 polygon_set a, b, c;
124 a += boost::polygon::rectangle_data<int>(0, 0, 1000, 1000);
125 a -= boost::polygon::rectangle_data<int>(100, 100, 900, 900);
126 a += boost::polygon::rectangle_data<int>(1000, -1000, 1010, -990);
127 std::vector<polygon> polys;
128 std::vector<point> pts;
129 pts.push_back(point(-40, 0));
130 pts.push_back(point(-10, 10));
131 pts.push_back(point(0, 40));
132 pts.push_back(point(10, 10));
133 pts.push_back(point(40, 0));
134 pts.push_back(point(10, -10));
135 pts.push_back(point(0, -40));
136 pts.push_back(point(-10, -10));
137 pts.push_back(point(-40, 0));
138 polygon poly;
139 boost::polygon::set_points(poly, pts.begin(), pts.end());
140 b+=poly;
141 pts.clear();
142 pts.push_back(point(1040, 1040));
143 pts.push_back(point(1050, 1045));
144 pts.push_back(point(1045, 1050));
145 boost::polygon::set_points(poly, pts.begin(), pts.end());
146 b+=poly;
147 polys.clear();
148 convolve_two_polygon_sets(c, a, b);
149 c.get(polys);
150 for(int i = 0; i < polys.size(); ++i ){
151 std::cout << polys[i] << std::endl;
152 }
153 return 0;
154 }
155