SPAR/AIModule/BWTA/vendors/CGAL/CGAL/Boolean_set_operations_2/Gps_polygon_validation.h

Go to the documentation of this file.

// Copyright (c) 2008  Tel-Aviv University (Israel).
// All rights reserved.
//
// This file is part of CGAL (www.cgal.org); you may redistribute it under
// the terms of the Q Public License version 1.0.
// See the file LICENSE.QPL distributed with CGAL.
//
// Licensees holding a valid commercial license may use this file in
// accordance with the commercial license agreement provided with the software.
//
// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
//
// 
//
// Author(s): Baruch Zukerman <baruchzu@post.tau.ac.il>
//                 Ron Wein        <wein@post.tau.ac.il>
//                 Boris Kozorovitzky <boriskoz@post.tau.ac.il>
//                 Guy Zucker <guyzucke@post.tau.ac.il> 

#ifndef CGAL_GPS_POLYGON_VALIDATION_2_H
#define CGAL_GPS_POLYGON_VALIDATION_2_H

#include <CGAL/Boolean_set_operations_2/Gps_traits_adaptor.h>
#include <CGAL/Boolean_set_operations_2/Gps_default_dcel.h>
#include <CGAL/Boolean_set_operations_2/Gps_on_surface_base_2.h>

#include <CGAL/Arrangement_2/Arr_default_planar_topology.h>
#include <CGAL/Sweep_line_2.h>
#include <CGAL/Sweep_line_2/Sweep_line_event.h>
#include <CGAL/Sweep_line_2/Sweep_line_subcurve.h>
#include <CGAL/Sweep_line_empty_visitor.h>
#include <CGAL/Arr_default_overlay_traits.h>
#include <CGAL/Arr_naive_point_location.h>


#include <iostream>
#include <list>
#include <iterator>

#define CGAL_GPS_POLYGON_VALIDATION_2_TYPEDEF                           \
  typedef Gps_traits_adaptor<Traits_2>              Traits_adapter_2;   \
  typedef typename Traits_2::Curve_const_iterator                       \
    Curve_const_iterator;                                               \
  typedef std::pair<Curve_const_iterator,Curve_const_iterator>          \
    Cci_pair;                                                           \
  typedef typename Traits_2::Construct_curves_2                         \
    Construct_curves_2;                                                 \
  typedef typename Traits_adapter_2::Construct_vertex_2                 \
    Construct_vertex_2;
  

CGAL_BEGIN_NAMESPACE

/*Arrangement is templated with extended face dcel*/
template<typename Arrangement_2>
class ValidationOverlayTraits : 
  public CGAL::Arr_default_overlay_traits<Arrangement_2> 
{
public:
  typedef CGAL::Arr_default_overlay_traits<Arrangement_2>       Base;
  typedef typename Base::Face_handle_A          Face_handle_A;
  typedef typename Base::Face_handle_B          Face_handle_B;
  typedef typename Base::Face_handle_R          Face_handle_R;
   
  typedef typename Arrangement_2::Ccb_halfedge_const_circulator                 Ccb_halfedge_const_circulator;
  typedef typename Arrangement_2::Halfedge_const_handle                                                 Halfedge_const_handle;
  typedef typename Arrangement_2::Face_const_handle                                                                             Face_const_handle;
  typedef typename Arrangement_2::Inner_ccb_const_iterator                                                                              Inner_ccb_const_iterator;

  /*red faces source is the arrangement of holes. The blue faces (face) are caused by the PWH's outer boundary*/
  virtual void create_face(Face_handle_A red_face, Face_handle_B blue_face, Face_handle_R /*r_face*/) {    
    if ((red_face->contained()==true) && (blue_face->contained()==false)) {
      hole_overlap=true;                        
    }
  }

public:
  ValidationOverlayTraits() : hole_overlap(false) {}
  bool getHoleOverlap() {
    return hole_overlap; 
  }
  void setHoleOverlap(bool b) {
    hole_overlap=b; return;
  }
private:    
  bool hole_overlap;
}; 

  
template <class ArrTraits_>
class Gps_polygon_validation_visitor : 
  public Sweep_line_empty_visitor<ArrTraits_>
{
private:

  typedef ArrTraits_                                   Traits_2;
  typedef Gps_polygon_validation_visitor<Traits_2>     Self;
  typedef typename Traits_2::X_monotone_curve_2        X_monotone_curve_2;
  typedef typename Traits_2::Point_2                   Point_2;

  typedef Sweep_line_empty_visitor<Traits_2>           Base;
  typedef typename Base::Event                         Event;
  typedef typename Base::Subcurve                      Subcurve;
  typedef typename Base::Status_line_iterator          SL_iterator;

  typedef Basic_sweep_line_2<Traits_2, Self>           Sweep_line;

public:

  Gps_polygon_validation_visitor(bool is_s_simple = true): 
    m_is_valid(true),
    m_is_s_simple(is_s_simple)
    {}


  template <class XCurveIterator>
  void sweep(XCurveIterator begin, XCurveIterator end)
    {
      //Perform the sweep
      reinterpret_cast<Sweep_line*>(this->m_sweep_line)->sweep(begin, end);
    }

  bool after_handle_event(Event* event,SL_iterator, bool)
    {
      if(event->is_intersection() ||
         event->is_weak_intersection() ||
         event->is_overlap())
      {
        m_is_valid = false;
        reinterpret_cast<Sweep_line*>(this->m_sweep_line) -> stop_sweep();
      }
      else
      {
        if (m_is_s_simple && 
            (event->number_of_right_curves() +
             event->number_of_left_curves()) != 2)
        {
          m_is_valid = false;
          reinterpret_cast<Sweep_line*>(this->m_sweep_line) -> stop_sweep();
        }
      }

      return (true);
    }


  bool is_valid()
    {
      return m_is_valid;
    }


protected:

  bool m_is_valid;
  bool m_is_s_simple; // is strictly simple

};


