CGAL users discussion list

[stzpz <>]

Thanks very much for your reply!

For the first question, is that better to let the returning supporting_curve() contains the correct auxiliary data? Because the returning type of supporting_curve() is Arr_curve_data_traits_2.

In addition, I have one more question. Because I want to calculate the new control points of each sub bezier curve (X_monotone_curve_2), I use parameter_range() with de_Casteljau_2() to do that. But it seems that the returned values of parameter_range() is not so accurate for some case and hence influences the result of de_Casteljau_2(). For example, in the following code,

// ========= CODE BEGIN ==========

#include <CGAL/basic.h>

#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/Arr_curve_data_traits_2.h>

#include <CGAL/Arr_walk_along_line_point_location.h>

#include <CGAL/to_rational.h>

#include <list>

using namespace std;

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_org_2;

typedef Traits_org_2::Curve_2 Bezier_curve_2;

typedef unsigned int CurveNumber;

typedef CGAL::Arr_curve_data_traits_2<Traits_org_2, CurveNumber> Traits_2;

typedef Traits_2::Curve_2                               Bezier_curve_num_2;

typedef Traits_2::X_monotone_curve_2                    X_monotone_curve_2;

typedef Traits_2::Point_2 Point_2;

typedef CGAL::Arrangement_2<Traits_2>                   Arrangement_2;

typedef CGAL::Arr_walk_along_line_point_location<Arrangement_2>   Naive_pl;

#define TORAT(x) (CGAL::to_rational<Rational>((x)))

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

{

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

  std::ifstream   in_file (filename);

  int               n_curves;

  std::list<Bezier_curve_num_2>  curves;

  Bezier_curve_2             B;

  int               k;

  

  in_file >> n_curves;

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

    in_file >> B;

    Bezier_curve_num_2 bb(B, k);

    curves.push_back (bb);

  }

  

  Arrangement_2                     arr;

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

  

  Arrangement_2::Edge_iterator eit;

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

  {

      X_monotone_curve_2 x_curve = eit->curve();

      CurveNumber num = x_curve.data();

      if(num == 0) continue;  // only print the curve 1

      // ========= the source() and target() point is correct and accurate ==============

      cout<<"Curve "<<num<<": "<<x_curve.source()<<" -> "<<x_curve.target()<<endl;

      // ========= the parameter_range() to get to above points is not accurate ==========

      cout<<"\tParam range: "<<x_curve.parameter_range().first<<" "<<x_curve.parameter_range().second<<endl;

  }

  

  return 0;

}

// =========== CODE END =============

with test6.dat,

// =========== DATA BEGIN ============

2

2 20 80 100 0

2 -10 14 120 40

// =========== DATA END ==============

the accurate intersection point of this two line segments is (70, 30), and the new control point should also be (70, 30). The corresponding t value of the second line segment ( (-10, 14), (120, 40) ) should be 8/13 approximates 0.6154. But the second returning value of parameter_range() is 0.625. With that, the new control point becomes (71.25, 30.25), which is incorrect.

Is that a bug? And is there any other way to calculate new control points or t values of sub cubic bezier curves?

Thanks very much!

Sincerely yours,

Stzpz

2011/1/27 Sebastien Loriot (GeometryFactory) [via cgal-discuss] <[hidden email]>

stzpz wrote:

> Hello,
>
> I am willing to get the point location of a Bezier curves Arrangement, so I
> use Arr_Bezier_curve_traits_2 along with Arr_curve_data_traits_2 to
> construct the arrangement with auxiliary data (curve number) attached with
> each Bezier curve. And then I perform the point location function to get the
> outer connected boundaries of the point. Everything is fine except that the
> auxiliary data in the returning boundaries are incorrect.
>
> I use outer_ccb() to get the outer boundaries of the face, then use
> curve().supporting_curve() to get the original bezier curves with auxiliary
> data. The data in Bezier curves are correct. However, the auxiliary data
> corresponding with them are in correct. Here is the code:
>
> // =================== CODE BEGIN =====================
> #include <CGAL/basic.h>
> #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/Arr_curve_data_traits_2.h>
> #include <CGAL/Arr_walk_along_line_point_location.h>
> #include <CGAL/to_rational.h>
> #include <list>
> using namespace std;
>
> 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_org_2;
> typedef Traits_org_2::Curve_2 Bezier_curve_2;
>
> typedef unsigned int CurveNumber;
> typedef CGAL::Arr_curve_data_traits_2<Traits_org_2, CurveNumber> Traits_2;
>
> typedef Traits_2::Curve_2                               Bezier_curve_num_2;
> typedef Traits_2::Point_2 Point_2;
> typedef CGAL::Arrangement_2<Traits_2>                   Arrangement_2;
> typedef CGAL::Arr_walk_along_line_point_location<Arrangement_2>   Naive_pl;
>
> #define TORAT(x) (CGAL::to_rational<Rational>((x)))
>
> void point_loc(Arrangement_2 *arr) {
> Naive_pl pl(*arr);
>        
>         // this point is inside the face
> Point_2 p(TORAT(50), TORAT(40));
>
> CGAL::Object obj = pl.locate(p);
> Arrangement_2::Face_const_handle      f;
>    
> if (CGAL::assign(f, obj)) {
>     if(!f->is_unbounded()) {
> Arrangement_2::Ccb_halfedge_const_circulator bound_circ = f->outer_ccb();
>
> // first sub curve
>                 Bezier_curve_num_2 curr_curve_num =
> bound_circ->curve().supporting_curve();
>                 Bezier_curve_2 curr_curve = curr_curve_num;
>
>                 // ================ the result is INCORRECT of the next line
> ===================
>                 CurveNumber curve_num = curr_curve_num.data();
>                 cout<<"current curve num: "<<curve_num<<endl;
>                //
> ==================================================================
>         }
>     }
> }
>
> int main (int argc, char *argv[]) {
>   const char   *filename = (argc > 1) ? argv[1] : "test5.dat";
>   std::ifstream   in_file (filename);
>
>   int               n_curves;
>   std::list<Bezier_curve_num_2>  curves;
>   Bezier_curve_2             B;
>   int               k;
>  
>   in_file >> n_curves;
>   for (k = 0; k < n_curves; k++) {
>     in_file >> B;
>     Bezier_curve_num_2 bb(B, k);
>     curves.push_back (bb);
>   }
>  
>   Arrangement_2                     arr;
>   insert (arr, curves.begin(), curves.end());
>  
>   Arrangement_2::Edge_iterator eit;
>   for(eit = arr.edges_begin(); eit != arr.edges_end(); ++eit) {
>       // ============= this result is CORRECT ==============
>       int num = eit->curve().data();
>       std::cout<<"Current curve number:"<<num<<std::endl;
>       // =============================================
>   }
>  
>   point_loc(&arr);
>
>   return 0;
> }
> // =================== CODE END =====================
> The data file test5.dat is in below
> =================== DATA BEGIN =====================
> 3
> 2 0 0 100 100
> 2 20 80 100 0
> 2 -10 14 120 40
> =================== DATA END ======================
>
> Could anybody help me to find out how to get the correct auxiliary data in
> the returning boundaries constructed by point location algorithm?
>

Actually, there is no bug here.

Basically, Traits_2::X_monotone_curve_2 is a pair
(Traits_org_2::X_monotone_curve_2,CurveNumber)

No information is stored to get back to Traits_2::Curve_2 used
to create the X monotone curve. However, the information hold by
the Curve_2 is always copied to the X_monotone_curve_2.
Thus replacing

   CurveNumber curve_num = curr_curve_num.data();

by
   CurveNumber curve_num = bound_circ->curve().data();
will do what you want.

At this line:

Bezier_curve_num_2 curr_curve_num = bound_circ->curve().supporting_curve();

the constructor of Bezier_curve_num_2 is implicitly called with no data
(we should probably had an explicit keyword to that constructor).

(looking at the doc here:
http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Arrangement_on_surface_2_ref/Class_Arr_curve_data_traits_2.html#Cross_link_anchor_1223
you will see no constructor of X_monotone_curve_2 from Curve_2).

>
> Besides, it seems that Arr_Bezier_curves_traits_2 cannot handle some special
> case of curves like horizontal line segments. For example, using the code
> above and another data file below,
> =================== DATA BEGIN =====================
> 3
> 2 0 0 100 0
> 2 30 -20 30 80
> 2 100 -15 -20 75
> =================== DATA END ======================
> the program will terminate with assertion fails in line 770 of
> Bezier_curve_2.h when inserting bezier curves into arrangement. Is it a bug
> and how to fix it?

There indeed seems to have a bug here.

The fix will be posted here.
In the meantime, translating your data by 1 in the (0,1) direction
makes it work (the problem comes in the case the polynomial for y
coordinates is 0).

S.

>
>
> Does anyone know how to solve them? Thanks very much!
>
> Sincerely yours,
>
> Stzpz
>


--

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

---

If you reply to this email, your message will be added to the discussion below:

http://cgal-discuss.949826.n4.nabble.com/About-Bezier-curves-in-Arrangement-tp3238384p3241657.html

To unsubscribe from About Bezier curves in Arrangement, click here.

---

View this message in context: Re: About Bezier curves in Arrangement
Sent from the cgal-discuss mailing list archive at Nabble.com.