CGAL users discussion list

[Tapadi <>]

Hi all,

Here is a problem that is puzzling me for a while, even though it looks
basic.

*Context:* I build a 2D arrangement containing only one polyline curve.

*Problem:* There is a vertex duplication for some input curves.

Here is a code snippet ready for compilation, that gives the choice between
creating a polyline representing a left-sided circle and creating a polyline
representing a right-sided circle by tweaking the boolean value
"correct_behavior". 

The polyline is then added to an arrangement. It is cut into two x-monotone
subcurves in each case. However, in the left-sided case, the cutting vertex
is duplicated and the final arrangement has 4 vertices instead of 3. If
CGAL_precondition(cgal_arr.is_valid()) is called, then the process
terminates because it finds out the vertex duplication.

This code snippet is a modification from "ex_polylines.cpp", a source code
example for "CGAL Arrangements and Their Applications".

-----------------  code snippet  -----------------

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Arr_segment_traits_2.h>
#include <CGAL/Arr_polyline_traits_2.h>
#include <CGAL/Arrangement_2.h>

typedef CGAL::Exact_predicates_inexact_constructions_kernel  Kernel;
typedef CGAL::Arr_segment_traits_2<Kernel>                   Segment_traits;
typedef CGAL::Arr_polyline_traits_2<Segment_traits>          Traits;
typedef Traits::Point_2                                      Point_2;
typedef Traits::Curve_2                                      Polyline_2;
typedef CGAL::Arrangement_2<Traits>                          Arrangement_2;

#include <list>
#include <stdio.h>

int main(int argc, char *argv[]) {
  Arrangement_2 cgal_arr;
  std::list<Point_2> pts;
  const bool correct_behavior = false;
  
  if (correct_behavior) { // Builds a right-sided half circle
    pts.push_back(Point_2(250, 150 ));
    pts.push_back(Point_2(300, 163.397 ));
    pts.push_back(Point_2(336.603, 200 ));
    pts.push_back(Point_2(350, 250 ));
    pts.push_back(Point_2(336.603, 300 ));
    pts.push_back(Point_2(300, 336.603 ));
    pts.push_back(Point_2(250, 350 ));
  } else { // Builds a left-sided half circle
    pts.push_back(Point_2(250, 150 ));
    pts.push_back(Point_2(200, 163.397 ));
    pts.push_back(Point_2(163.397, 200 ));
    pts.push_back(Point_2(150, 250 ));
    pts.push_back(Point_2(163.397, 300 ));
    pts.push_back(Point_2(200, 336.603 ));
    pts.push_back(Point_2(250, 350 ));
  }

  Polyline_2 polyline(pts.begin(), pts.end());
  insert(cgal_arr, polyline);
  // CGAL_precondition(cgal_arr.is_valid()); // quits if correct_behavior ==
false

  // Next line prints "3 vertices" (correct cutting) if correct_behavior ==
true
  //        or prints "4 vertices" (incorrect) if correct_behavior == false
  printf("number of vertices in the arrangement : %li\n",
cgal_arr.number_of_vertices());
  
}

-----------------  end of code snippet  -----------------


Please try it out, I have no hint left about where it can come from... Am I
missing something important ?
Thanks in advance.

Best Regards,
Hugo Loi
PhD student at Inria - Maverick Team
http://maverick.inria.fr/



--
View this message in context: 
http://cgal-discuss.949826.n4.nabble.com/CGAL-doesn-t-like-left-sided-half-circles-Is-it-a-bug-or-do-I-have-a-bug-tp4656863.html
Sent from the cgal-discuss mailing list archive at Nabble.com.