Conforming triangulaions and kernels

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

Conforming triangulaions and kernels

Ben Supnik
Hi Y'all,

The docs for make_conforming_Delaunay_2 say that it requires
ConformingDelaunayTriangulationTraits_2. traits.

ConformingDelaunayTriangulationTraits_2 is labeled as having "Any model
of Kernel concept. In particular, all CGAL kernels."

But...this doesn't seem correct to me - am I right in thinking that some
CGAL exact pred exact construction kernels do not have sqrt?  The one I
was using did not, and I get a compile failure due to being unable to
tkae the sqrt of a number.

If sqrt is indeed required and not in all kernels, is there a way to get
an exact predicate/exact construction kernel without one of LEDA or GMP?

cheers
ben
--
Scenery Home Page: http://scenery.x-plane.com/
Scenery blog: http://xplanescenery.blogspot.com/
Plugin SDK: http://www.xsquawkbox.net/xpsdk/
X-Plane Wiki: http://wiki.x-plane.com/
Scenery mailing list: [hidden email]
Developer mailing list: [hidden email]
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Conforming triangulaions and kernels

Sylvain Pion
Administrator
Ben Supnik wrote:

> The docs for make_conforming_Delaunay_2 say that it requires
> ConformingDelaunayTriangulationTraits_2. traits.
>
> ConformingDelaunayTriangulationTraits_2 is labeled as having "Any model
> of Kernel concept. In particular, all CGAL kernels."
>
> But...this doesn't seem correct to me - am I right in thinking that some
> CGAL exact pred exact construction kernels do not have sqrt?  The one I
> was using did not, and I get a compile failure due to being unable to
> tkae the sqrt of a number.
>
> If sqrt is indeed required and not in all kernels, is there a way to get
> an exact predicate/exact construction kernel without one of LEDA or GMP?

Known issue (to me at least).

One way to cheat is to define a sqrt() function for the number type
that you use, and make it approximate (convert to double, use std::sqrt,
and convert back).  It might work for some/most rational number types,
and hopefully the algorithms won't break too much...

--
Sylvain Pion
INRIA Sophia-Antipolis
Geometrica Project-Team
CGAL, http://cgal.org/
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Conforming triangulaions and kernels

Fernando Cacciola-3
Hi Ben,
Hu Sylvain,

Sylvain Pion wrote:

> Ben Supnik wrote:
>> The docs for make_conforming_Delaunay_2 say that it requires
>> ConformingDelaunayTriangulationTraits_2. traits.
>>
>> ConformingDelaunayTriangulationTraits_2 is labeled as having "Any
>> model of Kernel concept. In particular, all CGAL kernels."
>>
>> But...this doesn't seem correct to me - am I right in thinking that
>> some CGAL exact pred exact construction kernels do not have sqrt?  The
>> one I was using did not, and I get a compile failure due to being
>> unable to tkae the sqrt of a number.
>>
>> If sqrt is indeed required and not in all kernels, is there a way to
>> get an exact predicate/exact construction kernel without one of LEDA
>> or GMP?
>
> Known issue (to me at least).
>
> One way to cheat is to define a sqrt() function for the number type
> that you use, and make it approximate (convert to double, use std::sqrt,
> and convert back).  It might work for some/most rational number types,
> and hopefully the algorithms won't break too much...
>

FWIW, the straight skeleton package uses such a cheat.

If you look at the header:

CGAL/constructions/Straight_skeleton_cons_ftC2.h

There is the function:

inexact_sqrt(num)

which does what Sylvain said.

You might wan't to base your version on that one.

It works for arbitrary number types, it uses CORE::BigFloat instead of double if
available, and if it uses double, it checks for overflow after the to_double
conversion, and for Quotient<NT> it avoids the division.


Best

Fernando Cacciola
www.geometryfactory.com

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Conforming triangulaions and kernels

avaxman
I use the babilonian method, which can approximate a square root in rational
numbers up to a certain precision. The best advantage of this method is that
two identical rational number would produce the same root. The drawback is that
it complicates the rational number greatly; For this, I truncate the number to
the precision (i.e., numerator*=10^PRECISION, integer x=div(numerator,
denominator), truncated=x/10^PRECISION).

Amir.

Quoting Fernando Cacciola <[hidden email]>:

