CGAL users discussion list

[David Keller <>]

Hi,

sorry for insisting on similar topics here: I came across a failure 
caused by overlaying two arrangements with partially overlapping curves.

You find a test scenario containing two test cases attached to this 
mail. Both test cases fail by throwing an exception, actually a 
precondition failure in CGAL. The program gives the following output:

====== BEGIN OUTPUT ======
Running 2 test cases...
CGAL error: assertion violation!
Expr: !pt.is_red_object_null() || !pt.is_blue_object_null()
File: 
../../../../libs/external/cgal/CGAL-3.3.1/include/CGAL/Arr_overlay_2/Overlay_visitor.h
Line: 594
Explanation:
arr_overlay_with_orverlapping_curves.cpp(59): error in 
"simple_overlay_test": exception thrown by CGAL::overlay( arr1, arr2, 
ovl, ot )
CGAL error: assertion violation!
Expr: !pt.is_blue_object_null()
File: 
../../../../libs/external/cgal/CGAL-3.3.1/include/CGAL/Arr_overlay_2/Overlay_visitor.h
Line: 271
Explanation:
arr_overlay_with_orverlapping_curves.cpp(83): error in "overlay_test": 
exception thrown by CGAL::overlay( arr1, arr2, ovl, ot )

*** 2 failures detected in test suite "Master Test Suite"

EXIT STATUS: 201
====== END OUTPUT ======

When trying to debug these I found Overlay_visitor being called with 
event points which miss a correct point_info, i.e. their relations to 
objects in the "blue" and "red" arrangement is not set. 
Overlay_meta_traits actually gets the correct information on overlapping 
subcurves and associates these curves with "purple" information. 
However, the end points are apparently not correctly flagged with 
"purple" information and thus violate the preconditions in Overlay_visitor.

I have actually no idea how to further debug these things, at least from 
my point of view the code in Overlay_visitor and Overlay_meta_traits is 
not easily readable. Hence, I would be glad to get further hints on 
where to look at or even on how to fix this issue. Maybe the problem is 
even known and there is a fix for it?

Thanks and regards
David Keller


// #define VERBOSE
#define BOOST_TEST_MAIN
#include <boost/test/unit_test.hpp>

#include <sstream>
#include <boost/array.hpp>

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Arrangement_with_history_2.h>
#include <CGAL/Arr_polyline_traits_2.h>
#include <CGAL/Arr_non_caching_segment_traits_2.h>
#include <CGAL/Arr_extended_dcel.h>
#include <CGAL/Arr_overlay.h>
#include <CGAL/Arr_default_overlay_traits.h>

struct VertexData
{};

struct HalfedgeData
{};

struct FaceData
{};

typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel;
typedef CGAL::Arr_non_caching_segment_traits_2<Kernel>      SegmentTraits;
typedef CGAL::Arr_polyline_traits_2<SegmentTraits>          Traits;
typedef CGAL::Arr_extended_dcel<Traits, VertexData, HalfedgeData, FaceData>
                                                            Dcel;
typedef CGAL::Arrangement_with_history_2<Traits,Dcel>       Arrangement;
typedef Traits::Curve_2                                     Curve;
typedef Traits::Point_2                                     Point;
typedef CGAL::Arr_default_overlay_traits<Arrangement>       Overlay_traits;

BOOST_AUTO_TEST_CASE( simple_overlay_test )
{

  Arrangement arr1, arr2, ovl;

  std::vector<Curve> curves;
  std::vector<Point> points;

  points.push_back( Point( 0., 0. ) );
  points.push_back( Point( 10., 0. ) );
  curves.push_back( Curve( points.begin(), points.end() ) );
  points.clear();
  points.push_back( Point( 1., -1. ) );
  points.push_back( Point( 2., 0. ) );
  points.push_back( Point( 5., 0. ) );
  points.push_back( Point( 7., 1. ) );
  curves.push_back( Curve( points.begin(), points.end() ) );
  points.clear();
  

  CGAL::insert_curves( arr1, curves.begin(), curves.begin() + 1 );
  CGAL::insert_curves( arr2, curves.begin() + 1 , curves.end() );

  Overlay_traits ot;
  BOOST_CHECK_NO_THROW( CGAL::overlay( arr1, arr2, ovl, ot ) );
  BOOST_CHECK( ovl.is_valid() );

}