//Traits_2 templates the General_polygon_set_2 Traits.
//These include types for polygon and PWH.
template <typename Traits_2>
bool is_closed_polygon(const typename Traits_2::Polygon_2& pgn, Traits_2 traits)
{
  
  CGAL_GPS_POLYGON_VALIDATION_2_TYPEDEF
    Cci_pair              itr_pair = traits.construct_curves_2_object()(pgn);
  Curve_const_iterator  begin = itr_pair.first;
  Curve_const_iterator  end = itr_pair.second;

  if (begin == end)
    return (true);  // An empty polygon is valid.
    
  Traits_adapter_2            traits_adapter;
  typename Traits_2::Equal_2  equal_func = traits.equal_2_object();
  Curve_const_iterator        curr, next;
  Construct_vertex_2    construct_vertex_func;
  construct_vertex_func = traits_adapter.construct_vertex_2_object();
  curr = next = begin;
  ++next;

  if (next == end)
    return (false); // A polygon cannot have just a single edge.

  while (next != end)
  {
    // Make sure that the current target equals the next source.
    if (equal_func (construct_vertex_func (*curr, 0),
                    construct_vertex_func (*curr, 1)))
      return (false);

    if (! equal_func (construct_vertex_func (*curr, 1), 
                      construct_vertex_func (*next, 0)))
      return (false);

    // Move to the next pair of edges.
    curr = next;
    ++next;
  }

  // Make sure that the last target equals the first source.
  if (equal_func (construct_vertex_func (*curr, 0),
                  construct_vertex_func (*curr, 1)))
    return (false);

  if (! equal_func (construct_vertex_func (*curr, 1),
                    construct_vertex_func (*begin, 0)))
    return (false);

  return (true);
}
template <typename Traits_2>
bool is_simple_polygon(const typename Traits_2::Polygon_2& pgn,Traits_2 traits)
{// Previously known as is_strictly_simple

  CGAL_GPS_POLYGON_VALIDATION_2_TYPEDEF
    // Sweep the boundary curves and look for intersections.
    typedef Gps_polygon_validation_visitor<Traits_2>  Visitor;
  typedef Sweep_line_2<Traits_2, Visitor>           Sweep_line;

  Cci_pair              itr_pair = traits.construct_curves_2_object()(pgn);
  Visitor               visitor;
  Sweep_line            sweep_line (&traits, &visitor);

  visitor.sweep(itr_pair.first, itr_pair.second);
  return (visitor.is_valid());
}


