CGAL users discussion list

[Alex Tsui <>]

Attached, I will leave a small program and two data files that show the problem.

Running the test with a.dat will demonstrate that we unexpectedly find an intersection point between the upper quarter circle curve and the lower quarter circle curve after being made x-monotone. We expect them to be disjoint because there is a tiny subcurve separating them.

b.dat replaces the lower quarter circle with a straight-line segment with the same endpoints. Running the test with this shows that no intersection point is found, as we expect.

I tracked the source of the intersection point to a call on line 2442 in the Arr_geometry_traits/Bezier_x_monotone_2.h file, in the _intersect method. The details are beyond me at the moment, but I guess a way to proceed would be to compare why a.dat and b.dat yield different results.

On Mon, Jun 30, 2014 at 4:58 PM, atsui <> wrote:

This is not a solution but a continuation of investigating this bug.

I've tested the two-curve input on CGAL 4.4 and it fails at a different
point from what you had described. For me, it is trying to perform the sweep
line algorithm (see the _sweep method in Basic_sweep_line_2_impl.h:154) and
dies before finishing. Here's a trace that I generated by compiling with
CGAL_SL_VERBOSE defined: http://pastebin.com/xt0UQWGd

Note that the first curve that gets inserted is split as you said, into
(2.15 1.475 --> ~2.175 ~1.45) and (~2.175 ~1.45 --> 2.175 1.45). So the
expected result of inserting the input curves is 3 monotone curves:

A (2.15 1.475 --> ~2.175 ~1.45)
C (~2.175 ~1.45 --> 2.175 1.45)
B (2.175 1.45 --> 2.15 1.425)

The trouble starts on line 121 of the trace, where when setting up the
events, it tries to intersect B with A and "successfully" finds an
intersection point. In fact, A and B should be disjoint by the x-monotone
decomposition above. So that causes strange behavior downstream.

I actually also had no luck switching the order of the two input curves.



--
View this message in context: http://cgal-discuss.949826.n4.nabble.com/Precondition-violation-in-Bezier-x-monoton-2-h-using-Bezier-arrangement-tp4659201p4659495.html

Sent from the cgal-discuss mailing list archive at Nabble.com.

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss

find_package(CGAL COMPONENTS Core REQUIRED)
include(${CGAL_USE_FILE})
add_executable(test test.cpp)
target_link_libraries(test ${CGAL_LIBRARIES})

Attachment: a.dat
Description: MOPAC data

Attachment: b.dat
Description: MOPAC data

#include <fstream>
#include <CGAL/basic.h>
#ifndef CGAL_USE_CORE
#error "CGAL needs CORE."
#endif
#include <CGAL/Cartesian.h>
#include <CGAL/CORE_algebraic_number_traits.h>
#include <CGAL/Arr_Bezier_curve_traits_2.h>

typedef CGAL::CORE_algebraic_number_traits Nt_traits;
typedef Nt_traits::Rational Rational;
typedef Nt_traits::Algebraic Algebraic;
typedef CGAL::Cartesian<Rational> Rat_kernel;
typedef CGAL::Cartesian<Algebraic> Alg_kernel;
typedef CGAL::Arr_Bezier_curve_traits_2<Rat_kernel, Alg_kernel, Nt_traits>
  ArrTraitsType;
typedef ArrTraitsType::Point_2 Point_2;
typedef ArrTraitsType::Curve_2 Curve_2;
typedef ArrTraitsType::X_monotone_curve_2 X_monotone_curve_2;
typedef std::pair< Point_2, X_monotone_curve_2::Multiplicity >
  Intersection_point_2;

int main( int argc, char *argv[] )
{
  ArrTraitsType traits;

  if ( argc < 2 )
  {
    std::cout << "Usage: " << argv[0] << " bezier-curves-filename\n";
    return 1;
  }

  // Read the curves from the input file.
  std::ifstream inputFile( argv[1] );
  unsigned int n_curves;
  std::list<Curve_2> curves;
  Curve_2 B;
  unsigned int k;
  inputFile >> n_curves;
  std::cout << "\ninput curves:\n";
  for (k = 0; k < n_curves; k++) {
    // Read the current curve (specified by its control points).
    inputFile >> B;
    curves.push_back (B);
    std::cout << "  "
        << "B = {"
        << B
        << "}"
        << std::endl;
  }
  inputFile.close( );

  // make the curves monotone
  std::cout << "\nafter making x-monotone:\n";
  std::list<CGAL::Object> make_xcurves_res;
  std::vector<X_monotone_curve_2> xcurves;
  for (std::list<Curve_2>::iterator it = curves.begin( ); it != curves.end( ); ++it )
  {
    traits.make_x_monotone_2_object()( *it, std::back_inserter(make_xcurves_res) );
  }
  for (std::list<CGAL::Object>::iterator it = make_xcurves_res.begin( );
    it != make_xcurves_res.end( ); ++it )
  {
    X_monotone_curve_2 cv;
    if ( CGAL::assign( cv, *it ) )
    {
      std::cout << "  " << cv << "\n";
      std::cout << "  parameter range: "
        << "("
        << cv.parameter_range().first
        << " "
        << cv.parameter_range().second
        << ")"
        << "\n";
      xcurves.push_back( cv );
    }
  }

  // check particular a x-monotone curve pair for intersection
  std::list<CGAL::Object> intersect_res;
  traits.intersect_2_object()( xcurves[0], xcurves[2], std::back_inserter( intersect_res ) );
  std::cout << "\nintersection points found: "
    << intersect_res.size( )
    << "\n";
  for (std::list<CGAL::Object>::iterator it = intersect_res.begin( );
    it != intersect_res.end( ); ++it )
  {
    Intersection_point_2 int_pt;
    if ( CGAL::assign( int_pt, *it ) )
    {
      std::cout << "  "
        << int_pt.first
        << "\n";
    }
  }

  return 0;
}