partition with information associated to the polygon vertices

Pair_partition_traits_2.h

// Copyright (c) 2000  Max-Planck-Institute Saarbruecken (Germany).
// All rights reserved.
//
// This file is part of CGAL (www.cgal.org).
// You can redistribute it and/or modify it under the terms of the GNU
// General Public License as published by the Free Software Foundation,
// either version 3 of the License, or (at your option) any later version.
//
// 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.
//
// $URL$
// $Id$
// SPDX-License-Identifier: GPL-3.0+
// 
//
// Author(s)     : Susan Hert <hert@mpi-sb.mpg.de>

#ifndef CGAL_PAIR_PARTITION_TRAITS_2_H
#define CGAL_PAIR_PARTITION_TRAITS_2_H

#include <CGAL/license/Partition_2.h>

#include <CGAL/polygon_function_objects.h>
#include <CGAL/Polygon_2.h>
#include <list>

namespace CGAL {


  template <typename Pair, typename Functor>
  struct Pair_functor {
    Functor fct;
    
    Pair_functor(const Functor fct)
      : fct(fct)
    {}

    typename Functor::result_type
    operator()(const Pair& p, const Pair& q)const
    {
      return fct(p.first,q.first);
    }
    
    typename Functor::result_type
    operator()(const Pair& p, const Pair& q, const Pair& r)const
    {
      return fct(p.first,q.first,r.first);
    }
  };

  template <typename Pair, typename K>
  struct Pair_compare_x_at_y_2 {
    
    typename K::Compare_x_at_y_2 fct;
    
    Pair_compare_x_at_y_2(typename K::Compare_x_at_y_2 fct)
      : fct(fct)
    {}
    
    typename K::Compare_x_at_y_2::result_type
    operator()(const Pair& p, const typename K::Line_2& line) const
    {
      return fct(p.first,line);
    }
  };

  
template <class Kernel_>
class Pair_partition_traits_2
{
private:
  typedef Kernel_                                     Kernel;
  typedef Pair_partition_traits_2<Kernel_>    Self;
  typedef Surface_mesh<typename Kernel::Point_2>      Surface_mesh;
  
public:

  Pair_partition_traits_2()
  {}

  
  typedef typename boost::graph_traits<Surface_mesh>::vertex_descriptor vertex_descriptor;

  typedef typename Kernel::FT FT;
  typedef typename boost::graph_traits<Surface_mesh>::vertex_descriptor vertex_descriptor;
  typedef std::pair<typename Kernel::Point_2, vertex_descriptor> Point_2;
  typedef ::std::list<Point_2>                        Container;
  typedef CGAL::Polygon_2<Self, Container>          Polygon_2;

  
  typedef Pair_functor<Point_2, typename Kernel::Equal_2>                Equal_2;

  typedef Pair_functor<Point_2, typename Kernel::Less_yx_2>                  Less_yx_2;
  typedef Pair_functor<Point_2, typename Kernel::Less_xy_2>                  Less_xy_2;
  typedef Pair_functor<Point_2, typename Kernel::Left_turn_2>                 Left_turn_2;
  typedef Pair_functor<Point_2, typename Kernel::Orientation_2>              Orientation_2;
  typedef Pair_functor<Point_2, typename Kernel::Compare_y_2>                Compare_y_2;
  typedef Pair_functor<Point_2, typename Kernel::Compare_x_2>                Compare_x_2;
  typedef CGAL::Is_convex_2<Self>                     Is_convex_2;
  typedef CGAL::Is_y_monotone_2<Self>                 Is_y_monotone_2;

  // needed by Indirect_edge_compare, used in y_monotone and greene_approx
  typedef typename Kernel::Line_2                     Line_2;
  typedef Pair_functor<Point_2, typename Kernel::Construct_line_2>           Construct_line_2;
  typedef Pair_compare_x_at_y_2<Point_2,typename Kernel>            Compare_x_at_y_2;
  typedef typename Kernel::Is_horizontal_2            Is_horizontal_2;
  
#if 0
  // needed by visibility graph and thus by optimal convex
  typedef typename Kernel::Ray_2                      Ray_2; 
  typedef typename Kernel::Collinear_are_ordered_along_line_2
  Collinear_are_ordered_along_line_2;
  typedef typename Kernel::Are_strictly_ordered_along_line_2
  Are_strictly_ordered_along_line_2;
  typedef typename Kernel::Intersect_2                Intersect_2;
  typedef typename Kernel::Assign_2                   Assign_2;
  typedef typename Kernel::Object_2                   Object_2;

  // needed by approx_convex (for constrained triangulation)
  // and optimal convex (for vis. graph)
#endif  
  typedef typename Kernel::Segment_2                  Segment_2;
#if 0  
  // needed by optimal convex (for vis. graph)
  typedef typename Kernel::Construct_segment_2        Construct_segment_2;
  typedef typename Kernel::Construct_ray_2            Construct_ray_2;
#endif
  Equal_2
  equal_2_object() const
  { return Equal_2(Kernel().equal_2_object()); }

