// Copyright (c) 2000 Max-Planck-Institute Saarbruecken (Germany). // All rights reserved. // // This file is part of CGAL (www.cgal.org). // // $URL: https://github.com/CGAL/cgal/blob/v5.2/Partition_2/include/CGAL/Partition_2/Partitioned_polygon_2.h $ // $Id: Partitioned_polygon_2.h 0779373 2020-03-26T13:31:46+01:00 Sébastien Loriot // SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial // // // Author(s) : Susan Hert #ifndef CGAL_PARTITIONED_POLYGON_2_H #define CGAL_PARTITIONED_POLYGON_2_H #include #include #include #include namespace CGAL { // this will order the diagonals around a vertex from previous to // next, which means a CW order if the polygon vertices are in CCW order template class Indirect_CW_diag_compare { public: typedef typename Traits::Point_2 Point_2; typedef typename Traits::Orientation_2 Orig_orientation; Indirect_CW_diag_compare(){} Indirect_CW_diag_compare(Point_2 vertex, Iterator prev_ref, Iterator next_ref, const Traits& traits) : _orientation(traits.orientation_2_object()), _vertex(vertex), _prev_v_ref(prev_ref) { _vertex_orientation = _orientation(Point_2(*_prev_v_ref), Point_2(vertex), Point_2(*next_ref)); } bool operator()(Iterator d1, Iterator d2) { Orientation d1_orientation = _orientation(Point_2(*_prev_v_ref), Point_2(_vertex), Point_2(*d1)); Orientation d2_orientation = _orientation(Point_2(*_prev_v_ref), Point_2(_vertex), Point_2(*d2)); Orientation d1_to_d2 = _orientation(Point_2(*d1), Point_2(_vertex), Point_2(*d2)); // if both diagonals are on the same side of the line from previous // vertex to this vertex then d1 comes before d2 (in CW order from // the edge (previous, vertex)) if one makes a left turn from d1 to d2 if (d1_orientation == d2_orientation) return (d1_to_d2 == LEFT_TURN); // if d1 is on the line containing the edge (previous, vertex), then // the vertex must be a reflex vertex (otherwise the diagonal would // go outside the polygon) and d1 comes first if d2 is above the line // containing the three points, i.e., if it turns in the same // direction as the original edges around vertex. if (d1_orientation == COLLINEAR) return (d2_orientation == _vertex_orientation); // opposite sides of the line containing the previous edge // (again, vertex must be reflex) or d2 is collinear and d1 isn't. // In either case, d1 comes first if it is below the line containing // the previous edge. return (d1_orientation != _vertex_orientation); } private: Orig_orientation _orientation; Point_2 _vertex; Iterator _prev_v_ref; Orientation _vertex_orientation; }; template class Partition_vertex; // // requires // Traits::Polygon_2 // Traits::Point_2 // Traits::Left_turn_2 // Traits::Orientation_2 // template class Partitioned_polygon_2 : public std::vector< Partition_vertex< Traits_ > > { public: typedef Traits_ Traits; typedef Partition_vertex Vertex; typedef typename std::vector< Vertex >::iterator Iterator; typedef Circulator_from_iterator Circulator; typedef typename Traits::Polygon_2 Subpolygon_2; typedef typename Traits::Point_2 Point_2; typedef typename Traits::Left_turn_2 Left_turn_2; typedef std::list Diagonal_list; typedef typename Diagonal_list::iterator Diagonal_iterator; Partitioned_polygon_2(const Traits& traits) : _left_turn(traits.left_turn_2_object()), traits(traits) {} template Partitioned_polygon_2(InputIterator first, InputIterator beyond, const Traits& traits) : _left_turn(traits.left_turn_2_object()), traits(traits) { for (; first != beyond; first++) { this->push_back(Vertex(*first)); } } void insert_diagonal(Circulator v1_ref, Circulator v2_ref) { (*v1_ref).insert_diagonal(v2_ref); (*v2_ref).insert_diagonal(v1_ref); } void prune_diagonals() { Circulator first(this->begin(), this->end(), this->begin()); Circulator c = first; Diagonal_iterator d; #ifdef CGAL_PARTITIONED_POLY_DEBUG std::cout << "pruning diagonals ..." << std::endl; #endif do { d = (*c).diagonals_begin(); while (d != (*c).diagonals_end()) { if (!diagonal_is_necessary(c, *d)) { #ifdef CGAL_PARTITIONED_POLY_DEBUG std::cout << " removing from " << *c << " to " << **d << std::endl; #endif (**d).diagonal_erase(c); d = (*c).diagonal_erase(d); } else { d++; } } #ifdef CGAL_PARTITIONED_POLY_DEBUG (*c).print_diagonals(); #endif (*c).reset_current_diagonal(); } while (++c != first); } // the pruning is probably no longer necessary template OutputIterator partition(OutputIterator result, bool prune) { // walk through each vertex and sort the diagonals Circulator first(this->begin(), this->end()); Circulator c = first; Circulator next; Circulator prev = c; prev--; do { next = c; next++; (*c).sort_diagonals(prev, next, traits); #ifdef CGAL_PARTITIONED_POLY_DEBUG (*c).print_diagonals(); #endif prev = c; } while (++c != first); // now remove any diagonals that do not cut a reflex angle at one end if (prune) prune_diagonals(); #ifdef CGAL_PARTITIONED_POLY_DEBUG c = first; do { (*c).print_diagonals(); } while (++c != first); #endif make_polygon(first, result); return result; } private: template Circulator make_polygon(Circulator start, OutputIterator& result) { Subpolygon_2 new_polygon; Circulator next = start; do { new_polygon.push_back(*next); #ifdef CGAL_PARTITIONED_POLY_DEBUG std::cout << "adding vertex " << *next << std::endl; #endif Circulator diag; if ((*next).has_unused_diagonals()) { diag = (*next).current_diagonal(); #ifdef CGAL_PARTITIONED_POLY_DEBUG std::cout << "diagonal endpoint: " << *diag << std::endl; #endif (*next).advance_diagonal(); if (diag == start) { *result = new_polygon; result++; return next; } else { next = make_polygon(next, result); } } else next++; } while (next != start); *result = new_polygon; result++; return next; // if there are no diagonals at this vertex // push on the vertex // else if the first diagonal closes the polygon // close the polygon // return the current vertex (NOT the other end of the diagonal) // else // remove the first diagonal // recur, starting a new polygon at this vertex and return the // vertex where the new polygon ended // continue from the last vertex of the new polygon } bool cuts_reflex_angle(Circulator vertex_ref, Circulator diag_endpoint) { Circulator prev = vertex_ref; prev--; Circulator next = vertex_ref; next++; // find diag_endpoint in vertex_ref's list of diagonals Diagonal_iterator d_it; for (d_it = (*vertex_ref).diagonals_begin(); d_it != (*vertex_ref).diagonals_end() && diag_endpoint != *d_it; d_it++) { prev = *d_it; } Diagonal_iterator next_d_it = d_it; next_d_it++; if (next_d_it == (*vertex_ref).diagonals_end()) { next = vertex_ref; next++; } else next = *next_d_it; // return _right_turn(*prev, *vertex_ref, *next); return _left_turn(Point_2(*vertex_ref), Point_2(*prev), Point_2(*next)); } bool diagonal_is_necessary(Circulator diag_ref1, Circulator diag_ref2) { return (cuts_reflex_angle(diag_ref1, diag_ref2) || cuts_reflex_angle(diag_ref2, diag_ref1)); } Left_turn_2 _left_turn; const Traits& traits; }; template class Partition_vertex { private: typename Traits_::Point_2 point; public: typedef Traits_ Traits; typedef typename Traits::Point_2 Base_point; typedef typename Partitioned_polygon_2< Traits >::Circulator Circulator; typedef Partition_vertex Self; // // It might be better if this were a set that used Indirect_CW_diag_compare // as the Compare object, but the constructor for Indirect_CW_diag_compare // requires prev and next pointers, which would have to be supplied to // the constructor for a Partition_vertex as well, which is difficult to // do (perhaps impossible in general since you don't know what next and // previous will be until the whole polygon is constructed) // typedef std::list Diagonal_list; typedef typename Diagonal_list::iterator Diagonal_iterator; //default constructor added for EPECK Partition_vertex() { current_diag = diag_endpoint_refs.end() ; } Partition_vertex(Base_point p) : point(p) { current_diag = diag_endpoint_refs.end() ; } Partition_vertex(const Partition_vertex& other) : point(other.point) { // No need to deep copy. // We initialize in order to avoid problem with g++ safe STL current_diag = diag_endpoint_refs.end() ; } operator Base_point() const { return point; } Partition_vertex& operator=(const Partition_vertex&)=default; void insert_diagonal(Circulator v_ref) { diag_endpoint_refs.push_back(v_ref); } Diagonal_iterator diagonal_erase(Diagonal_iterator d_ref) { return diag_endpoint_refs.erase(d_ref); } Diagonal_iterator diagonal_erase(Circulator diag_endpoint) { Diagonal_iterator d_it = diagonals_begin(); for (d_it = diagonals_begin(); d_it != diagonals_end() && *d_it != diag_endpoint; d_it++) {} if (d_it != diagonals_end()) return diag_endpoint_refs.erase(d_it); return d_it; } Diagonal_iterator diagonals_begin() { return diag_endpoint_refs.begin(); } Diagonal_iterator diagonals_end() { return diag_endpoint_refs.end(); } bool has_unused_diagonals( ) { return current_diag != diag_endpoint_refs.end(); } // sort the diagonals ccw around the point they have in common // and remove any duplicate diagonals void sort_diagonals(const Circulator& prev, const Circulator& next, const Traits& traits) { diag_endpoint_refs.sort(Indirect_CW_diag_compare(*this, prev, next, traits)); diag_endpoint_refs.unique(); current_diag = diag_endpoint_refs.begin(); } void reset_current_diagonal( ) { current_diag = diag_endpoint_refs.begin(); } Circulator current_diagonal( ) const { return *current_diag; } void advance_diagonal() { if (current_diag != diag_endpoint_refs.end()) current_diag++; } void print_diagonals( ) const { std::cout << "from " << *this << std::endl; typename std::list::const_iterator it; for (it = diag_endpoint_refs.begin();it != diag_endpoint_refs.end(); it++) { std::cout << " to " << **it << std::endl; } } private: Diagonal_list diag_endpoint_refs; Diagonal_iterator current_diag; }; } #endif // CGAL_PARTITIONED_POLYGON_2_H