> Hi Ben,
> Hu Sylvain,
>
> Sylvain Pion wrote:
> > Ben Supnik wrote:
> >> The docs for make_conforming_Delaunay_2 say that it requires
> >> ConformingDelaunayTriangulationTraits_2. traits.
> >>
> >> ConformingDelaunayTriangulationTraits_2 is labeled as having "Any
> >> model of Kernel concept. In particular, all CGAL kernels."
> >>
> >> But...this doesn't seem correct to me - am I right in thinking that
> >> some CGAL exact pred exact construction kernels do not have sqrt?  The
> >> one I was using did not, and I get a compile failure due to being
> >> unable to tkae the sqrt of a number.
> >>
> >> If sqrt is indeed required and not in all kernels, is there a way to
> >> get an exact predicate/exact construction kernel without one of LEDA
> >> or GMP?
> >
> > Known issue (to me at least).
> >
> > One way to cheat is to define a sqrt() function for the number type
> > that you use, and make it approximate (convert to double, use std::sqrt,
> > and convert back).  It might work for some/most rational number types,
> > and hopefully the algorithms won't break too much...
> >
>
> FWIW, the straight skeleton package uses such a cheat.
>
> If you look at the header:
>
> CGAL/constructions/Straight_skeleton_cons_ftC2.h
>
> There is the function:
>
> inexact_sqrt(num)
>
> which does what Sylvain said.
>
> You might wan't to base your version on that one.
>
> It works for arbitrary number types, it uses CORE::BigFloat instead of double
> if
> available, and if it uses double, it checks for overflow after the to_double
>
> conversion, and for Quotient<NT> it avoids the division.
>
>
> Best
>
> Fernando Cacciola
> www.geometryfactory.com
>
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://lists-sop.inria.fr/wws/info/cgal-discuss
>


--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss
Reply | Threaded
Open this post in threaded view
|

Re: Conforming triangulaions and kernels

Ben Supnik
In reply to this post by Fernando Cacciola-3
Hi Y'all,

Thanks - it does look like the sqrt function is used only to construct
splits, and I can probably survive with inexactness if my input isn't
too horribly degenerate. :-)

One more question: what's the least bad way for me to collect all of the
vertices inserted into my triangulation during the make-conforming
operation?

I don't see any notifier interface, so it looks like my options would
mostly involve overriding, er, something in the TDS to detect vertex
creation.

cheers
ben


Fernando Cacciola wrote:

> Hi Ben,
> Hu Sylvain,
>
> Sylvain Pion wrote:
>> Ben Supnik wrote:
>>> The docs for make_conforming_Delaunay_2 say that it requires
>>> ConformingDelaunayTriangulationTraits_2. traits.
>>>
>>> ConformingDelaunayTriangulationTraits_2 is labeled as having "Any
>>> model of Kernel concept. In particular, all CGAL kernels."
>>>
>>> But...this doesn't seem correct to me - am I right in thinking that
>>> some CGAL exact pred exact construction kernels do not have sqrt?  
>>> The one I was using did not, and I get a compile failure due to being
>>> unable to tkae the sqrt of a number.
>>>
>>> If sqrt is indeed required and not in all kernels, is there a way to
>>> get an exact predicate/exact construction kernel without one of LEDA
>>> or GMP?
>>
>> Known issue (to me at least).
>>
>> One way to cheat is to define a sqrt() function for the number type
>> that you use, and make it approximate (convert to double, use std::sqrt,
>> and convert back).  It might work for some/most rational number types,
>> and hopefully the algorithms won't break too much...
>>
>
> FWIW, the straight skeleton package uses such a cheat.
>
> If you look at the header:
>
> CGAL/constructions/Straight_skeleton_cons_ftC2.h
>
> There is the function:
>
> inexact_sqrt(num)
>
> which does what Sylvain said.
>
> You might wan't to base your version on that one.
>
> It works for arbitrary number types, it uses CORE::BigFloat instead of
> double if available, and if it uses double, it checks for overflow after
> the to_double conversion, and for Quotient<NT> it avoids the division.
>
>
> Best
>
> Fernando Cacciola
> www.geometryfactory.com
>

--
Scenery Home Page: http://scenery.x-plane.com/
Scenery blog: http://xplanescenery.blogspot.com/
Plugin SDK: http://www.xsquawkbox.net/xpsdk/
X-Plane Wiki: http://wiki.x-plane.com/
Scenery mailing list: [hidden email]
Developer mailing list: [hidden email]
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss