1 // Copyright (c) 2006 Tel-Aviv University (Israel).
2 // All rights reserved.
3 //
4 // This file is part of CGAL (www.cgal.org).
5 //
6 // $URL: https://github.com/CGAL/cgal/blob/v5.3/Minkowski_sum_2/include/CGAL/minkowski_sum_2.h $
7 // $Id: minkowski_sum_2.h 254d60f 2019-10-19T15:23:19+02:00 Sébastien Loriot
8 // SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial
9 //
10 // Author(s) : Ron Wein <wein_r@yahoo.com>
11 // Efi Fogel <efifogel@gmail.com>
12
13 #ifndef CGAL_MINKOWSKI_SUM_2_H
14 #define CGAL_MINKOWSKI_SUM_2_H
15
16 #include <CGAL/license/Minkowski_sum_2.h>
17
18
19 #include <CGAL/basic.h>
20 #include <CGAL/Polygon_with_holes_2.h>
21 #include <CGAL/Minkowski_sum_2/Hole_filter_2.h>
22 #include <CGAL/Minkowski_sum_2/Minkowski_sum_by_reduced_convolution_2.h>
23 #include <CGAL/Minkowski_sum_2/Minkowski_sum_conv_2.h>
24 #include <CGAL/Minkowski_sum_2/Minkowski_sum_decomp_2.h>
25 #include <CGAL/Polygon_nop_decomposition_2.h>
26 #include <CGAL/Gps_segment_traits_2.h>
27
28 #include <list>
29
30 namespace CGAL {
31
32 /*!
33 * Computes the Minkowski sum \f$ P \oplus Q\f$ of two given polygons.
34 * The function computes the reduced convolution of the two polygons and
35 * extracts those loops of the convolution which are part of the Minkowsi
36 * sum. This method works very efficiently, regardless of whether `P` and
37 * `Q` are convex or non-convex.
38 * Note that as the input polygons may not be convex, their Minkowski
39 * sum may not be a simple polygon. The result is therefore represented
40 * as a polygon with holes.
41 * \param[in] pgn1 The first polygon.
42 * \param[in] pgn2 The second polygon.
43 * \pre Both `P` and `Q` are simple, counterclockwise-oriented polygons.
44 */
45 template <typename Kernel_, typename Container_>
46 Polygon_with_holes_2<Kernel_, Container_>
minkowski_sum_by_reduced_convolution_2(const Polygon_2<Kernel_,Container_> & pgn1,const Polygon_2<Kernel_,Container_> & pgn2)47 minkowski_sum_by_reduced_convolution_2(const Polygon_2<Kernel_,
48 Container_>& pgn1,
49 const Polygon_2<Kernel_,
50 Container_>& pgn2)
51 {
52 typedef Kernel_ Kernel;
53 typedef Container_ Container;
54
55 Minkowski_sum_by_reduced_convolution_2<Kernel, Container> mink_sum;
56 Polygon_2<Kernel, Container> sum_bound;
57 std::list<Polygon_2<Kernel, Container> > sum_holes;
58
59 if (pgn1.size() > pgn2.size())
60 mink_sum(pgn1, pgn2, sum_bound, std::back_inserter(sum_holes));
61 else mink_sum(pgn2, pgn1, sum_bound, std::back_inserter(sum_holes));
62
63 return (Polygon_with_holes_2<Kernel,Container>(sum_bound,
64 sum_holes.begin(),
65 sum_holes.end()));
66 }
67
68 /*!
69 * Computes the Minkowski sum \f$ P \oplus Q\f$ of two given polygons with
70 * holes.
71 * The function computes the reduced convolution of the two polygons and
72 * extracts those loops of the convolution which are part of the Minkowsi
73 * sum. This method works very efficiently, regardless of whether `P` and
74 * `Q` are convex or non-convex.
75 * The result is also represented as a polygon with holes.
76 * \param[in] pgn1 The first polygon.
77 * \param[in] pgn2 The second polygon.
78 */
79 template <typename Kernel_, typename Container_>
80 Polygon_with_holes_2<Kernel_, Container_>
minkowski_sum_by_reduced_convolution_2(const Polygon_with_holes_2<Kernel_,Container_> & pgn1,const Polygon_with_holes_2<Kernel_,Container_> & pgn2)81 minkowski_sum_by_reduced_convolution_2
82 (const Polygon_with_holes_2<Kernel_, Container_>& pgn1,
83 const Polygon_with_holes_2<Kernel_, Container_>& pgn2)
84 {
85 typedef Kernel_ Kernel;
86 typedef Container_ Container;
87
88 Hole_filter_2<Kernel, Container> hole_filter;
89
90 Polygon_with_holes_2<Kernel, Container> filtered_pgn1;
91 Polygon_with_holes_2<Kernel, Container> filtered_pgn2;
92
93 hole_filter(pgn1, pgn2, filtered_pgn1);
94 hole_filter(pgn2, pgn1, filtered_pgn2);
95
96 Minkowski_sum_by_reduced_convolution_2<Kernel, Container> mink_sum;
97 Polygon_2<Kernel, Container> sum_bound;
98 std::list<Polygon_2<Kernel, Container> > sum_holes;
99
100 mink_sum(filtered_pgn1, filtered_pgn2, sum_bound,
101 std::back_inserter(sum_holes));
102
103 return (Polygon_with_holes_2<Kernel,Container>(sum_bound,
104 sum_holes.begin(),
105 sum_holes.end()));
106 }
107
108 /*!
109 * Computes the Minkowski sum \f$ P \oplus Q\f$ of a simple polygon and a
110 * polygon with holes.
111 * The function computes the reduced convolution of the two polygons and
112 * extracts those loops of the convolution which are part of the Minkowsi
113 * sum. This method works very efficiently, regardless of whether `P` and
114 * `Q` are convex or non-convex.
115 * The result is also represented as a polygon with holes.
116 * \param[in] pgn1 The simple polygon.
117 * \param[in] pgn2 The polygon with holes.
118 */
119 template <typename Kernel_, typename Container_>
120 Polygon_with_holes_2<Kernel_, Container_>
minkowski_sum_by_reduced_convolution_2(const Polygon_2<Kernel_,Container_> & pgn1,const Polygon_with_holes_2<Kernel_,Container_> & pgn2)121 minkowski_sum_by_reduced_convolution_2
122 (const Polygon_2<Kernel_, Container_>& pgn1,
123 const Polygon_with_holes_2<Kernel_, Container_>& pgn2)
124 {
125 typedef Kernel_ Kernel;
126 typedef Container_ Container;
127
128 Hole_filter_2<Kernel, Container> hole_filter;
129 Polygon_with_holes_2<Kernel, Container> filtered_pgn2;
130 hole_filter(pgn2, pgn1, filtered_pgn2);
131 Minkowski_sum_by_reduced_convolution_2<Kernel, Container> mink_sum;
132 Polygon_2<Kernel, Container> sum_bound;
133 std::list<Polygon_2<Kernel, Container> > sum_holes;
134 mink_sum(pgn1, filtered_pgn2, sum_bound, std::back_inserter(sum_holes));
135 return (Polygon_with_holes_2<Kernel,Container>(sum_bound,
136 sum_holes.begin(),
137 sum_holes.end()));
138 }
139
140 /*!
141 * Computes the Minkowski sum \f$ P \oplus Q\f$ of a simple polygon and a
142 * polygon with holes.
143 * The function computes the reduced convolution of the two polygons and
144 * extracts those loops of the convolution which are part of the Minkowsi
145 * sum. This method works very efficiently, regardless of whether `P` and
146 * `Q` are convex or non-convex.
147 * The result is also represented as a polygon with holes.
148 * \param[in] pgn1 The polygon with holes.
149 * \param[in] pgn2 The simple polygon.
150 */
151 template <typename Kernel_, typename Container_>
152 Polygon_with_holes_2<Kernel_, Container_>
minkowski_sum_by_reduced_convolution_2(const Polygon_with_holes_2<Kernel_,Container_> & pgn1,const Polygon_2<Kernel_,Container_> & pgn2)153 minkowski_sum_by_reduced_convolution_2
154 (const Polygon_with_holes_2<Kernel_, Container_>& pgn1,
155 const Polygon_2<Kernel_, Container_>& pgn2)
156 { return minkowski_sum_by_reduced_convolution_2(pgn2, pgn1); }
157
158 /*!
159 * Compute the Minkowski sum of two simple polygons using the (full)
160 * convolution method.
161 * Note that as the input polygons may not be convex, their Minkowski sum may
162 * not be a simple polygon. The result is therefore represented as a polygon
163 * with holes.
164 * \param[in] pgn1 The first polygon.
165 * \param[in] pgn2 The second polygon.
166 * \return The resulting polygon with holes, representing the sum.
167 */
168 template <typename Kernel_, typename Container_>
169 Polygon_with_holes_2<Kernel_, Container_>
minkowski_sum_by_full_convolution_2(const Polygon_2<Kernel_,Container_> & pgn1,const Polygon_2<Kernel_,Container_> & pgn2)170 minkowski_sum_by_full_convolution_2(const Polygon_2<Kernel_, Container_>& pgn1,
171 const Polygon_2<Kernel_, Container_>& pgn2)
172 {
173 typedef Kernel_ Kernel;
174 typedef Container_ Container;
175
176 Minkowski_sum_by_convolution_2<Kernel, Container> mink_sum;
177 Polygon_2<Kernel, Container> sum_bound;
178 std::list<Polygon_2<Kernel, Container> > sum_holes;
179
180 if (pgn1.size() > pgn2.size())
181 mink_sum(pgn1, pgn2, sum_bound, std::back_inserter(sum_holes));
182 else mink_sum(pgn2, pgn1, sum_bound, std::back_inserter(sum_holes));
183 return (Polygon_with_holes_2<Kernel, Container>(sum_bound,
184 sum_holes.begin(),
185 sum_holes.end()));
186 }
187
188 /*!
189 * Compute the Minkowski sum of two simple polygons using the convolution
190 * method. This function defaults to calling the reduced convolution method,
191 * as it is more efficient in most cases.
192 * Note that as the input polygons may not be convex, their Minkowski sum may
193 * not be a simple polygon. The result is therefore represented as a polygon
194 * with holes.
195 * \param[in] pgn1 The first polygon.
196 * \param[in] pgn2 The second polygon.
197 * \return The resulting polygon with holes, representing the sum.
198 *
199 * \sa `CGAL::minkowski_sum_by_reduced_convolution_2()`
200 * \sa `CGAL::minkowski_sum_by_full_convolution_2()`
201 */
202 template <typename Kernel_, typename Container_>
203 Polygon_with_holes_2<Kernel_, Container_>
minkowski_sum_2(const Polygon_2<Kernel_,Container_> & pgn1,const Polygon_2<Kernel_,Container_> & pgn2)204 minkowski_sum_2(const Polygon_2<Kernel_, Container_>& pgn1,
205 const Polygon_2<Kernel_, Container_>& pgn2)
206 { return minkowski_sum_by_reduced_convolution_2(pgn1, pgn2); }
207
208 /*!
209 * Compute the Minkowski sum of two polygons with holes using the convolution
210 * method. This function defaults to calling the reduced convolution method,
211 * as it is more efficient in most cases.
212 * Note that the result may not be a simple polygon. The result is therefore
213 * represented as a polygon with holes.
214 * \param[in] pgn1 The first polygon with holes.
215 * \param[in] pgn2 The second polygon with holes.
216 * \return The resulting polygon with holes, representing the sum.
217 *
218 * \sa `CGAL::minkowski_sum_by_reduced_convolution_2()`
219 * \sa `CGAL::minkowski_sum_by_full_convolution_2()`
220 */
221 template <typename Kernel_, typename Container_>
222 Polygon_with_holes_2<Kernel_, Container_>
minkowski_sum_2(const Polygon_with_holes_2<Kernel_,Container_> & pgn1,const Polygon_with_holes_2<Kernel_,Container_> & pgn2)223 minkowski_sum_2(const Polygon_with_holes_2<Kernel_, Container_>& pgn1,
224 const Polygon_with_holes_2<Kernel_, Container_>& pgn2)
225 { return minkowski_sum_by_reduced_convolution_2(pgn1, pgn2); }
226
227 /*!
228 * Compute the Minkowski sum of a simple polygon and a polygon with holes
229 * using the convolution method. This function defaults to calling the reduced
230 * convolution method, as it is more efficient in most cases.
231 * Note that the result may not be a simple polygon. The result is therefore
232 * represented as a polygon with holes.
233 * \param[in] pgn1 The simple polygon.
234 * \param[in] pgn2 The polygon with holes.
235 * \return The resulting polygon with holes, representing the sum.
236 *
237 * \sa `CGAL::minkowski_sum_by_reduced_convolution_2()`
238 * \sa `CGAL::minkowski_sum_by_full_convolution_2()`
239 */
240 template <typename Kernel_, typename Container_>
241 Polygon_with_holes_2<Kernel_, Container_>
minkowski_sum_2(const Polygon_2<Kernel_,Container_> & pgn1,const Polygon_with_holes_2<Kernel_,Container_> & pgn2)242 minkowski_sum_2(const Polygon_2<Kernel_, Container_>& pgn1,
243 const Polygon_with_holes_2<Kernel_, Container_>& pgn2)
244 { return minkowski_sum_by_reduced_convolution_2(pgn1, pgn2); }
245
246 /*!
247 * Compute the Minkowski sum of a simple polygon and a polygon with holes
248 * using the convolution method. This function defaults to calling the reduced
249 * convolution method, as it is more efficient in most cases.
250 * Note that the result may not be a simple polygon. The result is therefore
251 * represented as a polygon with holes.
252 * \param[in] pgn1 The polygon with holes.
253 * \param[in] pgn2 The simple polygon.
254 * \return The resulting polygon with holes, representing the sum.
255 *
256 * \sa `CGAL::minkowski_sum_by_reduced_convolution_2()`
257 * \sa `CGAL::minkowski_sum_by_full_convolution_2()`
258 */
259 template <typename Kernel_, typename Container_>
260 Polygon_with_holes_2<Kernel_, Container_>
minkowski_sum_2(const Polygon_with_holes_2<Kernel_,Container_> & pgn1,const Polygon_2<Kernel_,Container_> & pgn2)261 minkowski_sum_2(const Polygon_with_holes_2<Kernel_, Container_>& pgn1,
262 const Polygon_2<Kernel_, Container_>& pgn2)
263 { return minkowski_sum_by_reduced_convolution_2(pgn1, pgn2); }
264
265 /*!
266 * \defgroup Minkowski sum by decomposition
267 * @{
268 */
269
270 /*! Compute the Minkowski sum of two simple polygons by decomposing each
271 * polygon to convex sub-polygons and computing the union of the pairwise
272 * Minkowski sums of the sub-polygons.
273 * Note that as the input polygons may not be convex, their Minkowski sum may
274 * not be a simple polygon. The result is therefore represented as a polygon
275 * with holes.
276 * \param[in] pgn1 The first polygon.
277 * \param[in] pgn2 The second polygon.
278 * \param[in] decomposition_strategy A functor for decomposing polygons.
279 * \return The resulting polygon with holes, representing the sum.
280 */
281 template <typename Kernel_, typename Container_,
282 typename DecompositionStrategy1_, typename DecompositionStrategy2_>
283 Polygon_with_holes_2<Kernel_, Container_>
minkowski_sum_2(const Polygon_2<Kernel_,Container_> & pgn1,const Polygon_2<Kernel_,Container_> & pgn2,const DecompositionStrategy1_ & decomposition_strategy1,const DecompositionStrategy2_ & decomposition_strategy2)284 minkowski_sum_2(const Polygon_2<Kernel_, Container_>& pgn1,
285 const Polygon_2<Kernel_, Container_>& pgn2,
286 const DecompositionStrategy1_& decomposition_strategy1,
287 const DecompositionStrategy2_& decomposition_strategy2)
288 {
289 typename Minkowski_sum_by_decomposition_2<DecompositionStrategy1_,
290 DecompositionStrategy2_,
291 Container_>::Traits_2 traits;
292 return minkowski_sum_2(pgn1, pgn2,
293 decomposition_strategy1, decomposition_strategy2,
294 traits);
295 }
296
297 /*! Compute the Minkowski sum of two simple polygons by decomposing each
298 * polygon to convex sub-polygons and computing the union of the pairwise
299 * Minkowski sums of the sub-polygons.
300 * Note that as the input polygons may not be convex, their Minkowski sum may
301 * not be a simple polygon. The result is therefore represented as a polygon
302 * with holes.
303 * \param[in] pgn1 The first polygon.
304 * \param[in] pgn2 The second polygon.
305 * \param[in] decomposition_strategy A functor for decomposing polygons.
306 * \param[in] traits The traits.
307 * \return The resulting polygon with holes, representing the sum.
308 *
309 * The type of the last argument, namely,
310 * Gps_segment_traits_2<Kernel_, Container_>
311 * and the type
312 * const typename Minkowski_sum_by_decomposition_2<DecompositionStrategy1_,
313 * DecompositionStrategy2_,
314 * Container_>::Traits_2>
315 * are exchangeable except for in one case, where there is an ambiguity.
316 * Thus, we use the former, even though it is less generic, as change to the
317 * traits type in Minkowski_sum_by_decomposition_2 would require a similar
318 * change here.
319 */
320 template <typename Kernel_, typename Container_,
321 typename DecompositionStrategy1_, typename DecompositionStrategy2_>
322 Polygon_with_holes_2<Kernel_, Container_>
minkowski_sum_2(const Polygon_2<Kernel_,Container_> & pgn1,const Polygon_2<Kernel_,Container_> & pgn2,const DecompositionStrategy1_ & decomposition_strategy1,const DecompositionStrategy2_ & decomposition_strategy2,const Gps_segment_traits_2<Kernel_,Container_> & traits)323 minkowski_sum_2(const Polygon_2<Kernel_, Container_>& pgn1,
324 const Polygon_2<Kernel_, Container_>& pgn2,
325 const DecompositionStrategy1_& decomposition_strategy1,
326 const DecompositionStrategy2_& decomposition_strategy2,
327 const Gps_segment_traits_2<Kernel_, Container_>& traits)
328 {
329 typedef Container_ Container;
330 typedef DecompositionStrategy1_ Decomposition_strategy1;
331 typedef DecompositionStrategy2_ Decomposition_strategy2;
332
333 Minkowski_sum_by_decomposition_2<Decomposition_strategy1,
334 Decomposition_strategy2, Container>
335 mink_sum(decomposition_strategy1, decomposition_strategy2, traits);
336 return mink_sum(pgn1, pgn2);
337 }
338
339 /*!
340 * Compute the Minkowski sum of two polygon with holes by decomposing each
341 * polygon to convex sub-polygons and computing the union of the pairwise
342 * Minkowski sums of the sub-polygons.
343 * The result is also represented as a polygon with holes.
344 * \param[in] pgn1 The first polygon.
345 * \param[in] pgn2 The second polygon.
346 * \param[in] decomposition_strategy A functor for decomposing polygons.
347 * \return The resulting polygon with holes, representing the sum.
348 */
349 template <typename Kernel_, typename Container_,
350 typename DecompositionStrategy1_, typename DecompositionStrategy2_>
351 Polygon_with_holes_2<Kernel_, Container_>
minkowski_sum_2(const Polygon_with_holes_2<Kernel_,Container_> & pgn1,const Polygon_with_holes_2<Kernel_,Container_> & pgn2,const DecompositionStrategy1_ & decomposition_strategy1,const DecompositionStrategy2_ & decomposition_strategy2)352 minkowski_sum_2(const Polygon_with_holes_2<Kernel_, Container_>& pgn1,
353 const Polygon_with_holes_2<Kernel_, Container_>& pgn2,
354 const DecompositionStrategy1_& decomposition_strategy1,
355 const DecompositionStrategy2_& decomposition_strategy2)
356 {
357 typename Minkowski_sum_by_decomposition_2<DecompositionStrategy1_,
358 DecompositionStrategy2_,
359 Container_>::Traits_2 traits;
360 return minkowski_sum_2(pgn1, pgn2,
361 decomposition_strategy1, decomposition_strategy2,
362 traits);
363 }
364
365 /*! Compute the Minkowski sum of two polygon with holes by decomposing each
366 * polygon to convex sub-polygons and computing the union of the pairwise
367 * Minkowski sums of the sub-polygons.
368 * The result is also represented as a polygon with holes.
369 * \param[in] pgn1 The first polygon.
370 * \param[in] pgn2 The second polygon.
371 * \param[in] decomposition_strategy A functor for decomposing polygons.
372 * \param[in] traits The traits.
373 * \return The resulting polygon with holes, representing the sum.
374 */
375 template <typename Kernel_, typename Container_,
376 typename DecompositionStrategy1_, typename DecompositionStrategy2_>
377 Polygon_with_holes_2<Kernel_, Container_>
minkowski_sum_2(const Polygon_with_holes_2<Kernel_,Container_> & pgn1,const Polygon_with_holes_2<Kernel_,Container_> & pgn2,const DecompositionStrategy1_ & decomposition_strategy1,const DecompositionStrategy2_ & decomposition_strategy2,const Gps_segment_traits_2<Kernel_,Container_> & traits)378 minkowski_sum_2(const Polygon_with_holes_2<Kernel_, Container_>& pgn1,
379 const Polygon_with_holes_2<Kernel_, Container_>& pgn2,
380 const DecompositionStrategy1_& decomposition_strategy1,
381 const DecompositionStrategy2_& decomposition_strategy2,
382 const Gps_segment_traits_2<Kernel_, Container_>& traits)
383 {
384 typedef Kernel_ Kernel;
385 typedef Container_ Container;
386 typedef DecompositionStrategy1_ Decomposition_strategy1;
387 typedef DecompositionStrategy2_ Decomposition_strategy2;
388
389 Minkowski_sum_by_decomposition_2<Decomposition_strategy1,
390 Decomposition_strategy2, Container>
391 mink_sum(decomposition_strategy1, decomposition_strategy2, traits);
392 Hole_filter_2<Kernel, Container> hole_filter;
393 Polygon_with_holes_2<Kernel,Container> filtered_pgn1;
394 Polygon_with_holes_2<Kernel,Container> filtered_pgn2;
395 hole_filter(pgn1, pgn2, filtered_pgn1);
396 hole_filter(pgn2, pgn1, filtered_pgn2);
397 return mink_sum(filtered_pgn1, filtered_pgn2);
398 }
399
400 /*! Compute the Minkowski sum of a simple polygon and a polygon with holes
401 * by decomposing each polygon to convex sub-polygons and computing the union
402 * of the pairwise Minkowski sums of the sub-polygons. The result is also
403 * represented as a polygon with holes.
404 * \param[in] pgn1 The first polygon.
405 * \param[in] pgn2 The second polygon.
406 * \param[in] decomposition_strategy A functor for decomposing polygons.
407 * \return The resulting polygon with holes, representing the sum.
408 */
409 template <typename Kernel_, typename Container_,
410 typename DecompositionStrategy1_, typename DecompositionStrategy2_>
411 Polygon_with_holes_2<Kernel_, Container_>
minkowski_sum_2(const Polygon_2<Kernel_,Container_> & pgn1,const Polygon_with_holes_2<Kernel_,Container_> & pgn2,const DecompositionStrategy1_ & decomposition_strategy1,const DecompositionStrategy2_ & decomposition_strategy2)412 minkowski_sum_2(const Polygon_2<Kernel_, Container_>& pgn1,
413 const Polygon_with_holes_2<Kernel_, Container_>& pgn2,
414 const DecompositionStrategy1_& decomposition_strategy1,
415 const DecompositionStrategy2_& decomposition_strategy2)
416 {
417 typename Minkowski_sum_by_decomposition_2<DecompositionStrategy1_,
418 DecompositionStrategy2_,
419 Container_>::Traits_2 traits;
420 return minkowski_sum_2(pgn1, pgn2,
421 decomposition_strategy1, decomposition_strategy2,
422 traits);
423 }
424
425 /*! Compute the Minkowski sum of a simple polygon and a polygon with holes
426 * by decomposing each polygon to convex sub-polygons and computing the union
427 * of the pairwise Minkowski sums of the sub-polygons. The result is also
428 * represented as a polygon with holes.
429 * \param[in] pgn1 The simple polygon.
430 * \param[in] pgn2 The polygon with holes.
431 * \param[in] decomposition_strategy A functor for decomposing polygons.
432 * \param[in] traits The traits.
433 * \return The resulting polygon with holes, representing the sum.
434 */
435 template <typename Kernel_, typename Container_,
436 typename DecompositionStrategy1_, typename DecompositionStrategy2_>
437 Polygon_with_holes_2<Kernel_, Container_>
minkowski_sum_2(const Polygon_2<Kernel_,Container_> & pgn1,const Polygon_with_holes_2<Kernel_,Container_> & pgn2,const DecompositionStrategy1_ & decomposition_strategy1,const DecompositionStrategy2_ & decomposition_strategy2,const Gps_segment_traits_2<Kernel_,Container_> & traits)438 minkowski_sum_2(const Polygon_2<Kernel_, Container_>& pgn1,
439 const Polygon_with_holes_2<Kernel_, Container_>& pgn2,
440 const DecompositionStrategy1_& decomposition_strategy1,
441 const DecompositionStrategy2_& decomposition_strategy2,
442 const Gps_segment_traits_2<Kernel_, Container_>& traits)
443 {
444 typedef Kernel_ Kernel;
445 typedef Container_ Container;
446 typedef DecompositionStrategy1_ Decomposition_strategy1;
447 typedef DecompositionStrategy2_ Decomposition_strategy2;
448
449 Minkowski_sum_by_decomposition_2<Decomposition_strategy1,
450 Decomposition_strategy2, Container>
451 mink_sum(decomposition_strategy1, decomposition_strategy2, traits);
452 Hole_filter_2<Kernel, Container> hole_filter;
453 Polygon_with_holes_2<Kernel, Container> filtered_pgn2;
454 hole_filter(pgn2, pgn1, filtered_pgn2);
455 return mink_sum(pgn1, filtered_pgn2);
456 }
457
458 /*! Compute the Minkowski sum of a simple polygon and a polygon with holes
459 * by decomposing each polygon to convex sub-polygons and computing the union
460 * of the pairwise Minkowski sums of the sub-polygons. The result is also
461 * represented as a polygon with holes.
462 * \param[in] pgn1 The second polygon.
463 * \param[in] pgn2 The first polygon.
464 * \param[in] decomposition_strategy A functor for decomposing polygons.
465 * \return The resulting polygon with holes, representing the sum.
466 */
467 template <typename Kernel_, typename Container_,
468 typename DecompositionStrategy1_, typename DecompositionStrategy2_>
469 Polygon_with_holes_2<Kernel_, Container_>
minkowski_sum_2(const Polygon_with_holes_2<Kernel_,Container_> & pgn1,const Polygon_2<Kernel_,Container_> & pgn2,const DecompositionStrategy1_ & decomposition_strategy1,const DecompositionStrategy2_ & decomposition_strategy2)470 minkowski_sum_2(const Polygon_with_holes_2<Kernel_, Container_>& pgn1,
471 const Polygon_2<Kernel_, Container_>& pgn2,
472 const DecompositionStrategy1_& decomposition_strategy1,
473 const DecompositionStrategy2_& decomposition_strategy2)
474 {
475 typename Minkowski_sum_by_decomposition_2<DecompositionStrategy1_,
476 DecompositionStrategy2_,
477 Container_>::Traits_2 traits;
478 return minkowski_sum_2(pgn1, pgn2,
479 decomposition_strategy1, decomposition_strategy2,
480 traits);
481 }
482
483 /*! Compute the Minkowski sum of a simple polygon and a polygon with holes
484 * by decomposing each polygon to convex sub-polygons and computing the union
485 * of the pairwise Minkowski sums of the sub-polygons. The result is also
486 * represented as a polygon with holes.
487 * \param[in] pgn1 The polygon with holes.
488 * \param[in] pgn2 The simple polygon.
489 * \param[in] decomposition_strategy A functor for decomposing polygons.
490 * \param[in] traits The traits.
491 * \return The resulting polygon with holes, representing the sum.
492 */
493 template <typename Kernel_, typename Container_,
494 typename DecompositionStrategy1_, typename DecompositionStrategy2_>
495 Polygon_with_holes_2<Kernel_, Container_>
minkowski_sum_2(const Polygon_with_holes_2<Kernel_,Container_> & pgn1,const Polygon_2<Kernel_,Container_> & pgn2,const DecompositionStrategy1_ & decomposition_strategy1,const DecompositionStrategy2_ & decomposition_strategy2,const Gps_segment_traits_2<Kernel_,Container_> & traits)496 minkowski_sum_2(const Polygon_with_holes_2<Kernel_, Container_>& pgn1,
497 const Polygon_2<Kernel_, Container_>& pgn2,
498 const DecompositionStrategy1_& decomposition_strategy1,
499 const DecompositionStrategy2_& decomposition_strategy2,
500 const Gps_segment_traits_2<Kernel_, Container_>& traits)
501 {
502 return minkowski_sum_2(pgn2, pgn1,
503 decomposition_strategy2, decomposition_strategy1,
504 traits);
505 }
506
507 /*! Compute the Minkowski sum of two simple polygons by decomposing each
508 * polygon to convex sub-polygons and computing the union of the pairwise
509 * Minkowski sums of the sub-polygons.
510 * Note that as the input polygons may not be convex, their Minkowski sum may
511 * not be a simple polygon. The result is therefore represented as a polygon
512 * with holes.
513 * \param[in] pgn1 The first polygon.
514 * \param[in] pgn2 The second polygon.
515 * \param[in] decomposition_strategy A functor for decomposing polygons.
516 * \return The resulting polygon with holes, representing the sum.
517 */
518 template <typename Kernel_, typename Container_,
519 typename DecompositionStrategy1_>
520 Polygon_with_holes_2<Kernel_, Container_>
minkowski_sum_2(const Polygon_2<Kernel_,Container_> & pgn1,const Polygon_2<Kernel_,Container_> & pgn2,const DecompositionStrategy1_ & decomposition_strategy1)521 minkowski_sum_2(const Polygon_2<Kernel_, Container_>& pgn1,
522 const Polygon_2<Kernel_, Container_>& pgn2,
523 const DecompositionStrategy1_& decomposition_strategy1)
524 {
525 typename Minkowski_sum_by_decomposition_2<DecompositionStrategy1_,
526 DecompositionStrategy1_,
527 Container_>::Traits_2 traits;
528 return minkowski_sum_2(pgn1, pgn2,
529 decomposition_strategy1, decomposition_strategy1,
530 traits);
531 }
532
533 /*! Compute the Minkowski sum of two simple polygons by decomposing each
534 * polygon to convex sub-polygons and computing the union of the pairwise
535 * Minkowski sums of the sub-polygons.
536 * Note that as the input polygons may not be convex, their Minkowski sum may
537 * not be a simple polygon. The result is therefore represented as a polygon
538 * with holes.
539 * \param[in] pgn1 The first polygon.
540 * \param[in] pgn2 The second polygon.
541 * \param[in] decomposition_strategy A functor for decomposing polygons.
542 * \param[in] traits The traits.
543 * \return The resulting polygon with holes, representing the sum.
544 */
545 template <typename Kernel_, typename Container_,
546 typename DecompositionStrategy1_>
547 Polygon_with_holes_2<Kernel_, Container_>
minkowski_sum_2(const Polygon_2<Kernel_,Container_> & pgn1,const Polygon_2<Kernel_,Container_> & pgn2,const DecompositionStrategy1_ & decomposition_strategy1,const Gps_segment_traits_2<Kernel_,Container_> & traits)548 minkowski_sum_2(const Polygon_2<Kernel_, Container_>& pgn1,
549 const Polygon_2<Kernel_, Container_>& pgn2,
550 const DecompositionStrategy1_& decomposition_strategy1,
551 const Gps_segment_traits_2<Kernel_, Container_>& traits)
552 {
553 typedef Container_ Container;
554 typedef DecompositionStrategy1_ Decomposition_strategy1;
555
556 Minkowski_sum_by_decomposition_2<Decomposition_strategy1,
557 Decomposition_strategy1, Container>
558 mink_sum(decomposition_strategy1, decomposition_strategy1, traits);
559 return mink_sum(pgn1, pgn2);
560 }
561
562 /*!
563 * Compute the Minkowski sum of two polygon with holes by decomposing each
564 * polygon to convex sub-polygons and computing the union of the pairwise
565 * Minkowski sums of the sub-polygons.
566 * The result is also represented as a polygon with holes.
567 * \param[in] pgn1 The first polygon.
568 * \param[in] pgn2 The second polygon.
569 * \param[in] decomposition_strategy A functor for decomposing polygons.
570 * \return The resulting polygon with holes, representing the sum.
571 */
572 template <typename Kernel_, typename Container_,
573 typename DecompositionStrategy1_>
574 Polygon_with_holes_2<Kernel_, Container_>
minkowski_sum_2(const Polygon_with_holes_2<Kernel_,Container_> & pgn1,const Polygon_with_holes_2<Kernel_,Container_> & pgn2,const DecompositionStrategy1_ & decomposition_strategy1)575 minkowski_sum_2(const Polygon_with_holes_2<Kernel_, Container_>& pgn1,
576 const Polygon_with_holes_2<Kernel_, Container_>& pgn2,
577 const DecompositionStrategy1_& decomposition_strategy1)
578 {
579 typename Minkowski_sum_by_decomposition_2<DecompositionStrategy1_,
580 DecompositionStrategy1_,
581 Container_>::Traits_2 traits;
582 return minkowski_sum_2(pgn1, pgn2,
583 decomposition_strategy1, decomposition_strategy1,
584 traits);
585 }
586
587 /*! Compute the Minkowski sum of two polygon with holes by decomposing each
588 * polygon to convex sub-polygons and computing the union of the pairwise
589 * Minkowski sums of the sub-polygons.
590 * The result is also represented as a polygon with holes.
591 * \param[in] pgn1 The first polygon.
592 * \param[in] pgn2 The second polygon.
593 * \param[in] decomposition_strategy A functor for decomposing polygons.
594 * \param[in] traits The traits.
595 * \return The resulting polygon with holes, representing the sum.
596 */
597 template <typename Kernel_, typename Container_,
598 typename DecompositionStrategy1_>
599 Polygon_with_holes_2<Kernel_, Container_>
minkowski_sum_2(const Polygon_with_holes_2<Kernel_,Container_> & pgn1,const Polygon_with_holes_2<Kernel_,Container_> & pgn2,const DecompositionStrategy1_ & decomposition_strategy1,const Gps_segment_traits_2<Kernel_,Container_> & traits)600 minkowski_sum_2(const Polygon_with_holes_2<Kernel_, Container_>& pgn1,
601 const Polygon_with_holes_2<Kernel_, Container_>& pgn2,
602 const DecompositionStrategy1_& decomposition_strategy1,
603 const Gps_segment_traits_2<Kernel_, Container_>& traits)
604 {
605 typedef Kernel_ Kernel;
606 typedef Container_ Container;
607 typedef DecompositionStrategy1_ Decomposition_strategy1;
608
609 Minkowski_sum_by_decomposition_2<Decomposition_strategy1,
610 Decomposition_strategy1, Container>
611 mink_sum(decomposition_strategy1, decomposition_strategy1, traits);
612 Hole_filter_2<Kernel, Container> hole_filter;
613 Polygon_with_holes_2<Kernel,Container> filtered_pgn1;
614 Polygon_with_holes_2<Kernel,Container> filtered_pgn2;
615 hole_filter(pgn1, pgn2, filtered_pgn1);
616 hole_filter(pgn2, pgn1, filtered_pgn2);
617 return mink_sum(filtered_pgn1, filtered_pgn2);
618 }
619
620 /*! Compute the Minkowski sum of a simple polygon and a polygon with holes
621 * by decomposing each polygon to convex sub-polygons and computing the union
622 * of the pairwise Minkowski sums of the sub-polygons. The result is also
623 * represented as a polygon with holes.
624 * \param[in] pgn1 The first polygon.
625 * \param[in] pgn2 The second polygon.
626 * \param[in] decomposition_strategy A functor for decomposing polygons.
627 * \return The resulting polygon with holes, representing the sum.
628 */
629 template <typename Kernel_, typename Container_,
630 typename DecompositionStrategy1_>
631 Polygon_with_holes_2<Kernel_, Container_>
minkowski_sum_2(const Polygon_2<Kernel_,Container_> & pgn1,const Polygon_with_holes_2<Kernel_,Container_> & pgn2,const DecompositionStrategy1_ & decomposition_strategy1)632 minkowski_sum_2(const Polygon_2<Kernel_, Container_>& pgn1,
633 const Polygon_with_holes_2<Kernel_, Container_>& pgn2,
634 const DecompositionStrategy1_& decomposition_strategy1)
635 {
636 typename Minkowski_sum_by_decomposition_2<DecompositionStrategy1_,
637 DecompositionStrategy1_,
638 Container_>::Traits_2 traits;
639 return minkowski_sum_2(pgn1, pgn2,
640 decomposition_strategy1, decomposition_strategy1,
641 traits);
642 }
643
644 /*! Compute the Minkowski sum of a simple polygon and a polygon with holes
645 * by decomposing each polygon to convex sub-polygons and computing the union
646 * of the pairwise Minkowski sums of the sub-polygons. The result is also
647 * represented as a polygon with holes.
648 * \param[in] pgn1 The simple polygon.
649 * \param[in] pgn2 The polygon with holes.
650 * \param[in] decomposition_strategy A functor for decomposing polygons.
651 * \param[in] traits The traits.
652 * \return The resulting polygon with holes, representing the sum.
653 */
654 template <typename Kernel_, typename Container_,
655 typename DecompositionStrategy1_>
656 Polygon_with_holes_2<Kernel_, Container_>
minkowski_sum_2(const Polygon_2<Kernel_,Container_> & pgn1,const Polygon_with_holes_2<Kernel_,Container_> & pgn2,const DecompositionStrategy1_ & decomposition_strategy1,const Gps_segment_traits_2<Kernel_,Container_> & traits)657 minkowski_sum_2(const Polygon_2<Kernel_, Container_>& pgn1,
658 const Polygon_with_holes_2<Kernel_, Container_>& pgn2,
659 const DecompositionStrategy1_& decomposition_strategy1,
660 const Gps_segment_traits_2<Kernel_, Container_>& traits)
661 {
662 typedef Kernel_ Kernel;
663 typedef Container_ Container;
664 typedef DecompositionStrategy1_ Decomposition_strategy1;
665
666 Minkowski_sum_by_decomposition_2<Decomposition_strategy1,
667 Decomposition_strategy1, Container>
668 mink_sum(decomposition_strategy1, decomposition_strategy1, traits);
669 Hole_filter_2<Kernel, Container> hole_filter;
670 Polygon_with_holes_2<Kernel,Container> filtered_pgn2;
671 hole_filter(pgn2, pgn1, filtered_pgn2);
672 return mink_sum(pgn1, filtered_pgn2);
673 }
674
675 /*! Compute the Minkowski sum of a simple polygon and a polygon with holes
676 * by decomposing each polygon to convex sub-polygons and computing the union
677 * of the pairwise Minkowski sums of the sub-polygons. The result is also
678 * represented as a polygon with holes.
679 * \param[in] pgn1 The second polygon.
680 * \param[in] pgn2 The first polygon.
681 * \param[in] decomposition_strategy A functor for decomposing polygons.
682 * \return The resulting polygon with holes, representing the sum.
683 */
684 template <typename Kernel_, typename Container_,
685 typename DecompositionStrategy1_>
686 Polygon_with_holes_2<Kernel_, Container_>
minkowski_sum_2(const Polygon_with_holes_2<Kernel_,Container_> & pgn1,const Polygon_2<Kernel_,Container_> & pgn2,const DecompositionStrategy1_ & decomposition_strategy1)687 minkowski_sum_2(const Polygon_with_holes_2<Kernel_, Container_>& pgn1,
688 const Polygon_2<Kernel_, Container_>& pgn2,
689 const DecompositionStrategy1_& decomposition_strategy1)
690 {
691 typename Minkowski_sum_by_decomposition_2<DecompositionStrategy1_,
692 DecompositionStrategy1_,
693 Container_>::Traits_2 traits;
694 return minkowski_sum_2(pgn1, pgn2,
695 decomposition_strategy1, decomposition_strategy1,
696 traits);
697 }
698
699 /*! Compute the Minkowski sum of a simple polygon and a polygon with holes
700 * by decomposing each polygon to convex sub-polygons and computing the union
701 * of the pairwise Minkowski sums of the sub-polygons. The result is also
702 * represented as a polygon with holes.
703 * \param[in] pgn1 The polygon with holes.
704 * \param[in] pgn2 The simple polygon.
705 * \param[in] decomposition_strategy A functor for decomposing polygons.
706 * \param[in] traits The traits.
707 * \return The resulting polygon with holes, representing the sum.
708 */
709 template <typename Kernel_, typename Container_,
710 typename DecompositionStrategy1_>
711 Polygon_with_holes_2<Kernel_, Container_>
minkowski_sum_2(const Polygon_with_holes_2<Kernel_,Container_> & pgn1,const Polygon_2<Kernel_,Container_> & pgn2,const DecompositionStrategy1_ & decomposition_strategy1,const Gps_segment_traits_2<Kernel_,Container_> & traits)712 minkowski_sum_2(const Polygon_with_holes_2<Kernel_, Container_>& pgn1,
713 const Polygon_2<Kernel_, Container_>& pgn2,
714 const DecompositionStrategy1_& decomposition_strategy1,
715 const Gps_segment_traits_2<Kernel_, Container_>& traits)
716 {
717 return minkowski_sum_2(pgn2, pgn1,
718 decomposition_strategy1, decomposition_strategy1,
719 traits);
720 }
721
722 /*! Compute the Minkowski sum of two simple polygons by decomposing each
723 * polygon to convex sub-polygons and computing the union of the pairwise
724 * Minkowski sums of the sub-polygons.
725 * Note that as the input polygons may not be convex, their Minkowski sum may
726 * not be a simple polygon. The result is therefore represented as a polygon
727 * with holes.
728 * \param[in] pgn1 The first polygon.
729 * \param[in] pgn2 The second polygon.
730 * \param[in] decomposition_strategy A functor for decomposing polygons.
731 * \return The resulting polygon with holes, representing the sum.
732 */
733 template <typename Kernel_, typename Container_, typename Decomposition_>
734 Polygon_with_holes_2<Kernel_, Container_>
minkowski_sum_by_decomposition_2(const Polygon_2<Kernel_,Container_> & pgn1,const Polygon_2<Kernel_,Container_> & pgn2,const Decomposition_ & decomp)735 minkowski_sum_by_decomposition_2(const Polygon_2<Kernel_, Container_>& pgn1,
736 const Polygon_2<Kernel_, Container_>& pgn2,
737 const Decomposition_& decomp)
738 {
739 typename Minkowski_sum_by_decomposition_2<Decomposition_, Decomposition_,
740 Container_>::Traits_2 traits;
741 return minkowski_sum_by_decomposition_2(pgn1, pgn2, decomp, traits);
742 }
743
744 /*! Compute the Minkowski sum of two simple polygons by decomposing each
745 * polygon to convex sub-polygons and computing the union of the pairwise
746 * Minkowski sums of the sub-polygons.
747 * Note that as the input polygons may not be convex, their Minkowski sum may
748 * not be a simple polygon. The result is therefore represented as a polygon
749 * with holes.
750 * \param[in] pgn1 The first polygon.
751 * \param[in] pgn2 The second polygon.
752 * \param[in] decomposition A functor for decomposing polygons.
753 * \param[in] traits The traits.
754 * \return The resulting polygon with holes, representing the sum.
755 */
756 template <typename Kernel_, typename Container_, typename Decomposition_>
757 Polygon_with_holes_2<Kernel_, Container_>
minkowski_sum_by_decomposition_2(const Polygon_2<Kernel_,Container_> & pgn1,const Polygon_2<Kernel_,Container_> & pgn2,const Decomposition_ & decomp,const Gps_segment_traits_2<Kernel_,Container_> & traits)758 minkowski_sum_by_decomposition_2
759 (const Polygon_2<Kernel_, Container_>& pgn1,
760 const Polygon_2<Kernel_, Container_>& pgn2,
761 const Decomposition_& decomp,
762 const Gps_segment_traits_2<Kernel_, Container_>& traits)
763 {
764 typedef Kernel_ Kernel;
765 typedef Container_ Container;
766 typedef Decomposition_ Decomposition;
767 typedef Polygon_nop_decomposition_2<Kernel> Nop_decomposition;
768
769 if (pgn1.is_convex()) {
770 Nop_decomposition decomp_nop;
771 if (pgn2.is_convex()) {
772 Minkowski_sum_by_decomposition_2<Nop_decomposition, Nop_decomposition,
773 Container>
774 mink_sum(decomp_nop, decomp_nop, traits);
775 return mink_sum(pgn1, pgn2);
776 }
777 Minkowski_sum_by_decomposition_2<Nop_decomposition, Decomposition,
778 Container>
779 mink_sum(decomp_nop, decomp, traits);
780 return mink_sum(pgn1, pgn2);
781 }
782
783 if (pgn2.is_convex()) {
784 Nop_decomposition decomp_nop;
785 Minkowski_sum_by_decomposition_2<Decomposition, Nop_decomposition,
786 Container>
787 mink_sum(decomp, decomp_nop, traits);
788 return mink_sum(pgn1, pgn2);
789 }
790
791 Minkowski_sum_by_decomposition_2<Decomposition, Decomposition, Container>
792 mink_sum(decomp, decomp, traits);
793 return mink_sum(pgn1, pgn2);
794 }
795
796 /*! Compute the Minkowski sum of two polygon with holes by decomposing each
797 * polygon to convex sub-polygons and computing the union of the pairwise
798 * Minkowski sums of the sub-polygons.
799 * The result is also represented as a polygon with holes.
800 * \param[in] pgn1 The first polygon.
801 * \param[in] pgn2 The second polygon.
802 * \param[in] decomposition A functor for decomposing polygons.
803 * \return The resulting polygon with holes, representing the sum.
804 */
805 template <typename Kernel_, typename Container_,
806 typename NoHolesDecomposition_, typename WithHolesDecomposition_>
807 Polygon_with_holes_2<Kernel_, Container_>
minkowski_sum_by_decomposition_2(const Polygon_with_holes_2<Kernel_,Container_> & pgn1,const Polygon_with_holes_2<Kernel_,Container_> & pgn2,const NoHolesDecomposition_ & decomp_no_holes,const WithHolesDecomposition_ & decomp_with_holes)808 minkowski_sum_by_decomposition_2
809 (const Polygon_with_holes_2<Kernel_, Container_>& pgn1,
810 const Polygon_with_holes_2<Kernel_, Container_>& pgn2,
811 const NoHolesDecomposition_& decomp_no_holes,
812 const WithHolesDecomposition_& decomp_with_holes)
813 {
814 typename Minkowski_sum_by_decomposition_2<NoHolesDecomposition_,
815 WithHolesDecomposition_,
816 Container_>::Traits_2 traits;
817 return minkowski_sum_by_decomposition_2(pgn1, pgn2,
818 decomp_no_holes, decomp_with_holes,
819 traits);
820 }
821
822 /*! Compute the Minkowski sum of two polygon with holes by decomposing each
823 * polygon to convex sub-polygons and computing the union of the pairwise
824 * Minkowski sums of the sub-polygons.
825 * The result is also represented as a polygon with holes.
826 * \param[in] pgn1 The first polygon.
827 * \param[in] pgn2 The second polygon.
828 * \param[in] decomposition A functor for decomposing polygons.
829 * \param[in] traits The traits.
830 * \return The resulting polygon with holes, representing the sum.
831 */
832 template <typename Kernel_, typename Container_,
833 typename NoHolesDecomposition_, typename WithHolesDecomposition_>
834 Polygon_with_holes_2<Kernel_, Container_>
minkowski_sum_by_decomposition_2(const Polygon_with_holes_2<Kernel_,Container_> & pgn1,const Polygon_with_holes_2<Kernel_,Container_> & pgn2,const NoHolesDecomposition_ & decomp_no_holes,const WithHolesDecomposition_ & decomp_with_holes,const Gps_segment_traits_2<Kernel_,Container_> & traits)835 minkowski_sum_by_decomposition_2
836 (const Polygon_with_holes_2<Kernel_, Container_>& pgn1,
837 const Polygon_with_holes_2<Kernel_, Container_>& pgn2,
838 const NoHolesDecomposition_& decomp_no_holes,
839 const WithHolesDecomposition_& decomp_with_holes,
840 const Gps_segment_traits_2<Kernel_, Container_>& traits)
841 {
842 typedef Kernel_ Kernel;
843 typedef Container_ Container;
844 typedef NoHolesDecomposition_ No_holes_decomposition;
845 typedef WithHolesDecomposition_ With_holes_decomposition;
846 typedef Polygon_nop_decomposition_2<Kernel> Nop_decomposition;
847
848 Hole_filter_2<Kernel, Container> hole_filter;
849 Polygon_with_holes_2<Kernel, Container> filtered_pgn1;
850 Polygon_with_holes_2<Kernel, Container> filtered_pgn2;
851 hole_filter(pgn1, pgn2, filtered_pgn1);
852 hole_filter(pgn2, pgn1, filtered_pgn2);
853
854 if (0 == filtered_pgn1.number_of_holes()) {
855 const Polygon_2<Kernel, Container>& pnh1 = filtered_pgn1.outer_boundary();
856 if (pnh1.is_convex()) {
857 // pnh1 is convex
858 Nop_decomposition decomp_nop;
859 if (0 == filtered_pgn2.number_of_holes()) {
860 const Polygon_2<Kernel, Container>& pnh2 =
861 filtered_pgn2.outer_boundary();
862 if (pnh2.is_convex()) {
863 // pnh2 is convex
864 Minkowski_sum_by_decomposition_2<Nop_decomposition, Nop_decomposition,
865 Container>
866 mink_sum(decomp_nop, decomp_nop, traits);
867 return mink_sum(pnh1, pnh2);
868 }
869 // pnh2 is concave
870 Minkowski_sum_by_decomposition_2<Nop_decomposition,
871 No_holes_decomposition,
872 Container>
873 mink_sum(decomp_nop, decomp_no_holes, traits);
874 return mink_sum(pnh1, pnh2);
875 }
876 // pnh2 has holes
877 Minkowski_sum_by_decomposition_2<Nop_decomposition,
878 With_holes_decomposition,
879 Container>
880 mink_sum(decomp_nop, decomp_with_holes, traits);
881 return mink_sum(pnh1, filtered_pgn2);
882 }
883 // pnh1 is concave
884 if (0 == filtered_pgn2.number_of_holes()) {
885 const Polygon_2<Kernel, Container>& pnh2 =
886 filtered_pgn2.outer_boundary();
887 if (pnh2.is_convex()) {
888 // pnh2 is convex
889 Nop_decomposition decomp_nop;
890 Minkowski_sum_by_decomposition_2<No_holes_decomposition,
891 Nop_decomposition,
892 Container>
893 mink_sum(decomp_no_holes, decomp_nop, traits);
894 return mink_sum(pnh1, pnh2);
895 }
896 // pnh2 is concave
897 Minkowski_sum_by_decomposition_2<No_holes_decomposition,
898 No_holes_decomposition,
899 Container>
900 mink_sum(decomp_no_holes, decomp_no_holes, traits);
901 return mink_sum(pnh1, pnh2);
902 }
903 // pnh2 has holes
904 Minkowski_sum_by_decomposition_2<No_holes_decomposition,
905 With_holes_decomposition,
906 Container>
907 mink_sum(decomp_no_holes, decomp_with_holes, traits);
908 return mink_sum(pnh1, filtered_pgn2);
909 }
910
911 // filtered_pgn1 has holes
912 if (0 == filtered_pgn2.number_of_holes()) {
913 const Polygon_2<Kernel, Container>& pnh2 =
914 filtered_pgn2.outer_boundary();
915 if (pnh2.is_convex()) {
916 // pnh2 is convex
917 Nop_decomposition decomp_nop;
918 Minkowski_sum_by_decomposition_2<Nop_decomposition,
919 With_holes_decomposition,
920 Container>
921 mink_sum(decomp_nop, decomp_with_holes, traits);
922 return mink_sum(pnh2, filtered_pgn1);
923 }
924 // pnh2 is concave
925 Minkowski_sum_by_decomposition_2<No_holes_decomposition,
926 With_holes_decomposition,
927 Container>
928 mink_sum(decomp_no_holes, decomp_with_holes, traits);
929 return mink_sum(pnh2, filtered_pgn1);
930 }
931 // pnh2 has holes
932 Minkowski_sum_by_decomposition_2<With_holes_decomposition,
933 With_holes_decomposition,
934 Container>
935 mink_sum(decomp_with_holes, decomp_with_holes, traits);
936 return mink_sum(filtered_pgn1, filtered_pgn2);
937 }
938
939 /*! Compute the Minkowski sum of a simple polygon and a polygon with holes
940 * by decomposing each polygon to convex sub-polygons and computing the union
941 * of the pairwise Minkowski sums of the sub-polygons. The result is also
942 * represented as a polygon with holes.
943 * \param[in] pgn1 The first polygon.
944 * \param[in] pgn2 The second polygon.
945 * \param[in] decomposition A functor for decomposing polygons.
946 * \return The resulting polygon with holes, representing the sum.
947 */
948 template <typename Kernel_, typename Container_,
949 typename NoHolesDecomposition_, typename WithHolesDecomposition_>
950 Polygon_with_holes_2<Kernel_, Container_>
minkowski_sum_by_decomposition_2(const Polygon_2<Kernel_,Container_> & pgn1,const Polygon_with_holes_2<Kernel_,Container_> & pgn2,const NoHolesDecomposition_ & decomp_no_holes,const WithHolesDecomposition_ & decomp_with_holes)951 minkowski_sum_by_decomposition_2
952 (const Polygon_2<Kernel_, Container_>& pgn1,
953 const Polygon_with_holes_2<Kernel_, Container_>& pgn2,
954 const NoHolesDecomposition_& decomp_no_holes,
955 const WithHolesDecomposition_& decomp_with_holes)
956 {
957 typename Minkowski_sum_by_decomposition_2<NoHolesDecomposition_,
958 WithHolesDecomposition_,
959 Container_>::Traits_2 traits;
960 return minkowski_sum_by_decomposition_2(pgn1, pgn2,
961 decomp_no_holes, decomp_with_holes,
962 traits);
963 }
964
965 /*! Compute the Minkowski sum of a simple polygon and a polygon with holes
966 * by decomposing each polygon to convex sub-polygons and computing the union
967 * of the pairwise Minkowski sums of the sub-polygons. The result is also
968 * represented as a polygon with holes.
969 * \param[in] pgn1 The simple polygon.
970 * \param[in] pgn2 The polygon with holes.
971 * \param[in] decomposition A functor for decomposing polygons.
972 * \param[in] traits The traits.
973 * \return The resulting polygon with holes, representing the sum.
974 */
975 template <typename Kernel_, typename Container_,
976 typename NoHolesDecomposition_, typename WithHolesDecomposition_>
977 Polygon_with_holes_2<Kernel_, Container_>
minkowski_sum_by_decomposition_2(const Polygon_2<Kernel_,Container_> & pgn1,const Polygon_with_holes_2<Kernel_,Container_> & pgn2,const NoHolesDecomposition_ & decomp_no_holes,const WithHolesDecomposition_ & decomp_with_holes,const Gps_segment_traits_2<Kernel_,Container_> & traits)978 minkowski_sum_by_decomposition_2
979 (const Polygon_2<Kernel_, Container_>& pgn1,
980 const Polygon_with_holes_2<Kernel_, Container_>& pgn2,
981 const NoHolesDecomposition_& decomp_no_holes,
982 const WithHolesDecomposition_& decomp_with_holes,
983 const Gps_segment_traits_2<Kernel_, Container_>& traits)
984 {
985 typedef Kernel_ Kernel;
986 typedef Container_ Container;
987 typedef NoHolesDecomposition_ No_holes_decomposition;
988 typedef WithHolesDecomposition_ With_holes_decomposition;
989 typedef Polygon_nop_decomposition_2<Kernel> Nop_decomposition;
990
991 Hole_filter_2<Kernel, Container> hole_filter;
992 Polygon_with_holes_2<Kernel,Container> filtered_pgn2;
993 hole_filter(pgn2, pgn1, filtered_pgn2);
994
995 if (pgn1.is_convex()) {
996 Nop_decomposition decomp_nop;
997 if (0 == filtered_pgn2.number_of_holes()) {
998 const Polygon_2<Kernel, Container>& pnh2 = filtered_pgn2.outer_boundary();
999 if (pnh2.is_convex()) {
1000 Minkowski_sum_by_decomposition_2<Nop_decomposition, Nop_decomposition,
1001 Container>
1002 mink_sum(decomp_nop, decomp_nop, traits);
1003 return mink_sum(pgn1, pnh2);
1004 }
1005 // pnh2 is concave
1006 Minkowski_sum_by_decomposition_2<Nop_decomposition,
1007 No_holes_decomposition,
1008 Container>
1009 mink_sum(decomp_nop, decomp_no_holes, traits);
1010 return mink_sum(pgn1, pnh2);
1011 }
1012 // pnh2 has holes
1013 Minkowski_sum_by_decomposition_2<Nop_decomposition,
1014 With_holes_decomposition,
1015 Container>
1016 mink_sum(decomp_nop, decomp_with_holes, traits);
1017 return mink_sum(pgn1, filtered_pgn2);
1018 }
1019 // pgn1 is concave
1020 if (0 == filtered_pgn2.number_of_holes()) {
1021 const Polygon_2<Kernel, Container>& pnh2 = filtered_pgn2.outer_boundary();
1022 if (pnh2.is_convex()) {
1023 // pnh2 is convex
1024 Nop_decomposition decomp_nop;
1025 Minkowski_sum_by_decomposition_2<No_holes_decomposition,
1026 Nop_decomposition,
1027 Container>
1028 mink_sum(decomp_no_holes, decomp_nop, traits);
1029 return mink_sum(pgn1, pnh2);
1030 }
1031 // pnh2 is concave
1032 Minkowski_sum_by_decomposition_2<No_holes_decomposition,
1033 No_holes_decomposition,
1034 Container>
1035 mink_sum(decomp_no_holes, decomp_no_holes, traits);
1036 return mink_sum(pgn1, pnh2);
1037 }
1038 // pnh2 has holes
1039 Minkowski_sum_by_decomposition_2<No_holes_decomposition,
1040 With_holes_decomposition,
1041 Container>
1042 mink_sum(decomp_no_holes, decomp_with_holes, traits);
1043 return mink_sum(pgn1, filtered_pgn2);
1044 }
1045
1046 /*! Compute the Minkowski sum of a simple polygon and a polygon with holes
1047 * by decomposing each polygon to convex sub-polygons and computing the union
1048 * of the pairwise Minkowski sums of the sub-polygons. The result is also
1049 * represented as a polygon with holes.
1050 * \param[in] pgn1 The second polygon.
1051 * \param[in] pgn2 The first polygon.
1052 * \param[in] decomposition A functor for decomposing polygons.
1053 * \return The resulting polygon with holes, representing the sum.
1054 */
1055 template <typename Kernel_, typename Container_,
1056 typename NoHolesDecomposition_, typename WithHolesDecomposition_>
1057 Polygon_with_holes_2<Kernel_, Container_>
minkowski_sum_by_decomposition_2(const Polygon_with_holes_2<Kernel_,Container_> & pgn1,const Polygon_2<Kernel_,Container_> & pgn2,const NoHolesDecomposition_ & decomp_no_holes,const WithHolesDecomposition_ & decomp_with_holes)1058 minkowski_sum_by_decomposition_2
1059 (const Polygon_with_holes_2<Kernel_, Container_>& pgn1,
1060 const Polygon_2<Kernel_, Container_>& pgn2,
1061 const NoHolesDecomposition_& decomp_no_holes,
1062 const WithHolesDecomposition_& decomp_with_holes)
1063 {
1064 typename Minkowski_sum_by_decomposition_2<NoHolesDecomposition_,
1065 WithHolesDecomposition_,
1066 Container_>::Traits_2 traits;
1067 return minkowski_sum_by_decomposition_2(pgn1, pgn2,
1068 decomp_no_holes, decomp_with_holes,
1069 traits);
1070 }
1071
1072 /*! Compute the Minkowski sum of a simple polygon and a polygon with holes
1073 * by decomposing each polygon to convex sub-polygons and computing the union
1074 * of the pairwise Minkowski sums of the sub-polygons. The result is also
1075 * represented as a polygon with holes.
1076 * \param[in] pgn1 The polygon with holes.
1077 * \param[in] pgn2 The simple polygon.
1078 * \param[in] decomposition A functor for decomposing polygons.
1079 * \param[in] traits The traits.
1080 * \return The resulting polygon with holes, representing the sum.
1081 */
1082 template <typename Kernel_, typename Container_,
1083 typename NoHoleDecomposition_, typename WithHolesDecomposition_>
1084 Polygon_with_holes_2<Kernel_, Container_>
minkowski_sum_by_decomposition_2(const Polygon_with_holes_2<Kernel_,Container_> & pgn1,const Polygon_2<Kernel_,Container_> & pgn2,const NoHoleDecomposition_ & decomp_no_holes,const WithHolesDecomposition_ & decomp_with_holes,const Gps_segment_traits_2<Kernel_,Container_> & traits)1085 minkowski_sum_by_decomposition_2
1086 (const Polygon_with_holes_2<Kernel_, Container_>& pgn1,
1087 const Polygon_2<Kernel_, Container_>& pgn2,
1088 const NoHoleDecomposition_& decomp_no_holes,
1089 const WithHolesDecomposition_& decomp_with_holes,
1090 const Gps_segment_traits_2<Kernel_, Container_>& traits)
1091 {
1092 return minkowski_sum_by_decomposition_2(pgn2, pgn1,
1093 decomp_no_holes, decomp_with_holes,
1094 traits);
1095 }
1096
1097 /*!@}*/
1098
1099 } //namespace CGAL
1100
1101 #endif
1102