template <typename Traits_2>
bool has_valid_orientation_polygon (const typename Traits_2::Polygon_2& pgn,Traits_2 traits)
{
  CGAL_GPS_POLYGON_VALIDATION_2_TYPEDEF

    Cci_pair         itr_pair = traits.construct_curves_2_object()(pgn);
  Traits_adapter_2            traits_adapter;
  typedef typename Traits_adapter_2::Orientation_2  Check_orientation_2;

  if(itr_pair.first == itr_pair.second)
    return (true); // empty polygon

  return (traits_adapter.orientation_2_object()(itr_pair.first,
                                                itr_pair.second) == COUNTERCLOCKWISE);
}
/* A valid polygon is :
 * 1 - Closed or empty polygon
 * 2 - Simple (previously known as strictly simple)
 * 3 - Counterclockwise oriented
 */
template <typename Traits_2>
bool is_valid_polygon(const typename Traits_2::Polygon_2& pgn,Traits_2 traits)
{
  bool closed = is_closed_polygon(pgn,traits);
  //CGAL_warning_msg (closed,
 //               "The polygon's boundary is not closed.");
  if (! closed)
    return (false);

  bool simple = is_simple_polygon(pgn,traits);
  //CGAL_warning_msg (simple,
 //                   "The polygon is not simple.");  
  if (!simple)
    return (false);   

  bool valid_orientation = has_valid_orientation_polygon(pgn,traits);
  //CGAL_warning_msg (valid_orientation,
  //                  "The polygon has a wrong orientation.");
  if (! valid_orientation)
    return (false);

  return (true);
}

  
template <typename Traits_2>
bool is_closed_polygon_with_holes(const typename Traits_2::Polygon_with_holes_2& pgn, Traits_2 traits)
{
  typedef typename Traits_2::Polygon_with_holes_2                       Polygon_with_holes_2;    
  if(! is_closed_polygon (pgn.outer_boundary(),traits))
    return (false);

  typename Polygon_with_holes_2::Hole_const_iterator    itr;

  for (itr = pgn.holes_begin(); itr != pgn.holes_end(); ++itr)
  {
    if(! is_closed_polygon (*itr,traits))
      return (false);
  }
  return (true);
}

