CGAL users discussion list

[Ben Supnik <>]

Hi Jim,

When writing a buffering alg, the algorithm needs to either succeed in 
every geometric construction and predicate, or have specific alg-level 
fallback code to deal with "we ran out of bits, but the user can accept 
inexact output".  This second behavior has to be coded - the way the 
CGAL minkowski sum would fail due to rounding errors wouldn't be 
something you would want, it would involve potentially very strange output.

Not sure if this is bad form on the list, but if you want a buffering 
alg that can run strictly in floating point and give inexact results, 
GEOS/JTS does that.  It is not a true minkowski sum - it is more of a 
GIS buffering op.

I believe that at leaset _some_ of the Mikowski sum code is based on 
arrangement_2, which requires an exact kernel.

cheers
Ben


Jim Wilenius wrote:
> Hi!
>
> Thanks for replying! =)
>
> I would very much appreciate if you could explain in more detail...
>
> I don't understand why the kernel must be exact, even if new points are 
> created. Is this a specifically introduced limitation in CGAL or is it 
> that the use of inexact kernel causes errors due to floating point 
> representation which makes the algorithm throw exceptions.
>
> In my specific case, I would be satisfied if the precision of the 
> Point_2 is around 1E-9 which is very "dull" compared to the smallest 
> double. Is it possible to do this in CGAL? or do I need a new type of 
> Kernel. What I mean is, in my case, I can consider values to be the same 
> if the difference is "small". Is there a Kernel for this? 
> "epsilon_Kernel" =)
>
> I realize I should read more about Kernels... but in the mean time... =)
>
> Regards,
> Jim
>
>
> Efraim Fogel wrote:
> > During the computation of Minkowski sums new points might be
> > constructed. These points are used as operands of predicates. Thus, you
> > need an exact-construction kernel (as well as an exact-predicate
> > kernel). I didn't understand the second question.
> >
> > jim.wilenius wrote:
> > > Hi!
> > >  
> > >  I am using the CGAL lib in OSX 10.6. (freshly compiled, I followed the
> > > instructions carefully)
> > >
> > > I am using the CGAL::Exact_predicates_inexact_constructions_kernel 
> > > and when
> > > running minkowski sum I get:
> > > ---
> > > terminate called after throwing an instance of
> > > 'CGAL::Precondition_exception'
> > >   what():  CGAL ERROR: precondition violation!
> > > Expr: cv.is_in_x_range (p)
> > > File: /usr/local/include/CGAL/Arr_segment_traits_2.h
> > > Line: 486
> > > ---
> > >
> > > I get the error given the following two polygons (in order):
> > >
> > > P:
> > > 4
> > > 0.0 0.0
> > > 29.809108311772626 0.0
> > > 29.809108311772626 29.809108311772626
> > > 0.0 29.809108311772626
> > >
> > > Q:
> > > 7
> > > 99.10004234616522 202.2922116762398
> > > 168.16528534816382 202.2922116762398
> > > 168.16528534816382 271.3574546782384
> > > 154.3522367477641 271.3574546782384
> > > 140.53918814736437 243.73135747743896
> > > 126.72613954696467 229.91830887703924
> > > 99.10004234616522 216.1052602766395
> > >
> > > I am not sure exactly what the error means? Is it supposed to give an 
> > > error?
> > > If I use CGAL::Exact_predicates_exact_constructions_kernel then I do 
> > > not get
> > > the error.
> > >
> > > using exact constructions is extremely slow for my application, so I 
> > > would
> > > really like to use inexact.
> > >
> > > by the way, how inexact is the inexact kernel? Any pointers to useful 
> > > info
> > > is welcome.
> > >
> > > Regards,
> > > Jim
> > >   

--
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: 

Developer mailing list: