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) 2023 GeometryFactory. // All rights reserved. // // This file is part of CGAL (www.cgal.org). // // $URL: https://github.com/CGAL/cgal/blob/v6.1/Polygon_repair/include/CGAL/Polygon_repair/repair.h $ // $Id: include/CGAL/Polygon_repair/repair.h b26b07a1242 $ // SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial // // Author(s) : Ken Arroyo Ohori #ifndef CGAL_POLYGON_REPAIR_H #define CGAL_POLYGON_REPAIR_H #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include namespace CGAL { namespace Polygon_repair { #ifndef DOXYGEN_RUNNING template class Polygon_repair; #endif /// \ingroup PkgPolygonRepairFunctions /// repairs polygon `p` using the given rule /// \tparam Kernel parameter of the input and output polygons. Must be model of `ConstrainedDelaunayTriangulationTraits_2 ` /// \tparam Container parameter of the input and output polygons /// \tparam Rule must be `Even_odd_rule` or `Non_zero_rule` template Multipolygon_with_holes_2 repair(const Polygon_2& p , Rule = Rule()) { static_assert(std::is_same_v); CGAL::Polygon_repair::Polygon_repair pr; pr.add_to_triangulation_even_odd(p); if (pr.triangulation().number_of_faces() > 0) { pr.label_triangulation_even_odd(); pr.reconstruct_multipolygon(); } return pr.multipolygon(); } /// \ingroup PkgPolygonRepairFunctions /// repairs polygon with holes `p` using the given rule /// \tparam Kernel parameter of the input and output polygons. Must be model of `ConstrainedDelaunayTriangulationTraits_2 ` /// \tparam Container parameter of the input and output polygons /// \tparam Rule must be `Even_odd_rule` or `Non_zero_rule` template Multipolygon_with_holes_2 repair(const Polygon_with_holes_2& p, Rule = Rule()) { static_assert(std::is_same_v); CGAL::Polygon_repair::Polygon_repair pr; pr.add_to_triangulation_even_odd(p); if (pr.triangulation().number_of_faces() > 0) { pr.label_triangulation_even_odd(); pr.reconstruct_multipolygon(); } return pr.multipolygon(); } template Multipolygon_with_holes_2 repair(const Polygon_2& p, Non_zero_rule) { Winding winding; winding.insert(p); winding.label(); winding.label_domains(); return winding(); } template Multipolygon_with_holes_2 repair(const Polygon_with_holes_2& p, Non_zero_rule) { Winding winding; winding.insert(p); winding.label(); winding.label_domains(); return winding(); } /// \ingroup PkgPolygonRepairFunctions /// repairs multipolygon with holes `p` using the given rule /// \tparam Kernel parameter of the input and output polygons. Must be model of `ConstrainedDelaunayTriangulationTraits_2 ` /// \tparam Container parameter of the input and output polygons /// \tparam Rule may be any \ref PkgPolygonRepairRules /// \pre If the rule is the `Union_rule` or `Non_zero_rule`, each polygon with hole must be free of self-intersections, /// the outer boundary of each polygon with holes must be counterclockwise and the holes clockwise oriented. template Multipolygon_with_holes_2 repair(const Multipolygon_with_holes_2& p, Rule = Rule()) { static_assert(std::is_same_v); CGAL::Polygon_repair::Polygon_repair pr; pr.add_to_triangulation_even_odd(p); if (pr.triangulation().number_of_faces() > 0) { pr.label_triangulation_even_odd(); pr.reconstruct_multipolygon(); } return pr.multipolygon(); } template Multipolygon_with_holes_2 repair(const Multipolygon_with_holes_2& p, Non_zero_rule) { Winding winding; winding.insert(p); winding.label(); winding.label_domains(); return winding(); } template Multipolygon_with_holes_2 repair(const Multipolygon_with_holes_2& p, Union_rule) { struct Larger_than_zero { bool operator()(int i) const { return i > 0; } }; CGAL::Polygon_repair::Boolean bops; bops.insert(p); bops.mark_domains(); Larger_than_zero ltz; return bops(ltz); } template Multipolygon_with_holes_2 repair(const Multipolygon_with_holes_2& p, Intersection_rule) { struct Equal { int val; Equal(int val) : val(val) {} bool operator()(int i) const { return i == val; } }; CGAL::Polygon_repair::Boolean bops; bops.insert(p); bops.mark_domains(); Equal equal(p.number_of_polygons_with_holes()); return bops(equal); } /* template Multipolygon_with_holes_2 repair(const Multipolygon_with_holes_2& p, Non_zero_rule rule) { static_assert(std::is_same_v); CGAL::Polygon_repair::Polygon_repair pr; pr.add_to_triangulation_even_odd(p); if (pr.triangulation().number_of_faces() > 0) { pr.label_triangulation_even_odd(); pr.reconstruct_multipolygon(); } return pr.multipolygon(); } */ template bool is_valid(const Polygon_2& polygon) { if (polygon.vertices().size() < 3) { std::cout << "Invalid: less than 3 vertices" << std::endl; return false; } for (auto const& edge: polygon.edges()) { if (edge.source() == edge.target()) { std::cout << "Invalid: duplicate vertices" << std::endl; return false; } } if (!polygon.is_simple()) { std::cout << "Invalid: not simple" << std::endl; return false; } return true; } template bool is_valid(const Polygon_with_holes_2& polygon) { // Validate outer boundary for (auto const& edge: polygon.outer_boundary().edges()) { if (edge.source() == edge.target()) { std::cout << "Invalid: duplicate vertices in outer boundary" << std::endl; return false; } } if (!polygon.outer_boundary().is_simple()) { std::cout << "Invalid: outer boundary not simple" << std::endl; return false; } // Validate holes for (auto const& hole: polygon.holes()) { for (auto const& edge: hole.edges()) { if (edge.source() == edge.target()) { std::cout << "Invalid: duplicate vertices in hole" << std::endl; return false; } } if (!hole.is_simple()) { std::cout << "Invalid: hole not simple" << std::endl; return false; } } // Create triangulation of outer boundary typename CGAL::Polygon_repair::Polygon_repair::Validation_triangulation vt; for (auto const& edge: polygon.outer_boundary().edges()) { try { vt.insert_constraint(edge.source(), edge.target()); } catch (typename CGAL::Polygon_repair::Polygon_repair::Validation_triangulation::Intersection_of_constraints_exception ice) { std::cout << "Invalid: intersection in outer boundary" << std::endl; return false; } } if (vt.number_of_faces() == 0) { std::cout << "Invalid: no outer boundary" << std::endl; return false; } for (auto const face: vt.all_face_handles()) { face->label() = 0; face->processed() = false; } std::list::Validation_triangulation::Face_handle> to_check; std::list to_check_added_by; CGAL::Polygon_repair::Polygon_repair::label_region(vt, vt.infinite_face(), -1, to_check, to_check_added_by); // exterior int regions = 0, holes = 0; while (!to_check.empty()) { if (to_check.front()->label() == 0) { // label = 0 means not labeled yet if (to_check_added_by.front() < 0) { CGAL::Polygon_repair::Polygon_repair::label_region(vt, to_check.front(), regions+1, to_check, to_check_added_by); ++regions; } else { CGAL::Polygon_repair::Polygon_repair::label_region(vt, to_check.front(), -(holes+2), to_check, to_check_added_by); ++holes; } } to_check.pop_front(); to_check_added_by.pop_front(); } CGAL_assertion(regions == 1 && holes == 0); // Hole nesting for (auto const& hole: polygon.holes()) { for (auto const& vertex: hole.vertices()) { typename CGAL::Polygon_repair::Polygon_repair::Validation_triangulation::Locate_type lt; int li; typename CGAL::Polygon_repair::Polygon_repair::Validation_triangulation::Face_handle f = vt.locate(vertex, lt, li); if (lt == CGAL::Polygon_repair::Polygon_repair::Validation_triangulation::Locate_type::FACE && f->label() != 1) { std::cout << "Invalid: hole (partly) outside outer boundary" << std::endl; return false; } } for (auto const& edge: hole.edges()) { try { vt.insert_constraint(edge.source(), edge.target()); } catch (typename CGAL::Polygon_repair::Polygon_repair::Validation_triangulation::Intersection_of_constraints_exception ice) { std::cout << "Invalid: hole (partly) outside outer boundary" << std::endl; return false; } } } // Connected interior for (auto const face: vt.all_face_handles()) { face->label() = 0; face->processed() = false; } to_check.clear(); to_check_added_by.clear(); CGAL::Polygon_repair::Polygon_repair::label_region(vt, vt.infinite_face(), -1, to_check, to_check_added_by); // exterior regions = 0; holes = 0; while (!to_check.empty()) { if (to_check.front()->label() == 0) { // label = 0 means not labeled yet if (to_check_added_by.front() < 0) { CGAL::Polygon_repair::Polygon_repair::label_region(vt, to_check.front(), regions+1, to_check, to_check_added_by); ++regions; } else { CGAL::Polygon_repair::Polygon_repair::label_region(vt, to_check.front(), -(holes+2), to_check, to_check_added_by); ++holes; } } to_check.pop_front(); to_check_added_by.pop_front(); } if (regions != 1) { std::cout << "Invalid: disconnected interior" << std::endl; return false; } CGAL_assertion(holes == polygon.number_of_holes()); return true; } template bool is_valid(const Multipolygon_with_holes_2& multipolygon) { // Validate polygons for (auto const& polygon: multipolygon.polygons_with_holes()) { if (!is_valid(polygon)) return false; } typename CGAL::Polygon_repair::Polygon_repair::Validation_triangulation vt; typename CGAL::Polygon_repair::Polygon_repair::Validation_triangulation::Locate_type lt; int li; for (auto const& polygon: multipolygon.polygons_with_holes()) { if (vt.number_of_faces() > 0) { // Relabel for (auto const face: vt.all_face_handles()) { face->label() = 0; face->processed() = false; } std::list::Validation_triangulation::Face_handle> to_check; std::list to_check_added_by; CGAL::Polygon_repair::Polygon_repair::label_region(vt, vt.infinite_face(), -1, to_check, to_check_added_by); // exterior int regions = 0, holes = 0; while (!to_check.empty()) { if (to_check.front()->label() == 0) { // label = 0 means not labeled yet if (to_check_added_by.front() < 0) { CGAL::Polygon_repair::Polygon_repair::label_region(vt, to_check.front(), regions+1, to_check, to_check_added_by); ++regions; } else { CGAL::Polygon_repair::Polygon_repair::label_region(vt, to_check.front(), -(holes+2), to_check, to_check_added_by); ++holes; } } to_check.pop_front(); to_check_added_by.pop_front(); } // Test vertices in labeled triangulation for (auto const& vertex: polygon.outer_boundary().vertices()) { typename CGAL::Polygon_repair::Polygon_repair::Validation_triangulation::Face_handle f = vt.locate(vertex, lt, li); if (lt == CGAL::Polygon_repair::Polygon_repair::Validation_triangulation::Locate_type::FACE && f->label() > 0) { std::cout << "Invalid: (partly) overlapping polygons" << std::endl; return false; } } for (auto const& hole: polygon.holes()) { for (auto const& vertex: hole.vertices()) { typename CGAL::Polygon_repair::Polygon_repair::Validation_triangulation::Face_handle f = vt.locate(vertex, lt, li); if (lt == CGAL::Polygon_repair::Polygon_repair::Validation_triangulation::Locate_type::FACE && f->label() > 0) { std::cout << "Invalid: (partly) overlapping polygons" << std::endl; return false; } } } } // Insert constraints while checking for intersections for (auto const& edge: polygon.outer_boundary().edges()) { try { vt.insert_constraint(edge.source(), edge.target()); } catch (typename CGAL::Polygon_repair::Polygon_repair::Validation_triangulation::Intersection_of_constraints_exception ice) { std::cout << "Invalid: (partly) overlapping polygons" << std::endl; return false; } } for (auto const& hole: polygon.holes()) { for (auto const& edge: hole.edges()) { try { vt.insert_constraint(edge.source(), edge.target()); } catch (typename CGAL::Polygon_repair::Polygon_repair::Validation_triangulation::Intersection_of_constraints_exception ice) { std::cout << "Invalid: (partly) overlapping polygons" << std::endl; return false; } } } } return true; } #ifndef DOXYGEN_RUNNING template > class Polygon_repair { public: using FT = typename Kernel::FT; using Point_2 = typename Kernel::Point_2; using Vertex_base = CGAL::Triangulation_vertex_base_2; using Face_base = CGAL::Constrained_triangulation_face_base_2; using Face_base_with_repair_info = internal::Triangulation_face_base_with_repair_info_2; using Triangulation_data_structure = CGAL::Triangulation_data_structure_2; using Tag = typename std::conditional::value, CGAL::Exact_predicates_tag, CGAL::Exact_intersections_tag>::type; using Constrained_Delaunay_triangulation = CGAL::Constrained_Delaunay_triangulation_2; using Triangulation = internal::Triangulation_with_even_odd_constraints_2; using Vertex_handle = typename Triangulation::Vertex_handle; using Face_handle = typename Triangulation::Face_handle; using Face_circulator = typename Triangulation::Face_circulator; using Edge = typename Triangulation::Edge; using Edge_map = typename std::conditional::value, std::unordered_set, boost::hash>>, std::set>>::type; using Vertex_map = typename std::conditional::value, std::unordered_map, std::map>::type; using Validation_tag = CGAL::No_constraint_intersection_tag; using Validation_triangulation = CGAL::Constrained_triangulation_2; using Polygon_2 = CGAL::Polygon_2; using Polygon_with_holes_2 = CGAL::Polygon_with_holes_2; using Multipolygon_with_holes_2 = CGAL::Multipolygon_with_holes_2; struct Polygon_less { bool operator()(const Polygon_2& pa, const Polygon_2& pb) const { typename Polygon_2::Vertex_iterator va = pa.vertices_begin(); typename Polygon_2::Vertex_iterator vb = pb.vertices_begin(); while (va != pa.vertices_end() && vb != pb.vertices_end()) { if (*va != *vb) return *va < *vb; ++va; ++vb; } if (vb == pb.vertices_end()) return false; return true; } }; struct Polygon_with_holes_less { Polygon_less pl; bool operator()(const Polygon_with_holes_2& pa, const Polygon_with_holes_2& pb) const { if (pl(pa.outer_boundary(), pb.outer_boundary())) return true; if (pl(pb.outer_boundary(), pa.outer_boundary())) return false; typename Polygon_with_holes_2::Hole_const_iterator ha = pa.holes_begin(); typename Polygon_with_holes_2::Hole_const_iterator hb = pb.holes_begin(); while (ha != pa.holes_end() && hb != pb.holes_end()) { if (pl(*ha, *hb)) return true; if (pl(*hb, *ha)) return false; } if (hb == pb.holes_end()) return false; return true; } }; /// \name Creation Polygon_repair() : number_of_polygons(0), number_of_holes(0) {} /// \name Modifiers /// @{ // Add edges of the polygon to the triangulation void add_to_triangulation_even_odd(const Polygon_2& polygon) { // Get unique edges for (auto const& edge: polygon.edges()) { if (edge.source() == edge.target()) continue; std::pair pair = (edge.source() < edge.target())? std::make_pair(edge.source(), edge.target()) : std::make_pair(edge.target(), edge.source()); auto inserted = unique_edges.insert(pair); if (!inserted.second) unique_edges.erase(inserted.first); } // Insert vertices Vertex_map vertices; std::vector> edges_to_insert; edges_to_insert.reserve(unique_edges.size()); for (auto const& edge: unique_edges) { Vertex_handle first_vertex, second_vertex; typename Vertex_map::const_iterator found = vertices.find(edge.first); if (found == vertices.end()) { first_vertex = t.insert(edge.first, search_start); vertices[edge.first] = first_vertex; } else { first_vertex = found->second; } search_start = first_vertex->face(); found = vertices.find(edge.second); if (found == vertices.end()) { second_vertex = t.insert(edge.second, search_start); vertices[edge.second] = second_vertex; } else { second_vertex = found->second; } search_start = second_vertex->face(); edges_to_insert.emplace_back(first_vertex, second_vertex); } // Insert edges for (auto const& edge: edges_to_insert) { t.even_odd_insert_constraint(edge.first, edge.second); } } // Add edges of the polygon to the triangulation void add_to_triangulation_even_odd(const Polygon_with_holes_2& polygon) { // Get unique edges for (auto const& edge: polygon.outer_boundary().edges()) { if (edge.source() == edge.target()) continue; std::pair pair = (edge.source() < edge.target())? std::make_pair(edge.source(), edge.target()) : std::make_pair(edge.target(), edge.source()); auto inserted = unique_edges.insert(pair); if (!inserted.second) unique_edges.erase(inserted.first); } for (auto const& hole: polygon.holes()) { for (auto const& edge: hole.edges()) { if (edge.source() == edge.target()) continue; std::pair pair = (edge.source() < edge.target())? std::make_pair(edge.source(), edge.target()) : std::make_pair(edge.target(), edge.source()); auto inserted = unique_edges.insert(pair); if (!inserted.second) unique_edges.erase(inserted.first); } } // Insert vertices Vertex_map vertices; std::vector> edges_to_insert; edges_to_insert.reserve(unique_edges.size()); for (auto const& edge: unique_edges) { Vertex_handle first_vertex, second_vertex; typename Vertex_map::const_iterator found = vertices.find(edge.first); if (found == vertices.end()) { first_vertex = t.insert(edge.first, search_start); vertices[edge.first] = first_vertex; } else { first_vertex = found->second; } search_start = first_vertex->face(); found = vertices.find(edge.second); if (found == vertices.end()) { second_vertex = t.insert(edge.second, search_start); vertices[edge.second] = second_vertex; } else { second_vertex = found->second; } search_start = second_vertex->face(); edges_to_insert.emplace_back(first_vertex, second_vertex); } // Insert edges for (auto const& edge: edges_to_insert) { t.even_odd_insert_constraint(edge.first, edge.second); } } // Add edges of the polygon to the triangulation void add_to_triangulation_even_odd(const Multipolygon_with_holes_2& multipolygon) { // Get unique edges for (auto const& polygon: multipolygon.polygons_with_holes()) { for (auto const& edge: polygon.outer_boundary().edges()) { if (edge.source() == edge.target()) continue; std::pair pair = (edge.source() < edge.target())? std::make_pair(edge.source(), edge.target()) : std::make_pair(edge.target(), edge.source()); auto inserted = unique_edges.insert(pair); if (!inserted.second) unique_edges.erase(inserted.first); } for (auto const& hole: polygon.holes()) { for (auto const& edge: hole.edges()) { if (edge.source() == edge.target()) continue; std::pair pair = (edge.source() < edge.target())? std::make_pair(edge.source(), edge.target()) : std::make_pair(edge.target(), edge.source()); auto inserted = unique_edges.insert(pair); if (!inserted.second) unique_edges.erase(inserted.first); } } } // Insert vertices Vertex_map vertices; std::vector> edges_to_insert; edges_to_insert.reserve(unique_edges.size()); for (auto const& edge: unique_edges) { Vertex_handle first_vertex, second_vertex; typename Vertex_map::const_iterator found = vertices.find(edge.first); if (found == vertices.end()) { first_vertex = t.insert(edge.first, search_start); vertices[edge.first] = first_vertex; } else { first_vertex = found->second; } search_start = first_vertex->face(); found = vertices.find(edge.second); if (found == vertices.end()) { second_vertex = t.insert(edge.second, search_start); vertices[edge.second] = second_vertex; } else { second_vertex = found->second; } search_start = second_vertex->face(); edges_to_insert.emplace_back(first_vertex, second_vertex); } // Insert edges for (auto const& edge: edges_to_insert) { t.even_odd_insert_constraint(edge.first, edge.second); } } // Label a region of adjacent triangles without passing through constraints // adjacent triangles that involve passing through constraints are added to to_check template static void label_region(T& tt, Face_handle face, int label, std::list& to_check, std::list& to_check_added_by) { // std::cout << "Labeling region with " << label << std::endl; std::list to_check_in_region; face->label() = label; to_check_in_region.push_back(face); face->processed() = true; // processed means added to a list (to ensure elements are only added once) while (!to_check_in_region.empty()) { for (int neighbour = 0; neighbour < 3; ++neighbour) { if (!tt.is_constrained(Edge(to_check_in_region.front(), neighbour))) { if (to_check_in_region.front()->neighbor(neighbour)->label() == 0) { // unlabeled to_check_in_region.front()->neighbor(neighbour)->label() = label; to_check_in_region.push_back(to_check_in_region.front()->neighbor(neighbour)); to_check_in_region.front()->neighbor(neighbour)->processed() = true; } } else { // constrained if (!to_check_in_region.front()->neighbor(neighbour)->processed()) { // not added to to_check to_check.push_back(to_check_in_region.front()->neighbor(neighbour)); to_check_added_by.push_back(label); to_check_in_region.front()->neighbor(neighbour)->processed() = true; } } } to_check_in_region.pop_front(); } } // Label triangles in triangulation void label_triangulation_even_odd() { // Simplify collinear edges (gets rid of order dependency) for (auto vertex: t.all_vertex_handles()) { typename Triangulation::Edge_circulator first_edge = t.incident_edges(vertex); typename Triangulation::Edge_circulator current_edge = first_edge; std::vector incident_constrained_edges; do { if (t.is_constrained(*current_edge)) { incident_constrained_edges.push_back(*current_edge); } ++current_edge; } while (current_edge != first_edge); if (incident_constrained_edges.size() == 2) { Point_2 v1 = incident_constrained_edges.front().first->vertex(incident_constrained_edges.front().first->ccw(incident_constrained_edges.front().second))->point(); Point_2 v2 = incident_constrained_edges.back().first->vertex(incident_constrained_edges.back().first->ccw(incident_constrained_edges.back().second))->point(); if (CGAL::collinear(v1, vertex->point(), v2)) { // std::cout << "Collinear points" << std::endl; // std::cout << "v1: " << v1 << std::endl; // std::cout << "in: " << vertex->point() << std::endl; // std::cout << "v2: " << v2 << std::endl; t.remove_incident_constraints(vertex); t.remove(vertex); t.insert_constraint(v1, v2); } } } // Init labels for (auto const face: t.all_face_handles()) { face->label() = 0; face->processed() = false; } // Label exterior with label -1, marking it as processed and // putting interior triangles adjacent to it in to_check std::list to_check; std::list to_check_added_by; label_region(t, t.infinite_face(), -1, to_check, to_check_added_by); // Label region of front element to_check list while (!to_check.empty()) { if (to_check.front()->label() == 0) { // label = 0 means not labeled yet if (to_check_added_by.front() < 0) { label_region(t, to_check.front(), number_of_polygons+1, to_check, to_check_added_by); ++number_of_polygons; } else { label_region(t, to_check.front(), -(number_of_holes+2), to_check, to_check_added_by); ++number_of_holes; } } to_check.pop_front(); to_check_added_by.pop_front(); } // std::cout << number_of_polygons << " polygons with " << number_of_holes << " holes in triangulation" << std::endl; } // Reconstruct ring boundary starting from an edge (face + opposite vertex) that is part of it void reconstruct_ring(std::list& ring, Face_handle face_adjacent_to_boundary, int opposite_vertex) { // std::cout << "Reconstructing ring for face " << face_adjacent_to_boundary->label() << "..." << std::endl; // Create ring Face_handle current_face = face_adjacent_to_boundary; int current_opposite_vertex = opposite_vertex; do { CGAL_assertion(current_face->label() == face_adjacent_to_boundary->label()); current_face->processed() = true; Vertex_handle pivot_vertex = current_face->vertex(current_face->cw(current_opposite_vertex)); // std::cout << "\tAdding point " << pivot_vertex->point() << std::endl; ring.push_back(pivot_vertex->point()); Face_circulator fc = t.incident_faces(pivot_vertex, current_face); do { ++fc; } while (fc->label() != current_face->label()); current_face = fc; current_opposite_vertex = fc->cw(fc->index(pivot_vertex)); } while (current_face != face_adjacent_to_boundary || current_opposite_vertex != opposite_vertex); // Start at lexicographically smallest vertex typename std::list::iterator smallest_vertex = ring.begin(); for (typename std::list::iterator current_vertex = ring.begin(); current_vertex != ring.end(); ++current_vertex) { if (*current_vertex < *smallest_vertex) smallest_vertex = current_vertex; } if (ring.front() != *smallest_vertex) { ring.splice(ring.begin(), ring, smallest_vertex, ring.end()); } } // Reconstruct multipolygon based on the triangles labeled as inside the polygon void reconstruct_multipolygon() { mp.clear(); std::vector polygons; // outer boundaries std::vector> holes; // holes are ordered (per polygon) polygons.resize(number_of_polygons); holes.resize(number_of_polygons); for (auto const face: t.all_face_handles()) { face->processed() = false; } for (auto const &face: t.finite_face_handles()) { if (face->label() < 1) continue; // exterior triangle if (face->processed()) continue; // already reconstructed for (int opposite_vertex = 0; opposite_vertex < 3; ++opposite_vertex) { if (face->label() == face->neighbor(opposite_vertex)->label()) continue; // not adjacent to boundary // Reconstruct ring std::list ring; reconstruct_ring(ring, face, opposite_vertex); // Put ring in polygons Polygon_2 polygon; polygon.reserve(ring.size()); polygon.insert(polygon.vertices_end(),ring.begin(), ring.end()); // std::cout << "Reconstructed ring for polygon " << face->label() << " with ccw? " << (polygon.orientation() == CGAL::COUNTERCLOCKWISE) << std::endl; if (polygon.orientation() == CGAL::COUNTERCLOCKWISE) { polygons[face->label()-1] = std::move(polygon); } else { holes[face->label()-1].insert(std::move(polygon)); } break; } } // Create polygons with holes and put in multipolygon std::set ordered_polygons; for (std::size_t i = 0; i < polygons.size(); ++i) { ordered_polygons.insert(Polygon_with_holes_2(std::move(polygons[i]), std::make_move_iterator(holes[i].begin()), std::make_move_iterator(holes[i].end()))); } for (auto const& polygon: ordered_polygons) { // std::cout << "Adding polygon " << polygon << std::endl; mp.add_polygon_with_holes(std::move(polygon)); } } // Erases the triangulation. void clear() { t.clear(); unique_edges.clear(); mp.clear(); number_of_polygons = 0; number_of_holes = 0; search_start = Triangulation::Face_handle(); } /// @} /// \name Access Functions /// @{ Triangulation& triangulation() { return t; } const Multipolygon_with_holes_2& multipolygon() { return mp; } /// @} protected: Triangulation t; Edge_map unique_edges; Multipolygon_with_holes_2 mp; int number_of_polygons, number_of_holes; Face_handle search_start; }; #endif // DOXYGEN_RUNNING /// \ingroup PkgPolygonRepairFunctions /// computes the union of all polygons with holes in `p` /// \tparam Kernel parameter of the input and output polygons. Must be model of `ConstrainedDelaunayTriangulationTraits_2 ` /// \tparam Container parameter of the input and output polygons /// \pre Each polygon with holes must be free of self-intersections, /// the outer boundaries must be counterclockwise and the holes clockwise oriented. template Multipolygon_with_holes_2 join(const Multipolygon_with_holes_2& pa) { struct Larger_than_zero { bool operator()(int i) const { return i > 0; } }; CGAL::Polygon_repair::Boolean bops; bops.insert(pa); bops.mark_domains(); Larger_than_zero ltz; return bops(ltz); } /// \ingroup PkgPolygonRepairFunctions /// computes the union of two polygonal domains /// \tparam Kernel parameter of the output polygons. Must be model of `ConstrainedDelaunayTriangulationTraits_2 ` /// \tparam Container parameter of the input and output polygons /// \tparam PA must be `Polygon_2`, or `Polygon_with_holes_2`, or `Multipolygon_with_holes_2` /// \tparam PB must be `Polygon_2`, or `Polygon_with_holes_2`, or `Multipolygon_with_holes_2` /// \pre The polygons `pa` and `pb` must be free of self-intersections, /// the outer boundaries must be counterclockwise and the holes clockwise oriented. template #ifdef DOXYGEN_RUNNING Multipolygon_with_holes_2 #else decltype(auto) #endif join(const PA& pa, const PB& pb, const Kernel& = Default(), const Container& = Default()) { typedef typename Default::Get::type Traits; typedef typename Default::Get::type Container_; struct Larger_than_zero { bool operator()(int i) const { return i > 0; } }; CGAL::Polygon_repair::Boolean bops; bops.insert(pa); bops.insert(pb); bops.mark_domains(); Larger_than_zero ltz; return bops(ltz); } /// \ingroup PkgPolygonRepairFunctions /// computes the intersection of all polygons with holes in `p` /// \tparam Kernel parameter of the input and output polygons. Must be model of `ConstrainedDelaunayTriangulationTraits_2 ` /// \tparam Container parameter of the input and output polygons /// \pre Each polygon with holes must be free of self-intersections /// the outer boundaries must be counterclockwise and the holes clockwise oriented. template Multipolygon_with_holes_2 intersect(const Multipolygon_with_holes_2& p) { struct Equal { int val; Equal(int val) : val(val) {} bool operator()(int i) const { return i == val; } }; CGAL::Polygon_repair::Boolean bops; bops.insert(p); bops.mark_domains(); Equal equal(p.number_of_polygons_with_holes()); return bops(equal); } /// \ingroup PkgPolygonRepairFunctions /// computes the intersection of two polygonal domains /// \tparam Kernel parameter of the output polygon. Must be model of `ConstrainedDelaunayTriangulationTraits_2 ` /// \tparam Container parameter of the input and output polygons /// \tparam PA must be `Polygon_2`, or `Polygon_with_holes_2`, or `Multipolygon_with_holes_2` /// \tparam PB must be `Polygon_2`, or `Polygon_with_holes_2`, or `Multipolygon_with_holes_2` /// \pre The polygons `pa` and `pb` must be free of self-intersections /// the outer boundaries must be counterclockwise and the holes clockwise oriented. template #ifdef DOXYGEN_RUNNING Multipolygon_with_holes_2 #else decltype(auto) #endif intersect(const PA& pa, const PB& pb, const Kernel& = Default(), const Container& = Default()) { typedef typename Default::Get::type Traits; typedef typename Default::Get::type Container_; struct Equal { bool operator()(int i) const { return i == 2; } }; CGAL::Polygon_repair::Boolean bops; bops.insert(pa); bops.insert(pb); bops.mark_domains(); Equal equal; return bops(equal); } } // namespace Polygon_repair } // namespace CGAL #endif // CGAL_POLYGON_REPAIR_H