CGAL users discussion list

[Hyungon Kim <>]

Hi,

Now I am going to use CGAL to do boolean operation for 2D polygons.
Before boolean operation, I need to make simple polygon with holes from an
abnormal polygon.
I expect Arrangement from CGAL handles this problem using sweep-line
algorithm.
However, Arrangement gives a different shapes from what I expected.
Here is an example in which one polygon has a self-intersected region and I
expect that Arrangement has two outer boundaries (one for polygon boundary
and another for hole). But the result is three outer boundaries including an
overlap area by self-intersected. Would you please let me know how to get
the simple polygon with holes from this kind of polygon with
self-intersected?

Thanks,
Hyungon Kim

#include    <iostream>
#include    <list>
using namespace std;

#include    <CGAL/basic.h>
#include    <CGAL/Gmpq.h>
#include    <CGAL/Simple_cartesian.h>
#include    <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include    <CGAL/Arr_segment_traits_2.h>
#include    <CGAL/Arr_linear_traits_2.h>
#include    <CGAL/Arr_polyline_traits_2.h>
#include    <CGAL/Arrangement_2.h>

typedef CGAL::Lazy_exact_nt<CGAL::Gmpq>                 FT;
typedef CGAL::Simple_cartesian<FT>                                          
cgalKernel;
typedef CGAL::Arr_segment_traits_2<cgalKernel>          Segment_Traits2;
typedef CGAL::Arr_polyline_traits_2<Segment_Traits2>    Traits2;
typedef Traits2::Point_2                                Point2;
typedef Traits2::Segment_2                              Segment2;
typedef Traits2::Curve_2                                Polyline2;
typedef CGAL::Arrangement_2<Traits2>                    Arrangement2;

//-----------------------------------------------------------------------------
// Print all neighboring vertices to a given arrangement vertex.
//
template<class Arrangement>
void print_neighboring_vertices(typename Arrangement::Vertex_const_handle v)
{
  if (v->is_isolated())
  {
    std::cout << "The vertex (" << v->point() << ") is isolated" <<
std::endl;
    return;
  }

  typename Arrangement::Halfedge_around_vertex_const_circulator  first,
curr;
  typename Arrangement::Vertex_const_handle                      u;

  std::cout << "The neighbors of the vertex (" << v->point() << ") are:";
  first = curr = v->incident_halfedges();
  do
  {
    // Note that the current halfedge is (u -> v):
    u = curr->source();
    std::cout << " (" << u->point() << ")";

    ++curr;
  } while (curr != first);
  std::cout << std::endl;

  return;
}

//-----------------------------------------------------------------------------
// Print all vertices (points) and edges (curves) along a connected
component
// boundary.
//
template<class Arrangement>
void print_ccb(typename Arrangement::Ccb_halfedge_const_circulator circ)
{
  typename Arrangement::Ccb_halfedge_const_circulator  curr = circ;
  typename Arrangement::Halfedge_const_handle          he;

  std::cout << "(" << curr->source()->point() << ")";
  do
  {
    he = curr;
    std::cout << "   [" << he->curve() << "]   "
              << "(" << he->target()->point() << ")";

    ++curr;
  } while (curr != circ);
  std::cout << std::endl;

  return;
}

//-----------------------------------------------------------------------------
// Print the boundary description of an arrangement face.
//
template<class Arrangement>
void print_face(typename Arrangement::Face_const_handle f)
{
  // Print the outer boundary.
  if (f->is_unbounded())
  {
    std::cout << "Unbounded face. " << std::endl;
  }
  else
  {
    std::cout << "Outer boundary: ";
    print_ccb<Arrangement> (f->outer_ccb());
  }

  // Print the boundary of each of the holes.
  typename Arrangement::Hole_const_iterator  hole;
  int                                         index = 1;

  for (hole = f->holes_begin(); hole != f->holes_end(); ++hole, ++index)
  {
    std::cout << "    Hole #" << index << ": ";
    print_ccb<Arrangement> (*hole);
  }

  // Print the isolated vertices.
  typename Arrangement::Isolated_vertex_const_iterator  iv;

  for (iv = f->isolated_vertices_begin(), index = 1;
       iv != f->isolated_vertices_end(); ++iv, ++index)
  {
    std::cout << "    Isolated vertex #" << index << ": "
              << "(" << iv->point() << ")" << std::endl;
  }

  return;
}

//-----------------------------------------------------------------------------
// Print the given arrangement.
//
template<class Arrangement>
void print_arrangement(const Arrangement& arr)
{
  CGAL_precondition (arr.is_valid());

  // Print the arrangement vertices.
  typename Arrangement::Vertex_const_iterator  vit;

  std::cout << arr.number_of_vertices() << " vertices:" << std::endl;
  for (vit = arr.vertices_begin(); vit != arr.vertices_end(); ++vit)
  {
    std::cout << "(" << vit->point() << ")";
    if (vit->is_isolated())
      std::cout << " - Isolated." << std::endl;
    else
      std::cout << " - degree " << vit->degree() << std::endl;
  }

  // Print the arrangement edges.
  typename Arrangement::Edge_const_iterator    eit;

  std::cout << arr.number_of_edges() << " edges:" << std::endl;
  for (eit = arr.edges_begin(); eit != arr.edges_end(); ++eit)
    std::cout << "[" << eit->curve() << "]" << std::endl;

  // Print the arrangement faces.
  typename Arrangement::Face_const_iterator    fit;

  std::cout << arr.number_of_faces() << " faces:" << std::endl;
  for (fit = arr.faces_begin(); fit != arr.faces_end(); ++fit)
    print_face<Arrangement> (fit);

  return;
}

int main()
{
    Arrangement2   arr;    
    std::list<Point2>   points;

    // case5: with overlap area
    points.clear();
    points.push_back(Point2(0,0));
    points.push_back(Point2(50,0));
    points.push_back(Point2(50,30));
    points.push_back(Point2(30,30));
    points.push_back(Point2(30,10));
    points.push_back(Point2(10,10));
    points.push_back(Point2(10,40));
    points.push_back(Point2(20,40));
    points.push_back(Point2(20,20));
    points.push_back(Point2(40,20));
    points.push_back(Point2(40,50));
    points.push_back(Point2(0,50));
    points.push_back(Point2(0,0));
    Polyline2   pline(points.begin(), points.end());
    
    insert(arr, pline);
    print_arrangement(arr);
    
    return 0;
}

-- 
View this message in context: 
http://cgal-discuss.949826.n4.nabble.com/How-to-get-one-boundary-and-one-hole-from-a-self-intersected-polygon-tp2133084p2133084.html
Sent from the cgal-discuss mailing list archive at Nabble.com.