//templated point location version
template<class Traits_2, class PointLocation>
bool is_crossover_outer_boundary(const typename Traits_2::Polygon_with_holes_2& pgn, Traits_2 traits, PointLocation& pl  ) {
  CGAL_GPS_POLYGON_VALIDATION_2_TYPEDEF  
    typedef typename Traits_2::Point_2                 Point_2;
  typedef typename Traits_2::Compare_endpoints_xy_2  Compare_endpoints_xy_2;
  typedef typename Traits_2::Construct_min_vertex_2  Construct_min_vertex_2; 
  typedef typename Traits_2::Construct_max_vertex_2  Construct_max_vertex_2;
  typedef CGAL::Gps_default_dcel<Traits_2>           Dcel;

  // IMPORTATNT! TODO!
  // Currently the topology traits is the bounded planar traits. This
  // should be replaced with a templated topology traits!
  typedef typename Default_planar_topology<Traits_2, Dcel>::Traits
                                                     Topology_traits;
  typedef CGAL::Gps_on_surface_base_2<Traits_2, Topology_traits> 
    Polygon_set_2;
  typedef typename Traits_2::Polygon_with_holes_2                                                       Polygon_with_holes_2;
  typedef typename Polygon_set_2::Arrangement_on_surface_2       Arrangement_2;
  typedef typename Arrangement_2::Halfedge_handle                Halfedge_handle;
  typedef typename Arrangement_2::Vertex_handle               Vertex_handle;
  typedef typename Arrangement_2::Vertex_const_handle               Vertex_const_handle;
  typedef typename Traits_2::Curve_const_iterator                               Curve_const_iterator;
    
  typename std::list<Halfedge_handle>   he_path;
  typename std::list<Halfedge_handle>::iterator         he_itr;
  //functors used throughout the function 
  Construct_min_vertex_2 min_functor = traits.construct_min_vertex_2_object();
  Construct_max_vertex_2 max_functor = traits.construct_max_vertex_2_object();
  Compare_endpoints_xy_2 cmp_endpoints =  traits.compare_endpoints_xy_2_object();
    
  Cci_pair              itr_pair = traits.construct_curves_2_object()(pgn.outer_boundary());
  Curve_const_iterator  begin = itr_pair.first;
  Curve_const_iterator  end = itr_pair.second;
  if (begin == end)
    return (true);  // An empty polygon is valid.
  //handles to consecutive curves 
  Curve_const_iterator        curr, next;
  curr = next = begin;
  //handles to vertices for insert. one maintains the current curve (already inserted) and next curve's joint vertex.
  //the other maintains the next curve's second vertex if it already exists in the arrangement. 
  Vertex_handle joint_ver, second_ver; 
  //closed check guarantees polygon has more than 1 curve    
  ++next;
  //halfedge handle whose target is always the joint vertex between next and curr. 
  Halfedge_handle last_he;
    
  Polygon_set_2 gps(traits);     
  Arrangement_2 arr = gps.arrangement();
  pl.attach(arr);

  //insert first edge lexicographically to arrangement
  // compute the joint vertex and insert to the path list a halfedge whose target is the joint vertex 
  last_he = CGAL::insert_non_intersecting_curve(arr, *curr);
  if  (cmp_endpoints(*curr) == SMALLER) { //polygon's boundary first curve is in lexicographic direction 
    joint_ver = last_he->target();
    he_path.push_back(last_he); 
  } else { //polygon's boundary first curve not lexicographic 
    joint_ver = last_he->source();
    he_path.push_back(last_he->twin()); 
  }

  /*insert the rest of the curves to the arrangement efficiently the previous closed polygon check guarantees
    equal_func (construct_vertex_func (*curr, 1), construct_vertex_func (*next, 0))) */
  while (next != end) {
    CGAL::Object obj;          
    Vertex_const_handle cver;
    Point_2 second_point;
    if(cmp_endpoints(*next) == SMALLER) { 
      //next curve's minimum is the joint vertex. Look if it's max exists in the arrangement and insert lexicographically 
      second_point = max_functor(*next);
      obj = pl.locate(second_point);
      if  (CGAL::assign (cver, obj)) {  
        //insert where both vertices exist
        second_ver = arr.non_const_handle(cver); 
        last_he = arr.insert_at_vertices( *next, joint_ver, second_ver);
      } else //insert from left vertex  
        last_he = arr.insert_from_left_vertex ( *next,joint_ver) ;  
    } else {  //next curve's maximum vertex is the joint vertex. try to locate the min vertex, and insert from right or from both vertices
      second_point = min_functor(*next);
      obj = pl.locate(second_point);
      if  (CGAL::assign (cver, obj))  {
        //insert where both vertices exist
        second_ver = arr.non_const_handle(cver); 
        last_he = arr.insert_at_vertices( *next, joint_ver, second_ver);
      } else  //insert from right vertex 
        last_he = arr.insert_from_right_vertex ( *next,joint_ver) ; 
    }
    // Move to the next pair of edges.
    he_path.push_back(last_he); 
    joint_ver=last_he->target();  
    curr = next;
    ++next;
  } //end of while 

//  We created a path of halfedges that circulates the polygon counterclockwise
//  The polygon should lay on the left of each of these half edges. 
//  If the boundary is invalid, the unbounded face should
//  be on the left of one of more than one of the halfedges.
//  The unbounded face is always to the right of the halfedges. We check if
//  all faces that lay on the right of the halfedges are equal (to the 
//  "unbounded" face).
  typename Arrangement_2::Face_handle fh = (*he_path.begin())->twin()->face();
  for (he_itr = he_path.begin(); he_itr != he_path.end(); he_itr++) {

    if ((*he_itr)->twin()->face() != fh)
      return false;
  }
  return true; 
}


template<typename Traits_2>
bool is_crossover_outer_boundary(
  const typename Traits_2::Polygon_with_holes_2& pgn, Traits_2 traits ) {

  typedef CGAL::Gps_default_dcel<Traits_2>                      Dcel;
  // IMPORTATNT! TODO!
  // Currently the topology traits is the bounded planar traits. This
  // should be replaced with a templated topology traits!
  typedef typename Default_planar_topology<Traits_2, Dcel>::Traits
                                                              Topology_traits;

  typedef CGAL::Gps_on_surface_base_2<Traits_2, Topology_traits> 
    Polygon_set_2;
  typedef typename Polygon_set_2::Arrangement_on_surface_2      Arrangement_2;
  typedef CGAL::Arr_naive_point_location<Arrangement_2>         Naive_pl;

  Naive_pl pl;
  return is_crossover_outer_boundary(pgn, traits, pl);
}



