2 Copyright 2010 Intel Corporation
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).
9 #include <boost/polygon/polygon.hpp>
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
;
17 void convolve_two_segments(std::vector
<point
>& figure
, const edge
& a
, const edge
& b
) {
18 using namespace boost::polygon
;
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
);
30 template <typename itrT1
, typename itrT2
>
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
)
37 std::vector
<point
> vec
;
40 for( ; ab
!= ae
; ++ab
) {
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());
55 template <typename itrT
>
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
));
67 void convolve_two_polygon_sets(polygon_set
& result
, const polygon_set
& a
, const polygon_set
& b
) {
68 using namespace boost::polygon
;
70 std::vector
<polygon
> a_polygons
;
71 std::vector
<polygon
> 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
);
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
]))));
91 namespace boost
{ namespace polygon
{
94 std::ostream
& operator<<(std::ostream
& o
, const polygon_data
<T
>& poly
) {
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
);
105 template <typename T
>
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
);
113 for(typename polygon_with_holes_data
<T
>::iterator_holes_type itr
= poly
.begin_holes();
114 itr
!= poly
.end_holes(); ++itr
) {
122 int main(int argc
, char **argv
) {
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));
139 boost::polygon::set_points(poly
, pts
.begin(), pts
.end());
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());
148 convolve_two_polygon_sets(c
, a
, b
);
150 for(int i
= 0; i
< polys
.size(); ++i
){
151 std::cout
<< polys
[i
] << std::endl
;