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