template <typename Traits_2>
bool is_relatively_simple_polygon_with_holes(const typename Traits_2::Polygon_with_holes_2& pgn, Traits_2 traits)
{// previously known as Simple
    
  CGAL_GPS_POLYGON_VALIDATION_2_TYPEDEF
    typedef typename Traits_2::X_monotone_curve_2     X_monotone_curve_2;
  typedef Gps_polygon_validation_visitor<Traits_2>  Visitor;
  typedef Sweep_line_2<Traits_2, Visitor>           Sweep_line;
  typedef typename Traits_2::Polygon_with_holes_2                       Polygon_with_holes_2;
         
  Construct_curves_2    construct_curves_func = traits.construct_curves_2_object();
  // Construct a container of all outer boundary curves.
  Cci_pair         itr_pair = construct_curves_func (pgn.outer_boundary());
  std::list<X_monotone_curve_2>  outer_curves;
  std::copy (itr_pair.first, itr_pair.second,
             std::back_inserter(outer_curves));
  //create visitor and sweep to verify outer boundary is relatively simple               
  Visitor      relative_visitor(false);
  Sweep_line   sweep_line (&traits, &relative_visitor);
  relative_visitor.sweep (outer_curves.begin(), outer_curves.end());
  if (!relative_visitor.is_valid())
    return false;
      
  //verify every hole is simple 
  typename Polygon_with_holes_2::Hole_const_iterator  hoit;
  std::list<X_monotone_curve_2>  hole_curves;    
  for (hoit = pgn.holes_begin(); hoit != pgn.holes_end(); ++hoit)
  {
    bool simple_hole = is_simple_polygon(*hoit,traits);
    if (!simple_hole)
      return false;
  }
  return true;
}



template <typename Traits_2>
bool has_valid_orientation_polygon_with_holes (const typename Traits_2::Polygon_with_holes_2& pgn, Traits_2 traits)
{
  CGAL_GPS_POLYGON_VALIDATION_2_TYPEDEF
    typedef typename Traits_2::X_monotone_curve_2     X_monotone_curve_2;
  typedef Gps_polygon_validation_visitor<Traits_2>  Visitor;
  typedef Sweep_line_2<Traits_2, Visitor>           Sweep_line;
  typedef typename Traits_adapter_2::Orientation_2  Check_orientation_2;
  typedef typename Traits_2::Polygon_with_holes_2                       Polygon_with_holes_2;

  Traits_adapter_2            traits_adapter;

  Construct_curves_2    construct_curves_func = traits.construct_curves_2_object();
  Check_orientation_2   check_orientation_func = traits_adapter.orientation_2_object();;
  // Check the orientation of the outer boundary.
  Cci_pair         itr_pair = construct_curves_func (pgn.outer_boundary());

  if ((itr_pair.first != itr_pair.second) && 
      check_orientation_func (itr_pair.first,  
                              itr_pair.second) != COUNTERCLOCKWISE)
  {
    return (false);
  }

  // Check the orientation of each of the holes.
  typename Polygon_with_holes_2::Hole_const_iterator    hoit;
    
  for (hoit = pgn.holes_begin(); hoit != pgn.holes_end(); ++hoit)
  {
    itr_pair = construct_curves_func (*hoit);

    if ((itr_pair.first !=itr_pair.second) &&
        check_orientation_func (itr_pair.first,  
                                itr_pair.second) != CLOCKWISE)
    {
      return (false);
    }
  }
  return (true);
}






