CGAL users discussion list

["Jeb Gaither" <>]

Hi Efi,

 

Thank you very much for your answer. I will keep you posted as I progress.

 

For your information, the Bezier Curves which have the issues are derived from self intersecting Bezier Splines.  I suspect I may be losing some accuracy in the conversion process.

 

One other quick question. So far I have successfully used CGAL Arrangements for shapes composed of either Polylines or Beziers Curves.  I would like to add mixed mode shapes with both types of edges. My plan is to covert lines to "straight"  Cubic Bezier Curves. Do you have any alternatives suggestions?

 

Thank you again.

 

Jeb

 

From: [mailto:] On Behalf Of Efi Fogel ( via cgal-discuss Mailing List)
Sent: Thursday, July 02, 2020 4:40 AM
To:
Subject: Re: [cgal-discuss] Precondition Violations Using CGAL Bezier Curves Arrangement

 

Hi Jeb,

 

You may know most or all of the facts below, but for the sake of other readers I repeat it.

 

Saving an arrangement instantiated with the Bezier geometry traits and reading back the saved information directly is impossible (without the risk of encountering problems caused by limited precision). The reason, in general, is because (intersection) points do not have exact representation; you can only obtain an approximation.

 

The solution is to save the curves that induced the arrangement in the first place.

Observe that you need to save the original curves (before inserted into the arrangement) and not the curves that are the geometric embeddings of the edges of the arrangement.

Then, to restore the arrangement, you need to read the curves and insert them into an arrangement (essentially re-constructing the arrangement).

 

Saving the curves must be done in an exact way, that is, the coordinates of the control points must be saved in an exact manner.

 

PS, you can write

os << CGAL::exact(x)

for any kernel object x. However you will need to provide your own (rather simple) implementation for exporting an object of the Curve_2 type of the Bezier traits.

I think that I'll add it to some future release of CGAL, but it may take some time...

 

Cheers,

