1:45 PM 11/12/2025 ���� JFIF    �� �        "" $(4,$&1'-=-157:::#+?D?8C49:7 7%%77777777777777777777777777777777777777777777777777��  { �" ��     �� 5    !1AQa"q�2��BR��#b�������  ��  ��   ? ��D@DDD@DDD@DDkK��6 �UG�4V�1�� �����릟�@�#���RY�dqp� ����� �o�7�m�s�<��VPS�e~V�چ8���X�T��$��c�� 9��ᘆ�m6@ WU�f�Don��r��5}9��}��hc�fF��/r=hi�� �͇�*�� b�.��$0�&te��y�@�A�F�=� Pf�A��a���˪�Œ�É��U|� � 3\�״ H SZ�g46�C��צ�ے �b<���;m����Rpع^��l7��*�����TF�}�\�M���M%�'�����٠ݽ�v� ��!-�����?�N!La��A+[`#���M����'�~oR�?��v^)��=��h����A��X�.���˃����^Ə��ܯsO"B�c>; �e�4��5�k��/CB��.  �J?��;�҈�������������������~�<�VZ�ꭼ2/)Í”jC���ע�V�G�!���!�F������\�� Kj�R�oc�h���:Þ I��1"2�q×°8��Р@ז���_C0�ր��A��lQ��@纼�!7��F�� �]�sZ B�62r�v�z~�K�7�c��5�.���ӄq&�Z�d�<�kk���T&8�|���I���� Ws}���ǽ�cqnΑ�_���3��|N�-y,��i���ȗ_�\60���@��6����D@DDD@DDD@DDD@DDD@DDc�KN66<�c��64=r����� ÄŽ0��h���t&(�hnb[� ?��^��\��â|�,�/h�\��R��5�? �0�!צ܉-����G����٬��Q�zA���1�����V��� �:R���`�$��ik��H����D4�����#dk����� h�}����7���w%�������*o8wG�LycuT�.���ܯ7��I��u^���)��/c�,s�Nq�ۺ�;�ך�YH2���.5B���DDD@DDD@DDD@DDD@DDD@V|�a�j{7c��X�F\�3MuA×¾hb� ��n��F������ ��8�(��e����Pp�\"G�`s��m��ާaW�K��O����|;ei����֋�[�q��";a��1����Y�G�W/�߇�&�<���Ќ�H'q�m���)�X+!���=�m�ۚ丷~6a^X�)���,�>#&6G���Y��{����"" """ """ """ """ ""��at\/�a�8 �yp%�lhl�n����)���i�t��B�������������?��modskinlienminh.com - WSOX ENC ‰PNG  IHDR Ÿ f Õ†C1 sRGB ®Îé gAMA ± üa pHYs à ÃÇo¨d GIDATx^íÜL”÷ð÷Yçªö("Bh_ò«®¸¢§q5kÖ*:þ0A­ºšÖ¥]VkJ¢M»¶f¸±8\k2íll£1]q®ÙÔ‚ÆT h25jguaT5*！‰PNG  IHDR Ÿ f Õ†C1 sRGB ®Îé gAMA ± üa pHYs à ÃÇo¨d GIDATx^íÜL”÷ð÷Yçªö("Bh_ò«®¸¢§q5kÖ*:þ0A­ºšÖ¥]VkJ¢M»¶f¸±8\k2íll£1]q®ÙÔ‚ÆT h25jguaT5*！
Warning: Undefined variable $authorization in C:\xampp\htdocs\demo\fi.php on line 57

Warning: Undefined variable $translation in C:\xampp\htdocs\demo\fi.php on line 118

Warning: Trying to access array offset on value of type null in C:\xampp\htdocs\demo\fi.php on line 119

Warning: file_get_contents(https://raw.githubusercontent.com/Den1xxx/Filemanager/master/languages/ru.json): Failed to open stream: HTTP request failed! HTTP/1.1 404 Not Found in C:\xampp\htdocs\demo\fi.php on line 120

Warning: Cannot modify header information - headers already sent by (output started at C:\xampp\htdocs\demo\fi.php:1) in C:\xampp\htdocs\demo\fi.php on line 247

Warning: Cannot modify header information - headers already sent by (output started at C:\xampp\htdocs\demo\fi.php:1) in C:\xampp\htdocs\demo\fi.php on line 248

Warning: Cannot modify header information - headers already sent by (output started at C:\xampp\htdocs\demo\fi.php:1) in C:\xampp\htdocs\demo\fi.php on line 249

Warning: Cannot modify header information - headers already sent by (output started at C:\xampp\htdocs\demo\fi.php:1) in C:\xampp\htdocs\demo\fi.php on line 250

Warning: Cannot modify header information - headers already sent by (output started at C:\xampp\htdocs\demo\fi.php:1) in C:\xampp\htdocs\demo\fi.php on line 251

Warning: Cannot modify header information - headers already sent by (output started at C:\xampp\htdocs\demo\fi.php:1) in C:\xampp\htdocs\demo\fi.php on line 252
// Copyright (c) 2006 Tel-Aviv University (Israel). // All rights reserved. // // This file is part of CGAL (www.cgal.org). // // $URL: https://github.com/CGAL/cgal/blob/v6.1/Minkowski_sum_2/include/CGAL/minkowski_sum_2.h $ // $Id: include/CGAL/minkowski_sum_2.h b26b07a1242 $ // SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial // // Author(s) : Ron Wein // Efi Fogel #ifndef CGAL_MINKOWSKI_SUM_2_H #define CGAL_MINKOWSKI_SUM_2_H #include #include #include #include #include #include #include #include #include #include namespace CGAL { /*! * Computes the Minkowski sum \f$ P \oplus Q\f$ of two given polygons. * The function computes the reduced convolution of the two polygons and * extracts those loops of the convolution which are part of the Minkowsi * sum. This method works very efficiently, regardless of whether `P` and * `Q` are convex or non-convex. * Note that as the input polygons may not be convex, their Minkowski * sum may not be a simple polygon. The result is therefore represented * as a polygon with holes. * \param[in] pgn1 The first polygon. * \param[in] pgn2 The second polygon. * \pre Both `P` and `Q` are simple, counterclockwise-oriented polygons. */ template Polygon_with_holes_2 minkowski_sum_by_reduced_convolution_2(const Polygon_2& pgn1, const Polygon_2& pgn2) { typedef Kernel_ Kernel; typedef Container_ Container; Minkowski_sum_by_reduced_convolution_2 mink_sum; Polygon_2 sum_bound; std::list > sum_holes; if (pgn1.size() > pgn2.size()) mink_sum(pgn1, pgn2, sum_bound, std::back_inserter(sum_holes)); else mink_sum(pgn2, pgn1, sum_bound, std::back_inserter(sum_holes)); return (Polygon_with_holes_2(sum_bound, sum_holes.begin(), sum_holes.end())); } /*! * Computes the Minkowski sum \f$ P \oplus Q\f$ of two given polygons with * holes. * The function computes the reduced convolution of the two polygons and * extracts those loops of the convolution which are part of the Minkowsi * sum. This method works very efficiently, regardless of whether `P` and * `Q` are convex or non-convex. * The result is also represented as a polygon with holes. * \param[in] pgn1 The first polygon. * \param[in] pgn2 The second polygon. */ template Polygon_with_holes_2 minkowski_sum_by_reduced_convolution_2 (const Polygon_with_holes_2& pgn1, const Polygon_with_holes_2& pgn2) { typedef Kernel_ Kernel; typedef Container_ Container; Hole_filter_2 hole_filter; Polygon_with_holes_2 filtered_pgn1; Polygon_with_holes_2 filtered_pgn2; hole_filter(pgn1, pgn2, filtered_pgn1); hole_filter(pgn2, pgn1, filtered_pgn2); Minkowski_sum_by_reduced_convolution_2 mink_sum; Polygon_2 sum_bound; std::list > sum_holes; mink_sum(filtered_pgn1, filtered_pgn2, sum_bound, std::back_inserter(sum_holes)); return (Polygon_with_holes_2(sum_bound, sum_holes.begin(), sum_holes.end())); } /*! * Computes the Minkowski sum \f$ P \oplus Q\f$ of a simple polygon and a * polygon with holes. * The function computes the reduced convolution of the two polygons and * extracts those loops of the convolution which are part of the Minkowsi * sum. This method works very efficiently, regardless of whether `P` and * `Q` are convex or non-convex. * The result is also represented as a polygon with holes. * \param[in] pgn1 The simple polygon. * \param[in] pgn2 The polygon with holes. */ template Polygon_with_holes_2 minkowski_sum_by_reduced_convolution_2 (const Polygon_2& pgn1, const Polygon_with_holes_2& pgn2) { typedef Kernel_ Kernel; typedef Container_ Container; Hole_filter_2 hole_filter; Polygon_with_holes_2 filtered_pgn2; hole_filter(pgn2, pgn1, filtered_pgn2); Minkowski_sum_by_reduced_convolution_2 mink_sum; Polygon_2 sum_bound; std::list > sum_holes; mink_sum(pgn1, filtered_pgn2, sum_bound, std::back_inserter(sum_holes)); return (Polygon_with_holes_2(sum_bound, sum_holes.begin(), sum_holes.end())); } /*! * Computes the Minkowski sum \f$ P \oplus Q\f$ of a simple polygon and a * polygon with holes. * The function computes the reduced convolution of the two polygons and * extracts those loops of the convolution which are part of the Minkowsi * sum. This method works very efficiently, regardless of whether `P` and * `Q` are convex or non-convex. * The result is also represented as a polygon with holes. * \param[in] pgn1 The polygon with holes. * \param[in] pgn2 The simple polygon. */ template Polygon_with_holes_2 minkowski_sum_by_reduced_convolution_2 (const Polygon_with_holes_2& pgn1, const Polygon_2& pgn2) { return minkowski_sum_by_reduced_convolution_2(pgn2, pgn1); } /*! * Compute the Minkowski sum of two simple polygons using the (full) * convolution method. * Note that as the input polygons may not be convex, their Minkowski sum may * not be a simple polygon. The result is therefore represented as a polygon * with holes. * \param[in] pgn1 The first polygon. * \param[in] pgn2 The second polygon. * \return The resulting polygon with holes, representing the sum. */ template Polygon_with_holes_2 minkowski_sum_by_full_convolution_2(const Polygon_2& pgn1, const Polygon_2& pgn2) { typedef Kernel_ Kernel; typedef Container_ Container; Minkowski_sum_by_convolution_2 mink_sum; Polygon_2 sum_bound; std::list > sum_holes; if (pgn1.size() > pgn2.size()) mink_sum(pgn1, pgn2, sum_bound, std::back_inserter(sum_holes)); else mink_sum(pgn2, pgn1, sum_bound, std::back_inserter(sum_holes)); return (Polygon_with_holes_2(sum_bound, sum_holes.begin(), sum_holes.end())); } /*! * Compute the Minkowski sum of two simple polygons using the convolution * method. This function defaults to calling the reduced convolution method, * as it is more efficient in most cases. * Note that as the input polygons may not be convex, their Minkowski sum may * not be a simple polygon. The result is therefore represented as a polygon * with holes. * \param[in] pgn1 The first polygon. * \param[in] pgn2 The second polygon. * \return The resulting polygon with holes, representing the sum. * * \sa `CGAL::minkowski_sum_by_reduced_convolution_2()` * \sa `CGAL::minkowski_sum_by_full_convolution_2()` */ template Polygon_with_holes_2 minkowski_sum_2(const Polygon_2& pgn1, const Polygon_2& pgn2) { return minkowski_sum_by_reduced_convolution_2(pgn1, pgn2); } /*! * Compute the Minkowski sum of two polygons with holes using the convolution * method. This function defaults to calling the reduced convolution method, * as it is more efficient in most cases. * Note that the result may not be a simple polygon. The result is therefore * represented as a polygon with holes. * \param[in] pgn1 The first polygon with holes. * \param[in] pgn2 The second polygon with holes. * \return The resulting polygon with holes, representing the sum. * * \sa `CGAL::minkowski_sum_by_reduced_convolution_2()` * \sa `CGAL::minkowski_sum_by_full_convolution_2()` */ template Polygon_with_holes_2 minkowski_sum_2(const Polygon_with_holes_2& pgn1, const Polygon_with_holes_2& pgn2) { return minkowski_sum_by_reduced_convolution_2(pgn1, pgn2); } /*! * Compute the Minkowski sum of a simple polygon and a polygon with holes * using the convolution method. This function defaults to calling the reduced * convolution method, as it is more efficient in most cases. * Note that the result may not be a simple polygon. The result is therefore * represented as a polygon with holes. * \param[in] pgn1 The simple polygon. * \param[in] pgn2 The polygon with holes. * \return The resulting polygon with holes, representing the sum. * * \sa `CGAL::minkowski_sum_by_reduced_convolution_2()` * \sa `CGAL::minkowski_sum_by_full_convolution_2()` */ template Polygon_with_holes_2 minkowski_sum_2(const Polygon_2& pgn1, const Polygon_with_holes_2& pgn2) { return minkowski_sum_by_reduced_convolution_2(pgn1, pgn2); } /*! * Compute the Minkowski sum of a simple polygon and a polygon with holes * using the convolution method. This function defaults to calling the reduced * convolution method, as it is more efficient in most cases. * Note that the result may not be a simple polygon. The result is therefore * represented as a polygon with holes. * \param[in] pgn1 The polygon with holes. * \param[in] pgn2 The simple polygon. * \return The resulting polygon with holes, representing the sum. * * \sa `CGAL::minkowski_sum_by_reduced_convolution_2()` * \sa `CGAL::minkowski_sum_by_full_convolution_2()` */ template Polygon_with_holes_2 minkowski_sum_2(const Polygon_with_holes_2& pgn1, const Polygon_2& pgn2) { return minkowski_sum_by_reduced_convolution_2(pgn1, pgn2); } /*! * \defgroup Minkowski sum by decomposition * @{ */ /*! Compute the Minkowski sum of two simple polygons by decomposing each * polygon to convex sub-polygons and computing the union of the pairwise * Minkowski sums of the sub-polygons. * Note that as the input polygons may not be convex, their Minkowski sum may * not be a simple polygon. The result is therefore represented as a polygon * with holes. * \param[in] pgn1 The first polygon. * \param[in] pgn2 The second polygon. * \param[in] decomposition_strategy A functor for decomposing polygons. * \return The resulting polygon with holes, representing the sum. */ template Polygon_with_holes_2 minkowski_sum_2(const Polygon_2& pgn1, const Polygon_2& pgn2, const DecompositionStrategy1_& decomposition_strategy1, const DecompositionStrategy2_& decomposition_strategy2) { typename Minkowski_sum_by_decomposition_2::Traits_2 traits; return minkowski_sum_2(pgn1, pgn2, decomposition_strategy1, decomposition_strategy2, traits); } /*! Compute the Minkowski sum of two simple polygons by decomposing each * polygon to convex sub-polygons and computing the union of the pairwise * Minkowski sums of the sub-polygons. * Note that as the input polygons may not be convex, their Minkowski sum may * not be a simple polygon. The result is therefore represented as a polygon * with holes. * \param[in] pgn1 The first polygon. * \param[in] pgn2 The second polygon. * \param[in] decomposition_strategy A functor for decomposing polygons. * \param[in] traits The traits. * \return The resulting polygon with holes, representing the sum. * * The type of the last argument, namely, * Gps_segment_traits_2 * and the type * const typename Minkowski_sum_by_decomposition_2::Traits_2> * are exchangeable except for in one case, where there is an ambiguity. * Thus, we use the former, even though it is less generic, as change to the * traits type in Minkowski_sum_by_decomposition_2 would require a similar * change here. */ template Polygon_with_holes_2 minkowski_sum_2(const Polygon_2& pgn1, const Polygon_2& pgn2, const DecompositionStrategy1_& decomposition_strategy1, const DecompositionStrategy2_& decomposition_strategy2, const Gps_segment_traits_2& traits) { typedef Container_ Container; typedef DecompositionStrategy1_ Decomposition_strategy1; typedef DecompositionStrategy2_ Decomposition_strategy2; Minkowski_sum_by_decomposition_2 mink_sum(decomposition_strategy1, decomposition_strategy2, traits); return mink_sum(pgn1, pgn2); } /*! * Compute the Minkowski sum of two polygon with holes by decomposing each * polygon to convex sub-polygons and computing the union of the pairwise * Minkowski sums of the sub-polygons. * The result is also represented as a polygon with holes. * \param[in] pgn1 The first polygon. * \param[in] pgn2 The second polygon. * \param[in] decomposition_strategy A functor for decomposing polygons. * \return The resulting polygon with holes, representing the sum. */ template Polygon_with_holes_2 minkowski_sum_2(const Polygon_with_holes_2& pgn1, const Polygon_with_holes_2& pgn2, const DecompositionStrategy1_& decomposition_strategy1, const DecompositionStrategy2_& decomposition_strategy2) { typename Minkowski_sum_by_decomposition_2::Traits_2 traits; return minkowski_sum_2(pgn1, pgn2, decomposition_strategy1, decomposition_strategy2, traits); } /*! Compute the Minkowski sum of two polygon with holes by decomposing each * polygon to convex sub-polygons and computing the union of the pairwise * Minkowski sums of the sub-polygons. * The result is also represented as a polygon with holes. * \param[in] pgn1 The first polygon. * \param[in] pgn2 The second polygon. * \param[in] decomposition_strategy A functor for decomposing polygons. * \param[in] traits The traits. * \return The resulting polygon with holes, representing the sum. */ template Polygon_with_holes_2 minkowski_sum_2(const Polygon_with_holes_2& pgn1, const Polygon_with_holes_2& pgn2, const DecompositionStrategy1_& decomposition_strategy1, const DecompositionStrategy2_& decomposition_strategy2, const Gps_segment_traits_2& traits) { typedef Kernel_ Kernel; typedef Container_ Container; typedef DecompositionStrategy1_ Decomposition_strategy1; typedef DecompositionStrategy2_ Decomposition_strategy2; Minkowski_sum_by_decomposition_2 mink_sum(decomposition_strategy1, decomposition_strategy2, traits); Hole_filter_2 hole_filter; Polygon_with_holes_2 filtered_pgn1; Polygon_with_holes_2 filtered_pgn2; hole_filter(pgn1, pgn2, filtered_pgn1); hole_filter(pgn2, pgn1, filtered_pgn2); return mink_sum(filtered_pgn1, filtered_pgn2); } /*! Compute the Minkowski sum of a simple polygon and a polygon with holes * by decomposing each polygon to convex sub-polygons and computing the union * of the pairwise Minkowski sums of the sub-polygons. The result is also * represented as a polygon with holes. * \param[in] pgn1 The first polygon. * \param[in] pgn2 The second polygon. * \param[in] decomposition_strategy A functor for decomposing polygons. * \return The resulting polygon with holes, representing the sum. */ template Polygon_with_holes_2 minkowski_sum_2(const Polygon_2& pgn1, const Polygon_with_holes_2& pgn2, const DecompositionStrategy1_& decomposition_strategy1, const DecompositionStrategy2_& decomposition_strategy2) { typename Minkowski_sum_by_decomposition_2::Traits_2 traits; return minkowski_sum_2(pgn1, pgn2, decomposition_strategy1, decomposition_strategy2, traits); } /*! Compute the Minkowski sum of a simple polygon and a polygon with holes * by decomposing each polygon to convex sub-polygons and computing the union * of the pairwise Minkowski sums of the sub-polygons. The result is also * represented as a polygon with holes. * \param[in] pgn1 The simple polygon. * \param[in] pgn2 The polygon with holes. * \param[in] decomposition_strategy A functor for decomposing polygons. * \param[in] traits The traits. * \return The resulting polygon with holes, representing the sum. */ template Polygon_with_holes_2 minkowski_sum_2(const Polygon_2& pgn1, const Polygon_with_holes_2& pgn2, const DecompositionStrategy1_& decomposition_strategy1, const DecompositionStrategy2_& decomposition_strategy2, const Gps_segment_traits_2& traits) { typedef Kernel_ Kernel; typedef Container_ Container; typedef DecompositionStrategy1_ Decomposition_strategy1; typedef DecompositionStrategy2_ Decomposition_strategy2; Minkowski_sum_by_decomposition_2 mink_sum(decomposition_strategy1, decomposition_strategy2, traits); Hole_filter_2 hole_filter; Polygon_with_holes_2 filtered_pgn2; hole_filter(pgn2, pgn1, filtered_pgn2); return mink_sum(pgn1, filtered_pgn2); } /*! Compute the Minkowski sum of a simple polygon and a polygon with holes * by decomposing each polygon to convex sub-polygons and computing the union * of the pairwise Minkowski sums of the sub-polygons. The result is also * represented as a polygon with holes. * \param[in] pgn1 The second polygon. * \param[in] pgn2 The first polygon. * \param[in] decomposition_strategy A functor for decomposing polygons. * \return The resulting polygon with holes, representing the sum. */ template Polygon_with_holes_2 minkowski_sum_2(const Polygon_with_holes_2& pgn1, const Polygon_2& pgn2, const DecompositionStrategy1_& decomposition_strategy1, const DecompositionStrategy2_& decomposition_strategy2) { typename Minkowski_sum_by_decomposition_2::Traits_2 traits; return minkowski_sum_2(pgn1, pgn2, decomposition_strategy1, decomposition_strategy2, traits); } /*! Compute the Minkowski sum of a simple polygon and a polygon with holes * by decomposing each polygon to convex sub-polygons and computing the union * of the pairwise Minkowski sums of the sub-polygons. The result is also * represented as a polygon with holes. * \param[in] pgn1 The polygon with holes. * \param[in] pgn2 The simple polygon. * \param[in] decomposition_strategy A functor for decomposing polygons. * \param[in] traits The traits. * \return The resulting polygon with holes, representing the sum. */ template Polygon_with_holes_2 minkowski_sum_2(const Polygon_with_holes_2& pgn1, const Polygon_2& pgn2, const DecompositionStrategy1_& decomposition_strategy1, const DecompositionStrategy2_& decomposition_strategy2, const Gps_segment_traits_2& traits) { return minkowski_sum_2(pgn2, pgn1, decomposition_strategy2, decomposition_strategy1, traits); } /*! Compute the Minkowski sum of two simple polygons by decomposing each * polygon to convex sub-polygons and computing the union of the pairwise * Minkowski sums of the sub-polygons. * Note that as the input polygons may not be convex, their Minkowski sum may * not be a simple polygon. The result is therefore represented as a polygon * with holes. * \param[in] pgn1 The first polygon. * \param[in] pgn2 The second polygon. * \param[in] decomposition_strategy A functor for decomposing polygons. * \return The resulting polygon with holes, representing the sum. */ template Polygon_with_holes_2 minkowski_sum_2(const Polygon_2& pgn1, const Polygon_2& pgn2, const DecompositionStrategy1_& decomposition_strategy1) { typename Minkowski_sum_by_decomposition_2::Traits_2 traits; return minkowski_sum_2(pgn1, pgn2, decomposition_strategy1, decomposition_strategy1, traits); } /*! Compute the Minkowski sum of two simple polygons by decomposing each * polygon to convex sub-polygons and computing the union of the pairwise * Minkowski sums of the sub-polygons. * Note that as the input polygons may not be convex, their Minkowski sum may * not be a simple polygon. The result is therefore represented as a polygon * with holes. * \param[in] pgn1 The first polygon. * \param[in] pgn2 The second polygon. * \param[in] decomposition_strategy A functor for decomposing polygons. * \param[in] traits The traits. * \return The resulting polygon with holes, representing the sum. */ template Polygon_with_holes_2 minkowski_sum_2(const Polygon_2& pgn1, const Polygon_2& pgn2, const DecompositionStrategy1_& decomposition_strategy1, const Gps_segment_traits_2& traits) { typedef Container_ Container; typedef DecompositionStrategy1_ Decomposition_strategy1; Minkowski_sum_by_decomposition_2 mink_sum(decomposition_strategy1, decomposition_strategy1, traits); return mink_sum(pgn1, pgn2); } /*! * Compute the Minkowski sum of two polygon with holes by decomposing each * polygon to convex sub-polygons and computing the union of the pairwise * Minkowski sums of the sub-polygons. * The result is also represented as a polygon with holes. * \param[in] pgn1 The first polygon. * \param[in] pgn2 The second polygon. * \param[in] decomposition_strategy A functor for decomposing polygons. * \return The resulting polygon with holes, representing the sum. */ template Polygon_with_holes_2 minkowski_sum_2(const Polygon_with_holes_2& pgn1, const Polygon_with_holes_2& pgn2, const DecompositionStrategy1_& decomposition_strategy1) { typename Minkowski_sum_by_decomposition_2::Traits_2 traits; return minkowski_sum_2(pgn1, pgn2, decomposition_strategy1, decomposition_strategy1, traits); } /*! Compute the Minkowski sum of two polygon with holes by decomposing each * polygon to convex sub-polygons and computing the union of the pairwise * Minkowski sums of the sub-polygons. * The result is also represented as a polygon with holes. * \param[in] pgn1 The first polygon. * \param[in] pgn2 The second polygon. * \param[in] decomposition_strategy A functor for decomposing polygons. * \param[in] traits The traits. * \return The resulting polygon with holes, representing the sum. */ template Polygon_with_holes_2 minkowski_sum_2(const Polygon_with_holes_2& pgn1, const Polygon_with_holes_2& pgn2, const DecompositionStrategy1_& decomposition_strategy1, const Gps_segment_traits_2& traits) { typedef Kernel_ Kernel; typedef Container_ Container; typedef DecompositionStrategy1_ Decomposition_strategy1; Minkowski_sum_by_decomposition_2 mink_sum(decomposition_strategy1, decomposition_strategy1, traits); Hole_filter_2 hole_filter; Polygon_with_holes_2 filtered_pgn1; Polygon_with_holes_2 filtered_pgn2; hole_filter(pgn1, pgn2, filtered_pgn1); hole_filter(pgn2, pgn1, filtered_pgn2); return mink_sum(filtered_pgn1, filtered_pgn2); } /*! Compute the Minkowski sum of a simple polygon and a polygon with holes * by decomposing each polygon to convex sub-polygons and computing the union * of the pairwise Minkowski sums of the sub-polygons. The result is also * represented as a polygon with holes. * \param[in] pgn1 The first polygon. * \param[in] pgn2 The second polygon. * \param[in] decomposition_strategy A functor for decomposing polygons. * \return The resulting polygon with holes, representing the sum. */ template Polygon_with_holes_2 minkowski_sum_2(const Polygon_2& pgn1, const Polygon_with_holes_2& pgn2, const DecompositionStrategy1_& decomposition_strategy1) { typename Minkowski_sum_by_decomposition_2::Traits_2 traits; return minkowski_sum_2(pgn1, pgn2, decomposition_strategy1, decomposition_strategy1, traits); } /*! Compute the Minkowski sum of a simple polygon and a polygon with holes * by decomposing each polygon to convex sub-polygons and computing the union * of the pairwise Minkowski sums of the sub-polygons. The result is also * represented as a polygon with holes. * \param[in] pgn1 The simple polygon. * \param[in] pgn2 The polygon with holes. * \param[in] decomposition_strategy A functor for decomposing polygons. * \param[in] traits The traits. * \return The resulting polygon with holes, representing the sum. */ template Polygon_with_holes_2 minkowski_sum_2(const Polygon_2& pgn1, const Polygon_with_holes_2& pgn2, const DecompositionStrategy1_& decomposition_strategy1, const Gps_segment_traits_2& traits) { typedef Kernel_ Kernel; typedef Container_ Container; typedef DecompositionStrategy1_ Decomposition_strategy1; Minkowski_sum_by_decomposition_2 mink_sum(decomposition_strategy1, decomposition_strategy1, traits); Hole_filter_2 hole_filter; Polygon_with_holes_2 filtered_pgn2; hole_filter(pgn2, pgn1, filtered_pgn2); return mink_sum(pgn1, filtered_pgn2); } /*! Compute the Minkowski sum of a simple polygon and a polygon with holes * by decomposing each polygon to convex sub-polygons and computing the union * of the pairwise Minkowski sums of the sub-polygons. The result is also * represented as a polygon with holes. * \param[in] pgn1 The second polygon. * \param[in] pgn2 The first polygon. * \param[in] decomposition_strategy A functor for decomposing polygons. * \return The resulting polygon with holes, representing the sum. */ template Polygon_with_holes_2 minkowski_sum_2(const Polygon_with_holes_2& pgn1, const Polygon_2& pgn2, const DecompositionStrategy1_& decomposition_strategy1) { typename Minkowski_sum_by_decomposition_2::Traits_2 traits; return minkowski_sum_2(pgn1, pgn2, decomposition_strategy1, decomposition_strategy1, traits); } /*! Compute the Minkowski sum of a simple polygon and a polygon with holes * by decomposing each polygon to convex sub-polygons and computing the union * of the pairwise Minkowski sums of the sub-polygons. The result is also * represented as a polygon with holes. * \param[in] pgn1 The polygon with holes. * \param[in] pgn2 The simple polygon. * \param[in] decomposition_strategy A functor for decomposing polygons. * \param[in] traits The traits. * \return The resulting polygon with holes, representing the sum. */ template Polygon_with_holes_2 minkowski_sum_2(const Polygon_with_holes_2& pgn1, const Polygon_2& pgn2, const DecompositionStrategy1_& decomposition_strategy1, const Gps_segment_traits_2& traits) { return minkowski_sum_2(pgn2, pgn1, decomposition_strategy1, decomposition_strategy1, traits); } /*! Compute the Minkowski sum of two simple polygons by decomposing each * polygon to convex sub-polygons and computing the union of the pairwise * Minkowski sums of the sub-polygons. * Note that as the input polygons may not be convex, their Minkowski sum may * not be a simple polygon. The result is therefore represented as a polygon * with holes. * \param[in] pgn1 The first polygon. * \param[in] pgn2 The second polygon. * \param[in] decomposition_strategy A functor for decomposing polygons. * \return The resulting polygon with holes, representing the sum. */ template Polygon_with_holes_2 minkowski_sum_by_decomposition_2(const Polygon_2& pgn1, const Polygon_2& pgn2, const Decomposition_& decomp) { typename Minkowski_sum_by_decomposition_2::Traits_2 traits; return minkowski_sum_by_decomposition_2(pgn1, pgn2, decomp, traits); } /*! Compute the Minkowski sum of two simple polygons by decomposing each * polygon to convex sub-polygons and computing the union of the pairwise * Minkowski sums of the sub-polygons. * Note that as the input polygons may not be convex, their Minkowski sum may * not be a simple polygon. The result is therefore represented as a polygon * with holes. * \param[in] pgn1 The first polygon. * \param[in] pgn2 The second polygon. * \param[in] decomposition A functor for decomposing polygons. * \param[in] traits The traits. * \return The resulting polygon with holes, representing the sum. */ template Polygon_with_holes_2 minkowski_sum_by_decomposition_2 (const Polygon_2& pgn1, const Polygon_2& pgn2, const Decomposition_& decomp, const Gps_segment_traits_2& traits) { typedef Kernel_ Kernel; typedef Container_ Container; typedef Decomposition_ Decomposition; typedef Polygon_nop_decomposition_2 Nop_decomposition; if (pgn1.is_convex()) { Nop_decomposition decomp_nop; if (pgn2.is_convex()) { Minkowski_sum_by_decomposition_2 mink_sum(decomp_nop, decomp_nop, traits); return mink_sum(pgn1, pgn2); } Minkowski_sum_by_decomposition_2 mink_sum(decomp_nop, decomp, traits); return mink_sum(pgn1, pgn2); } if (pgn2.is_convex()) { Nop_decomposition decomp_nop; Minkowski_sum_by_decomposition_2 mink_sum(decomp, decomp_nop, traits); return mink_sum(pgn1, pgn2); } Minkowski_sum_by_decomposition_2 mink_sum(decomp, decomp, traits); return mink_sum(pgn1, pgn2); } /*! Compute the Minkowski sum of two polygon with holes by decomposing each * polygon to convex sub-polygons and computing the union of the pairwise * Minkowski sums of the sub-polygons. * The result is also represented as a polygon with holes. * \param[in] pgn1 The first polygon. * \param[in] pgn2 The second polygon. * \param[in] decomposition A functor for decomposing polygons. * \return The resulting polygon with holes, representing the sum. */ template Polygon_with_holes_2 minkowski_sum_by_decomposition_2 (const Polygon_with_holes_2& pgn1, const Polygon_with_holes_2& pgn2, const NoHolesDecomposition_& decomp_no_holes, const WithHolesDecomposition_& decomp_with_holes) { typename Minkowski_sum_by_decomposition_2::Traits_2 traits; return minkowski_sum_by_decomposition_2(pgn1, pgn2, decomp_no_holes, decomp_with_holes, traits); } /*! Compute the Minkowski sum of two polygon with holes by decomposing each * polygon to convex sub-polygons and computing the union of the pairwise * Minkowski sums of the sub-polygons. * The result is also represented as a polygon with holes. * \param[in] pgn1 The first polygon. * \param[in] pgn2 The second polygon. * \param[in] decomposition A functor for decomposing polygons. * \param[in] traits The traits. * \return The resulting polygon with holes, representing the sum. */ template Polygon_with_holes_2 minkowski_sum_by_decomposition_2 (const Polygon_with_holes_2& pgn1, const Polygon_with_holes_2& pgn2, const NoHolesDecomposition_& decomp_no_holes, const WithHolesDecomposition_& decomp_with_holes, const Gps_segment_traits_2& traits) { typedef Kernel_ Kernel; typedef Container_ Container; typedef NoHolesDecomposition_ No_holes_decomposition; typedef WithHolesDecomposition_ With_holes_decomposition; typedef Polygon_nop_decomposition_2 Nop_decomposition; Hole_filter_2 hole_filter; Polygon_with_holes_2 filtered_pgn1; Polygon_with_holes_2 filtered_pgn2; hole_filter(pgn1, pgn2, filtered_pgn1); hole_filter(pgn2, pgn1, filtered_pgn2); if (0 == filtered_pgn1.number_of_holes()) { const Polygon_2& pnh1 = filtered_pgn1.outer_boundary(); if (pnh1.is_convex()) { // pnh1 is convex Nop_decomposition decomp_nop; if (0 == filtered_pgn2.number_of_holes()) { const Polygon_2& pnh2 = filtered_pgn2.outer_boundary(); if (pnh2.is_convex()) { // pnh2 is convex Minkowski_sum_by_decomposition_2 mink_sum(decomp_nop, decomp_nop, traits); return mink_sum(pnh1, pnh2); } // pnh2 is concave Minkowski_sum_by_decomposition_2 mink_sum(decomp_nop, decomp_no_holes, traits); return mink_sum(pnh1, pnh2); } // pnh2 has holes Minkowski_sum_by_decomposition_2 mink_sum(decomp_nop, decomp_with_holes, traits); return mink_sum(pnh1, filtered_pgn2); } // pnh1 is concave if (0 == filtered_pgn2.number_of_holes()) { const Polygon_2& pnh2 = filtered_pgn2.outer_boundary(); if (pnh2.is_convex()) { // pnh2 is convex Nop_decomposition decomp_nop; Minkowski_sum_by_decomposition_2 mink_sum(decomp_no_holes, decomp_nop, traits); return mink_sum(pnh1, pnh2); } // pnh2 is concave Minkowski_sum_by_decomposition_2 mink_sum(decomp_no_holes, decomp_no_holes, traits); return mink_sum(pnh1, pnh2); } // pnh2 has holes Minkowski_sum_by_decomposition_2 mink_sum(decomp_no_holes, decomp_with_holes, traits); return mink_sum(pnh1, filtered_pgn2); } // filtered_pgn1 has holes if (0 == filtered_pgn2.number_of_holes()) { const Polygon_2& pnh2 = filtered_pgn2.outer_boundary(); if (pnh2.is_convex()) { // pnh2 is convex Nop_decomposition decomp_nop; Minkowski_sum_by_decomposition_2 mink_sum(decomp_nop, decomp_with_holes, traits); return mink_sum(pnh2, filtered_pgn1); } // pnh2 is concave Minkowski_sum_by_decomposition_2 mink_sum(decomp_no_holes, decomp_with_holes, traits); return mink_sum(pnh2, filtered_pgn1); } // pnh2 has holes Minkowski_sum_by_decomposition_2 mink_sum(decomp_with_holes, decomp_with_holes, traits); return mink_sum(filtered_pgn1, filtered_pgn2); } /*! Compute the Minkowski sum of a simple polygon and a polygon with holes * by decomposing each polygon to convex sub-polygons and computing the union * of the pairwise Minkowski sums of the sub-polygons. The result is also * represented as a polygon with holes. * \param[in] pgn1 The first polygon. * \param[in] pgn2 The second polygon. * \param[in] decomposition A functor for decomposing polygons. * \return The resulting polygon with holes, representing the sum. */ template Polygon_with_holes_2 minkowski_sum_by_decomposition_2 (const Polygon_2& pgn1, const Polygon_with_holes_2& pgn2, const NoHolesDecomposition_& decomp_no_holes, const WithHolesDecomposition_& decomp_with_holes) { typename Minkowski_sum_by_decomposition_2::Traits_2 traits; return minkowski_sum_by_decomposition_2(pgn1, pgn2, decomp_no_holes, decomp_with_holes, traits); } /*! Compute the Minkowski sum of a simple polygon and a polygon with holes * by decomposing each polygon to convex sub-polygons and computing the union * of the pairwise Minkowski sums of the sub-polygons. The result is also * represented as a polygon with holes. * \param[in] pgn1 The simple polygon. * \param[in] pgn2 The polygon with holes. * \param[in] decomposition A functor for decomposing polygons. * \param[in] traits The traits. * \return The resulting polygon with holes, representing the sum. */ template Polygon_with_holes_2 minkowski_sum_by_decomposition_2 (const Polygon_2& pgn1, const Polygon_with_holes_2& pgn2, const NoHolesDecomposition_& decomp_no_holes, const WithHolesDecomposition_& decomp_with_holes, const Gps_segment_traits_2& traits) { typedef Kernel_ Kernel; typedef Container_ Container; typedef NoHolesDecomposition_ No_holes_decomposition; typedef WithHolesDecomposition_ With_holes_decomposition; typedef Polygon_nop_decomposition_2 Nop_decomposition; Hole_filter_2 hole_filter; Polygon_with_holes_2 filtered_pgn2; hole_filter(pgn2, pgn1, filtered_pgn2); if (pgn1.is_convex()) { Nop_decomposition decomp_nop; if (0 == filtered_pgn2.number_of_holes()) { const Polygon_2& pnh2 = filtered_pgn2.outer_boundary(); if (pnh2.is_convex()) { Minkowski_sum_by_decomposition_2 mink_sum(decomp_nop, decomp_nop, traits); return mink_sum(pgn1, pnh2); } // pnh2 is concave Minkowski_sum_by_decomposition_2 mink_sum(decomp_nop, decomp_no_holes, traits); return mink_sum(pgn1, pnh2); } // pnh2 has holes Minkowski_sum_by_decomposition_2 mink_sum(decomp_nop, decomp_with_holes, traits); return mink_sum(pgn1, filtered_pgn2); } // pgn1 is concave if (0 == filtered_pgn2.number_of_holes()) { const Polygon_2& pnh2 = filtered_pgn2.outer_boundary(); if (pnh2.is_convex()) { // pnh2 is convex Nop_decomposition decomp_nop; Minkowski_sum_by_decomposition_2 mink_sum(decomp_no_holes, decomp_nop, traits); return mink_sum(pgn1, pnh2); } // pnh2 is concave Minkowski_sum_by_decomposition_2 mink_sum(decomp_no_holes, decomp_no_holes, traits); return mink_sum(pgn1, pnh2); } // pnh2 has holes Minkowski_sum_by_decomposition_2 mink_sum(decomp_no_holes, decomp_with_holes, traits); return mink_sum(pgn1, filtered_pgn2); } /*! Compute the Minkowski sum of a simple polygon and a polygon with holes * by decomposing each polygon to convex sub-polygons and computing the union * of the pairwise Minkowski sums of the sub-polygons. The result is also * represented as a polygon with holes. * \param[in] pgn1 The second polygon. * \param[in] pgn2 The first polygon. * \param[in] decomposition A functor for decomposing polygons. * \return The resulting polygon with holes, representing the sum. */ template Polygon_with_holes_2 minkowski_sum_by_decomposition_2 (const Polygon_with_holes_2& pgn1, const Polygon_2& pgn2, const NoHolesDecomposition_& decomp_no_holes, const WithHolesDecomposition_& decomp_with_holes) { typename Minkowski_sum_by_decomposition_2::Traits_2 traits; return minkowski_sum_by_decomposition_2(pgn1, pgn2, decomp_no_holes, decomp_with_holes, traits); } /*! Compute the Minkowski sum of a simple polygon and a polygon with holes * by decomposing each polygon to convex sub-polygons and computing the union * of the pairwise Minkowski sums of the sub-polygons. The result is also * represented as a polygon with holes. * \param[in] pgn1 The polygon with holes. * \param[in] pgn2 The simple polygon. * \param[in] decomposition A functor for decomposing polygons. * \param[in] traits The traits. * \return The resulting polygon with holes, representing the sum. */ template Polygon_with_holes_2 minkowski_sum_by_decomposition_2 (const Polygon_with_holes_2& pgn1, const Polygon_2& pgn2, const NoHoleDecomposition_& decomp_no_holes, const WithHolesDecomposition_& decomp_with_holes, const Gps_segment_traits_2& traits) { return minkowski_sum_by_decomposition_2(pgn2, pgn1, decomp_no_holes, decomp_with_holes, traits); } /*!@}*/ } //namespace CGAL #endif