/*Verify holes do not intersect between themselves as well with the outer boundary
  (except intersection on a vertex which is allowed).

  This efficient implementation utilizes the general poygon set for aggregated join
  operations for N holes which should result in a GPS that contains N independent PWH.
  Executing a difference(gps, outer boundary) should result in an empty set if
  no holes intersect the boundary. 

  An iterative use of the difference free function while iterating over the holes
  may have an advantage in case there are numerous holes that intersect the boundary
  and the iterative loop will be stopped after a small number of iterations.  

*/
template <class Traits_2>
bool are_holes_and_boundary_pairwise_disjoint(const typename Traits_2::Polygon_with_holes_2& pwh, Traits_2& traits)
{
  CGAL_GPS_POLYGON_VALIDATION_2_TYPEDEF

    typedef CGAL::Gps_default_dcel<Traits_2>         Dcel;
  // IMPORTATNT! TODO!
  // Currently the topology traits is the bounded planar traits. This
  // should be replaced with a templated topology traits!
  typedef typename Default_planar_topology<Traits_2, Dcel>::Traits
                                                     Topology_traits;

  typedef CGAL::Gps_on_surface_base_2<Traits_2, Topology_traits> 
    Polygon_set_2;
  typedef typename Polygon_set_2::Size                                                                  Size;
  typedef  typename Traits_2::Polygon_2                         Polygon_2;
  typedef typename Traits_2::Polygon_with_holes_2                                       Polygon_with_holes_2;
  typedef typename Polygon_with_holes_2::Hole_const_iterator    Hole_const_iterator;
  typedef typename Traits_2::X_monotone_curve_2     X_monotone_curve_2;
  typedef std::pair<Curve_const_iterator,
    Curve_const_iterator>           Cci_pair;
  typedef typename Traits_2::Construct_curves_2     Construct_curves_2;
  typedef typename Traits_2::Construct_general_polygon_with_holes_2       Construct_polygon_with_holes_2;
  typedef typename Traits_adapter_2::Construct_vertex_2
    Construct_vertex_2;
  typedef Gps_polygon_validation_visitor<Traits_2>  Visitor;
  typedef Sweep_line_2<Traits_2, Visitor>           Sweep_line ;
  typedef typename Polygon_set_2::Arrangement_on_surface_2
    Arrangement_2;
    
  /*  Should be perfored more efficeintly  than using sweep and than difference().*/
    
  /*Use sweep to find intersections on the interior of curves (not on vertices) and overlapping edges which are not allowed 
    (note that 0/1 dimension intersections are not detectes by do_intersect() which only returns the 2D intersection polygon if exists) 
    Note that using this sweep alone allows for a hole and an edge to share a vertex and intersect
    (like illegal input pgn_w_overlap_hole.dat in validation_example)*/
  Hole_const_iterator hoit;
  // Construct a container of all boundary curves.
  Polygon_2 pgn2 = traits.construct_outer_boundary_object()(pwh);   
  Construct_curves_2    construct_curves_func;    
  Cci_pair     itr_pair = construct_curves_func(pgn2);
    
  std::list<X_monotone_curve_2>  curves;
  std::copy (itr_pair.first, itr_pair.second,
             std::back_inserter(curves));

  std::pair<Hole_const_iterator, Hole_const_iterator> pair = traits.construct_holes_object()(pwh);
  for (hoit = pair.first; hoit!=pair.second; ++hoit)        
    //for (hoit = pgn.holes_begin(); hoit != pgn.holes_end(); ++hoit)
  {
    itr_pair = construct_curves_func (*hoit);
    std::copy (itr_pair.first, itr_pair.second,
               std::back_inserter(curves));
  }

  // Perform the sweep and check for curve  intersections on the interior.
  //Traits_2     traits; moved to top, needed also for boundary.
  Visitor      visitor(false);
  Sweep_line   sweep_line (&traits, &visitor);
  visitor.sweep (curves.begin(), curves.end());
  if  (!visitor.is_valid())
    return false;
      
  Polygon_set_2 gps(traits);
  //check for 2D  intersections of holes (holes must be disjoint except for vertices)     
  Size num_of_holes=0;
  //functors for creating a pwh needed for inserting pgns into the arrangement quickly 
  Construct_polygon_with_holes_2 construct_pwh_functor = traits.construct_polygon_with_holes_2_object () ;     
  for (hoit = pwh.holes_begin(); hoit != pwh.holes_end(); ++hoit) {
    Polygon_2 hole(*hoit);
    hole.reverse_orientation();
    /*gps.join() and gps.insert()requires that the polyon insrted is valid, and therfore hole
      orientation must be reversed*/ 
    bool intersect = gps.do_intersect(hole);    
    if (intersect)
      return false;
    else   {
      /*to use gps.insert(hole) it is required that the set coponents and the new holes  do not intersect.
        because the sweep detects shared edges and the do_intersect query detects 2D intersections we can safely use
        the insert(pwh) function whose performance is better than the join(pgn)*/
        Polygon_with_holes_2 empty_pwh = construct_pwh_functor(hole);
        //traits.Construct_general_polygon_with_holes_2 (hole);
  //    Polygon_with_holes_2 empty_pwh(hole);
      gps.insert(empty_pwh);
      num_of_holes++;
    }
  }  
  /*not good - doesn't work if intersection at vertices is legal.
    Size arr_num_of_holes = gps.number_of_polygons_with_holes();  
    if (num_of_holes != arr_num_of_holes)
    return false;
  */
  //check for intersection of holes with the outer boundary


  /*outer boundary can be relatively simple. Execution of 
    do_intersect(hole, boundary) or difference(hole,boundary) relies on
    implementation of General polygon set which has a precondition that requires
    valid polygon or PWH to be inserted (not just a simple polygon).  
    This helper function is utilized after checking for the PWH closure,
    relative simplicity and orientation. Therefore it is safe to assume the 
    outer boundary is  valid PWH with no holes. We can't assume it is a valid
    (simple) polygon. */       
  //Polygon_with_holes_2 boundary(pwh.outer_boundary(), fit, fit);     
 Polygon_with_holes_2 boundary =  construct_pwh_functor (pwh.outer_boundary());
  // Unbounded outer boundaries contain all the holes and the holes were checked
  // and are OK.
  if (boundary.is_unbounded()) 
    return true;

  /*do_intersect predicate will not suffice as hole can be completely outside
    the outer boundary in an (extremely strange) case
    The gps now contains all the holes. the difference between the boundary and a union of all
    the holes should be the empty set. For performance reasons, we use a customized overlay traits and 
    perform an arrangement overlay instead of difference */
  ValidationOverlayTraits<Arrangement_2> valOverlayTraits;
  valOverlayTraits.setHoleOverlap(false);
  Polygon_set_2 gps2(traits);
   
  Arrangement_2 boundary_arr = gps2.arrangement();
  gps2._insert(boundary,boundary_arr);
  Arrangement_2 holes_arr = gps.arrangement();    
  Arrangement_2 output_arr;
  overlay(holes_arr, boundary_arr, output_arr, valOverlayTraits);
  if (valOverlayTraits.getHoleOverlap())
    return false;
         
  /*old code that works less efficiently than the new overly traits
    gps.validation_difference(boundary);
    //if gps is not empty at least one hole intersected the boundary 
    if (!gps.is_empty())
    return (false);
  */        
  return (true);
} 