Efi

   ____  _        ____             _
  /_____/_) o    /__________  __  //
 (____ (   (    (    (_/ (_/-(-'_(/
                         _/

 

 

On Thu, 2 Jul 2020 at 00:41, Jeb Gaither <> wrote:

Hello,

 

Problem Description

 

I have successfully used the C:\del64\CGAL-5.0.1\examples\Arrangement_on_surface_2\build\Debug\Bezier_curves.exe for several years using different versions of CGAL as they have become available. My only modifications to the example code are to load the curves from a file and save the results to a file.

 

Recently I have been encountering a number of precondition violations. I have observed that sometimes if I repeatedly run the program with the same set of curves, once in a while it will produce a violation free result.

 

In reviewing other situations where individuals have encountered precondition violations, the solution is to change to an exact solution.

 

I cannot figure out how to do this for Bezier Curves.

 

I have include my source code and a failure example below.

 

Thank you!

 

Jeb Gaither

 

 

Source Code

 

//! \file examples/Arrangement_on_surface_2/Bezier_curves.cpp

// Constructing an arrangement of Bezier curves.

 

#include <fstream>

 

#include <CGAL/basic.h>

 

#ifndef CGAL_USE_CORE

#include <iostream>

int main ()

{

  std::cout << "Sorry, this example needs CORE ..." << std::endl;

  return 0;

}

#else

 

#include <CGAL/Cartesian.h>

#include <CGAL/CORE_algebraic_number_traits.h>

#include <CGAL/Arr_Bezier_curve_traits_2.h>

#include <CGAL/Arrangement_2.h>

#include <CGAL/IO/Arr_iostream.h>

 

#include "arr_inexact_construction_segments.h"

#include "arr_print.h"

 

typedef CGAL::CORE_algebraic_number_traits              Nt_traits;

typedef Nt_traits::Rational                             NT;

typedef Nt_traits::Rational                             Rational;

typedef Nt_traits::Algebraic                            Algebraic;

typedef CGAL::Cartesian<Rational>                       Rat_kernel;

typedef CGAL::Cartesian<Algebraic>                      Alg_kernel;

typedef Rat_kernel::Point_2                             Rat_point_2;

typedef CGAL::Arr_Bezier_curve_traits_2<Rat_kernel, Alg_kernel, Nt_traits>

                                                        Traits_2;

typedef Traits_2::Curve_2                               Bezier_curve_2;

typedef CGAL::Arrangement_2<Traits_2>                   Arrangement_2;

//typedef CGAL::Arrangement_2<Traits_2>                   Arrangement;

 

//-----------------------------------------------------------------------------

// Save all vertices (points) and edges (curves) along a connected component

// boundary.

//

template<class Arrangement>

void save_ccb(typename Arrangement::Ccb_halfedge_const_circulator circ,std::ofstream &aOutputFile)

{

                typename Arrangement::Ccb_halfedge_const_circulator  curr = circ;

                typename Arrangement::Halfedge_const_handle          he;

 

                aOutputFile << "(" << curr->source()->point() << ")";

                aOutputFile << std::endl;

                do

                {

                                he = curr;

                                aOutputFile << "   [" << he->curve() << "]   "

                                                << "(" << he->target()->point() << ")";

                                aOutputFile << std::endl;

                                ++curr;

                } while (curr != circ);

                aOutputFile << std::endl;

 

                return;

}

 

//-----------------------------------------------------------------------------

// Save the boundary description of an arrangement face.

//

template<class Arrangement>

void save_face(typename typename Arrangement::Face_const_handle f, std::ofstream &aOutputFile)

{

                // Print the outer boundary.

                if (f->is_unbounded())

                {

                                aOutputFile << "Unbounded face. " << std::endl;

                }

                else

                {

                                aOutputFile << "Outer boundary: ";

                                print_ccb<Arrangement>(f->outer_ccb(), aOutputFile);

                                aOutputFile << std::endl;

                }

 

                // 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)

                {

                                aOutputFile << "    Hole #" << index << ": ";

                                print_ccb<Arrangement>(*hole, aOutputFile);

                                aOutputFile << std::endl;

                }

 

                // 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)

                {

                                aOutputFile << "    Isolated vertex #" << index << ": "

                                                << "(" << iv->point() << ")" << std::endl;

                }

 

                return;

}

 

 

//-----------------------------------------------------------------------------

// Save the given arrangement to file.

//

template<class Arrangement>

void save_arrangement(const Arrangement& arr, std::ofstream &aOutputFile)

{

                CGAL_precondition(arr.is_valid());

 

                // Print the arrangement vertices.

                typename Arrangement::Vertex_const_iterator  vit;

 

                aOutputFile << arr.number_of_vertices() << " vertices:" << std::endl;

                for (vit = arr.vertices_begin(); vit != arr.vertices_end(); ++vit)

                {

                                aOutputFile << "(" << vit->point() << ")";

                                if (vit->is_isolated())

                                                aOutputFile << " - Isolated." << std::endl;

                                else

                                                aOutputFile << " - degree " << vit->degree() << std::endl;

                }

 

                // Print the arrangement edges.

                typename Arrangement::Edge_const_iterator    eit;

 

                aOutputFile << arr.number_of_edges() << " edges:" << std::endl;

                for (eit = arr.edges_begin(); eit != arr.edges_end(); ++eit)

                {

                                aOutputFile << "[" << eit->curve() << "]" << std::endl;

                }

                // Print the arrangement faces.

                typename Arrangement::Face_const_iterator    fit;

 

                aOutputFile << arr.number_of_faces() << " faces:" << std::endl;

                for (fit = arr.faces_begin(); fit != arr.faces_end(); ++fit)

                {

//                            save_face(fit->face(), aOutputFile);

// Print the outer boundary.

                                if (fit->is_unbounded())

                                {

                                                aOutputFile << "Unbounded face. " << std::endl;

                                }

                                else

                                {

                                                aOutputFile << "Outer boundary: ";

                                                save_ccb<Arrangement>(fit->outer_ccb(), aOutputFile);

                                }

 

                                // Print the boundary of each of the holes.

                                typename Arrangement::Hole_const_iterator  hole;

                                int                                         index = 1;

 

                                for (hole = fit->holes_begin(); hole != fit->holes_end(); ++hole, ++index)

                                {

                                                aOutputFile << "    Hole #" << index << ": ";

                                                save_ccb<Arrangement>(*hole, aOutputFile);

                                }

 

                                // Print the isolated vertices.

                                typename Arrangement::Isolated_vertex_const_iterator  iv;

 

                                for (iv = fit->isolated_vertices_begin(), index = 1;

                                                iv != fit->isolated_vertices_end(); ++iv, ++index)

                                {

                                                aOutputFile << "    Isolated vertex #" << index << ": "

                                                                << "(" << iv->point() << ")" << std::endl;

                                }

 

                }

 

                return;

}

 

int main (int argc, char *argv[])

{

  // Get the name of the input file from the command line, or use the default

  // Bezier.dat file if no command-line parameters are given.

                const char   *filename = (argc > 1) ? argv[1] : "Bezier.dat";

                const char   *outfilename = (argc > 1) ? argv[1] : "BezierOut.dat";

 

  // Open the input file.

  std::ifstream   in_file (filename);

 

  if (! in_file.is_open()) {

    std::cerr << "Failed to open " << filename << std::endl;

    return 1;

  }

 

  // Read the curves from the input file.

  unsigned int               n_curves;

 std::list<Bezier_curve_2>  curves;

  Bezier_curve_2             B;

  unsigned int               k;

 

  in_file >> n_curves;

  for (k = 0; k < n_curves; k++) {

    // Read the current curve (specified by its control points).

    in_file >> B;

    curves.push_back (B);

 

    std::cout << "B = {" << B << "}" << std::endl;

  }

  in_file.close();

 

  // Construct the arrangement.

 

  Arrangement_2                   arr;

  insert (arr, curves.begin(), curves.end());

 

  // Print the arrangement size.

  std::ofstream out_file(outfilename);

  out_file << "The arrangement size:" << std::endl

                                                << "   V = " << arr.number_of_vertices()

            << ",  E = " << arr.number_of_edges()

            << ",  F = " << arr.number_of_faces() << std::endl;

 

//  out_file << arr;

  save_arrangement(arr,out_file);

  out_file.close();

 

  return 0;

}

 

#endif

 

Failure Example

 

B = {4  3711507924 2865278219  3387450460 2979371134  3732852274 765306650  4082921600 751693496}

B = {4  4082921600 751693496  138023630 738080342  492760467 2924918518  150946400 2833985697}

B = {4  150946400 2833985697  4104099630 2743052877  3065734660 374349059  3364942830 563526687}

B = {4  3364942830 563526687  3664151001 752704315  1005965016 3499763387  780346946 3228647410}

B = {4  780346946 3228647410  554728876 2957531432  2761678721 3963207703  2889287872 4291330058}

B = {4  2889287872 4291330058  3016897023 324485117  1065165481 4270020853  1050800113 3916166178}

B = {4  1050800113 3916166178  1036434745 3562311503  2959435552 3204033711  2856266200 3548982900}

B = {4  2856266200 3548982900  2753096848 3893932088  623757336 647140960  837105897 345708045}

B = {4  837105897 345708045  1050454457 44275131  3606491089 2688200429  3301513570 2915003916}

B = {4  3301513570 2915003916  2996536052 3141807404  4125511678 951489078  198993326 823727760}

B = {4  198993326 823727760  567442270 695966440  175364532 2630762126  4073586476 2644375203}

B = {4  4073586476 2644375203  3676841125 2657988281  3275428162 750418751  3661633657 855020001}

B = {4  3661633657 855020001  4047839152 959621250  926695811 3076393280  589726066 2861216888}

B = {4  589726066 2861216888  252756322 2646040497  2699960175 98915684  2953013560 405815950}

B = {4  2953013560 405815950  3206066946 712716216  1264969863 3873641561  1122937075 3503452199}

B = {4  1122937075 3503452199  980904286 3133262837  2637935791 3526926066  2652301229 3925012512}

B = {4  2652301229 3925012512  2666666667 28131662  1038366037 430641326  1155958989 43625208}

B = {4  1155958989 43625208  1273551940 3951576384  3137038473 2775034485  2896254476 3112251688}

B = {4  2896254476 3112251688  2655470480 3449468891  310415954 1005477905  653155187 752675593}

B = {4  653155187 752675593  995894419 499873282  4026427409 2438259646  3613587087 2579689395}

B = {4  3613587087 2579689395  3200746765 2721119143  3639500427 1065592276  4082921600 1051979157}

B = {4  4082921600 1051979157  231375477 1038366037  679464162 2666666667  248867213 2548397013}

B = {4  248867213 2548397013  4113237559 2430127360  2803954977 565287424  3693372790 319518432}

CGAL error: precondition violation!

_expression_ : comp_f(object, nodeP->object) != LARGER

File       : C:\del64\CGAL 5.01\include\CGAL/Multiset.h

Line       : 2131

Explanation:

Refer to the bug-reporting instructions at https://www.cgal.org/bug_report.html

 

C:\del64\CGAL-5.0.1\examples\Arrangement_on_surface_2\build\Debug\Bezier_curves.exe (process 5928) exited with code -1.

To automatically close the console when debugging stops, enable Tools->Options->Debugging->Automatically close the console when debugging stops.

Press any key to close this window . . .

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

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