  Orientation_2
  orientation_2_object() const
  { return Orientation_2(Kernel().orientation_2_object()); }



    Less_yx_2
    less_yx_2_object() const
    { return Less_yx_2(Kernel().less_yx_2_object()); }

    Less_xy_2
    less_xy_2_object() const
    { return Less_xy_2(Kernel().less_xy_2_object()); }

    Left_turn_2
    left_turn_2_object() const
    { return Left_turn_2(Kernel().left_turn_2_object()); }

    Compare_y_2
    compare_y_2_object() const
    {  return Compare_y_2(Kernel().compare_y_2_object()); }

    Compare_x_2
    compare_x_2_object() const
    {  return Compare_x_2(Kernel().compare_x_2_object()); }

  
  
  Construct_line_2
  construct_line_2_object() const
  {  return Construct_line_2(Kernel().construct_line_2_object()); }

  Compare_x_at_y_2
  compare_x_at_y_2_object() const
  { return Compare_x_at_y_2(Kernel().compare_x_at_y_2_object()); }


#if 0  

  Construct_segment_2
  construct_segment_2_object() const
  { return Construct_segment_2(); }

  Construct_ray_2
  construct_ray_2_object() const
  { return Construct_ray_2(); }

  Collinear_are_ordered_along_line_2
  collinear_are_ordered_along_line_2_object() const
  { return Collinear_are_ordered_along_line_2(); }

  Are_strictly_ordered_along_line_2
  are_strictly_ordered_along_line_2_object() const
  { return Are_strictly_ordered_along_line_2(); }

#endif
  
  Is_horizontal_2
  is_horizontal_2_object() const
  {  return Is_horizontal_2(); }

  Is_convex_2
  is_convex_2_object(const Self& traits) const
  {  return Is_convex_2(traits); }

  Is_y_monotone_2
  is_y_monotone_2_object(const Self& traits) const
  {  return Is_y_monotone_2(traits); }

#if 0
  Intersect_2
  intersect_2_object() const
  {  return Intersect_2(); }

  Assign_2
  assign_2_object() const
  {  return Assign_2(); }
#endif  
};

}

#endif // CGAL_PAIR_PARTITION_TRAITS_2_H

y_monotone_partition_with_info.cpp

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Surface_mesh.h>
#include <CGAL/Pair_partition_traits_2.h>
#include <CGAL/partition_2.h>
#include <cassert>
#include <list>


typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Surface_mesh<K::Point_2> Surface_mesh;
typedef CGAL::Pair_partition_traits_2<K>            Traits;
typedef Traits::Point_2                                     Point_2;

typedef Traits::Polygon_2                                   Polygon_2;
typedef std::list<Polygon_2>                                Polygon_list;

/*  

      v4     v2
      | \   /| 
      |  \ / |
      |  v3  |
      |      |
      v0-----v1

 */

int main( )
{

  Surface_mesh sm;

  Traits traits;

  Polygon_2 polygon(traits);

  polygon.push_back(std::make_pair(K::Point_2(0,0), sm.add_vertex(K::Point_2(0,0))));
  polygon.push_back(std::make_pair(K::Point_2(2,0), sm.add_vertex(K::Point_2(2,0))));
  polygon.push_back(std::make_pair(K::Point_2(2,2), sm.add_vertex(K::Point_2(2,2))));
  polygon.push_back(std::make_pair(K::Point_2(1,1), sm.add_vertex(K::Point_2(1,1))));
  polygon.push_back(std::make_pair(K::Point_2(0,2), sm.add_vertex(K::Point_2(0,2))));
  
  Polygon_list partition_polys;



   CGAL::y_monotone_partition_2(polygon.vertices_begin(),
                                polygon.vertices_end(),
                                std::back_inserter(partition_polys),
                                traits);

   std::list<Polygon_2>::const_iterator   poly_it;
   for (poly_it = partition_polys.begin(); poly_it != partition_polys.end();
        poly_it++)
   {
     for(Point_2 p : *poly_it){
       std::cout << "[" << p.first << "| " << p.second << "] ";
     }
     std::cout << std::endl;
   }
#if 0
   assert(CGAL::partition_is_valid_2(polygon.vertices_begin(),
                                     polygon.vertices_end(),
                                     partition_polys.begin(),
                                     partition_polys.end()));
#endif
   return 0;
}

The header file is not complete and I only made it work for CGAL::y_monotone_partition(). Also it is not clear how it helps to split faces (assuming that the vertices in polygon were not added but the vertices around a face. The problem is to get the order of the new edges incident to v3 right. @sloriot, any idea? Also instead of Surface_mesh it should be an Arrangement_2 with the goal to split a non-y-monotone face.