/*A valid polygon with holes is :
 * 1 - Has empty or closed boundary and all the holes are closed
 * 2 - The PWH is relatively simple polygon (holes are simple...)
 * 3 - Has it's boundary oriented counterclockwise and the holes oriented clockwise
 * 4 - All the segments (boundry and holes) do not cross or intersect in their relative interior
 * 5 - The holes are on the interior of the boundary polygon if the boundary is not empty
 */
template <typename Traits_2>
bool is_valid_polygon_with_holes(const typename Traits_2::Polygon_with_holes_2& pgn, Traits_2 traits)
{
  bool closed = is_closed_polygon_with_holes(pgn,traits);
  //CGAL_warning_msg (closed, 
  //                  "The polygon's boundary or one of it's holes is not closed.");
  if (! closed)
    return (false);
      
  bool relatively_simple = is_relatively_simple_polygon_with_holes(pgn,traits);
  //CGAL_warning_msg (relatively_simple,
  //                  "The polygon is not relatively simple.");
  if (! relatively_simple)
    return (false);
    
  bool no_cross = is_crossover_outer_boundary(pgn, traits);
  //CGAL_warning_msg (no_cross,
  //                  "The polygon has a crossover.");
  if (!no_cross)
    return (false);
          
  bool valid_orientation = has_valid_orientation_polygon_with_holes(pgn,traits);
  //CGAL_warning_msg (valid_orientation,
  //                  "The polygon has a wrong orientation.");
  if (! valid_orientation)
    return (false);
    
  bool holes_disjoint = are_holes_and_boundary_pairwise_disjoint(pgn,traits);
  //CGAL_warning_msg (holes_disjoint,
  //                  "Holes of the PWH intersect amongst themselves or with outer boundary");
  if (! holes_disjoint)
    return false;
      
  return (true);
}

template <typename Traits_2>
bool is_valid_unknown_polygon(const typename Traits_2::Polygon_with_holes_2& pgn, 
                              Traits_2& traits)
{
  return is_valid_polygon_with_holes(pgn, traits);
}
  
template <typename Traits_2>
bool is_valid_unknown_polygon(const typename Traits_2::Polygon_2& pgn,
                              Traits_2& traits)
{
  return is_valid_polygon(pgn, traits);
}
  
CGAL_END_NAMESPACE

#endif