BOOST_AUTO_TEST_CASE( overlay_test )
{

  std::stringstream s( "20  3.70241 10.0638  3.54263 10.1538  3.38164 10.2439  3.21941 10.334  3.05592 10.424  2.89125 10.5135  2.72572 10.6018  2.56035 10.6874  2.3986 10.7661  2.25663 10.8221  2.31918 10.6983  3.24394 9.79979  4.12975 8.9881  5.0517 8.20885  6.01939 7.4895  7.04448 6.89657  8.12341 6.63783  9.06354 7.42606  9.38395 6.81832  7.88638 5.3789 25  3.21425 2.04354  3.07152 2.43112  2.93596 2.82442  2.80939 3.22403  2.69432 3.63062  2.5944 4.04491  2.51512 4.46754  2.46531 4.89881  2.45992 5.33766  2.52623 5.77874  2.71533 6.20316  3.10621 6.55775  3.73189 6.77633  4.61629 6.97293  5.36802 7.23286  5.88393 7.64123  4.55026 7.73043  3.71892 6.45533  3.4668 4.97397  3.68516 3.85621  4.78068 3.84595  6.19292 4.88864  7.35157 6.06477  7.76977 6.93931  6.44483 4.26612 49  3.39727 3.30167  3.729 3.77455  4.06235 4.24953  4.3974 4.72669  4.73425 5.20612  5.07301 5.68791  5.41377 6.17215  5.75665 6.6589  6.10176 7.14821  6.44921 7.64006  6.79908 8.13431  7.15135 8.6306  7.50581 9.12808  7.86175 9.62477  8.21707 10.1158  8.5648 10.5871  8.87361 10.9797  8.77222 10.6321  7.95184 9.13501  6.72429 7.55305  5.80865 7.30431  4.94529 8.47939  5.82739 9.62459  7.53309 9.12544  8.32274 7.73079  7.93102 6.17848  7.26714 5.11697  6.90449 4.27841  7.1238 3.44922  8.82289 2.90117  5.31564 1.66053  4.53624 1.5201  3.9417 1.51973  3.57666 1.67813  3.30579 1.92289  3.10673 2.19562  2.95313 2.47342  2.8287 2.75002  2.72428 3.02377  2.63439 3.29433  2.55555 3.56179  2.48542 3.82634  2.42236 4.0882  2.36514 4.34759  2.31286 4.60469  2.26481 4.85969  2.22043 5.11272  2.17926 5.36394  2.14297 5.59981 25  1.32114 2.07289  2.37628 2.44979  3.41099 2.92486  4.40552 3.52262  5.32495 4.27379  6.10651 5.21085  6.63724 6.34333  6.72124 7.54054  6.03814 7.8217  4.65939 6.89521  8.06583 8.72626  7.76416 10.829  6.93744 10.831  6.44036 10.5234  6.04502 10.2111  5.69272 9.89885  5.36613 9.58767  5.05725 9.27782  4.76159 8.9694  4.47633 8.6624  4.19953 8.35678  3.92981 8.05248  3.66616 7.74945  3.40777 7.44765  3.31723 7.34084 9  1.05133 3.49144  0.977792 4.93342  1.15934 6.40579  1.7234 7.86004  2.81679 9.17858  4.4883 10.1899  6.54077 10.8003  7.71263 11.1415  6.54919 10.5242" );

  boost::array<Curve, 5> curves;
  for ( unsigned i = 0; i < 5; ++i )
  {
    s >> curves[i];
  }

  Arrangement arr1, arr2, ovl;

  CGAL::insert_curves( arr1, curves.begin(), curves.begin() + 3 );
  CGAL::insert_curves( arr2, curves.begin() + 2 , curves.end() );


  Overlay_traits ot;
  BOOST_CHECK_NO_THROW( CGAL::overlay( arr1, arr2, ovl, ot ) );
  BOOST_CHECK( ovl.is_valid() );

}