CGAL users discussion list

[Andreas Fabri <>]

Hi Jens,

just using a plain exact type is too slow.  You might try out
CGAL::Lazy_exact_nt<CGAL::Gmpq> as number type.  It performs
floating point computation, more precisely interval arithmetic
with an interval of floats. At the same time it stores the
arithmetic expression, so that if we cannot compute the result
of a predicate with it, we recur to a more expensive exact
number type.

best regards,

andreas

Jens Egeblad wrote:
> Hi
>
> Just to close this subject so that you don't have to worry anymore. I
> began using CGAL::Quotient<CGAL::MP_Float> right after my last post
> here last week.
>
> It is far too slow for my application so I am going to look for
> alternative ways to do what I am doing.  I had hoped that the CGAL
> implementation was robust for doubles using some sort of epsilon
> value, because rational numbers are too slow. I need it to be 10-100
> times faster than it is now.
>
> I had looked at alternative kernels. Unfortunately my arrangements are
> fairly complex consisting of lots of intersections and overlapping
> segments and 10000s of cells. So this is not a viable way.
>
> So, I guess I haev to get my hands dirty and implement an alternative 
> algorithm
>
> Thanks for all your help so far!
>
> - Jens
>
> On 3/6/07, Efraim Fogel 
> <>
>  wrote:
> > Let me add and say that using an exact number type should not intimidate
> > you. You can use the already defined kernel type
> > CGAL::Exact_predicates_exact_constructions_kernel. This may already give
> > you the performance you need.
> >
> > If you are not going to construct new geometric objects (e.g.,
> > intersection points) at all. For example, if you intend to use the
> > function CGAL::insert_non_intersecting_curve() and no other, use the
> > kernel type  Exact_predicates_inexact_constructions_kernel, which is
> > more efficient in this case.
> >
> > Efi Fogel wrote:
> >
> > > Jens Egeblad wrote:
> > >
> > >> Sorry to spam you like this.
> > >>
> > >> Ok, so as I suspected it seems like my problem has to do with
> > >> precision. I thought arrangement_2 was very robust. Am I missing
> > >> something?
> > >
> > >
> > > Arrangement_2, like the implementations of many other data structures
> > > and algorithms of CGAL, is robust. Robustness is guarantied only if an
> > > exact number type is used, and is achieved through the careful
> > > handling of all degenerate cases.
> > >
> > >>
> > >> I have been using doubles but I have no problem with MP_Float.
> > >>
> > >> I would really like to use an efficient number type since this is a
> > >> performance critical applications.
> > >>
> > >> Is MP_Float efficient enough or does anyone have better idea?
> > >
> > >
> > > If your curves are linear (and you use a Cartesian kernel), you need a
> > > rational number type. You could use CGAL::Quotient<CGAL::MP_Float>.
> > > You can try CGAL::Gmpq, which is an adaptation of an exact rational
> > > number type provided by GMP, and if you have access to Leda, you can
> > > try leda::rational.
> > >
> > >>
> > >> Best - Jens
> > >>
> > >> On 2/28/07, Jens Egeblad 
> > <>
> >  wrote:
> > >>
> > >>> Hi again
> > >>>
> > >>> I hope someone can help me out here... Anyway I did a little bit more
> > >>> research and these are the x/y-values of cv.left(), cv.right() and p.
> > >>>
> > >>> cv.left(): -4.241547e+01, 9.937383e-01,
> > >>> cv.right(): -4.241547e+01, 3.496869e+00,
> > >>> p: -4.241547e+01, 2.289501e+00
> > >>>
> > >>> Looks like it is a vertical edge, which seems a bit odd... Can
> > >>> anyone help?
> > >>>
> > >>> - Jens
> > >>>
> > >>> On 2/28/07, 
> >
> >  
> > <>
> >  wrote:
> > >>> > Hi
> > >>> >
> > >>> > I get an assertion when I try to build an arrangement with a lot
> > >>> of lines:
> > >>> >
> > >>> > CGAL error: precondition violation!
> > >>> > Expr: Segment_assertions::_assert_is_point_on (p, cv,
> > >>> Has_exact_division()) && compare_xy(cv.left(), p) == SMALLER &&
> > >>> compare_xy(cv.right(), p) == LARGER
> > >>> > File:
> > >>> /Users/jegeblad/CGAL_Install/include/CGAL/Arr_segment_traits_2.h
> > >>> > Line: 730
> > >>> > Abort trap
> > >>> >
> > >>> >
> > >>> > Does anyone know what could cause this problem? Could it be a
> > >>> floating-point problem?
> > >>> >
> > >>> > Best - Jens
> > >>> >
> > >>> > --
> > >>> > You are currently subscribed to cgal-discuss.
> > >>> > To unsubscribe or access the archives, go to
> > >>> > https://lists-sop.inria.fr/wws/info/cgal-discuss
> > >>> >
> > >>>
> >
> >
> > --
> >  ____  _        ____             _
> >  /_____/_) o    /__________  __  //
> > (____ (   (    (    (_/ (_/-(-'_(/
> >                        _/
> >
> > --
> > You are currently subscribed to cgal-discuss.
> > To unsubscribe or access the archives, go to
> > https://lists-sop.inria.fr/wws/info/cgal-discuss