CGAL users discussion list

[Marc Glisse <>]

On Sat, 3 Jan 2015, Marius Kintel wrote:

> As the author of OpenSCAD, I get a lot of user testing of various CGAL 
> functions. I experience a lot of CGAL assertions, mostly due to malformed 
> data.
> This one looks suspiciously like a CGAL bug though:
>
> CGAL error: assertion violation!
> Expression : orientation(v1,v2,vz) != COPLANAR
> File       : 
> /Users/kintel/code/OpenSCAD/libraries/install/include/CGAL/convex_hull_3.h
> Line       : 350
>
> Looking at my minimal example below, it appears that CGAL is using two 
> different methods for determining whether three points are collinear; a 
> collinearity test and a coplanarity test involving a fourth point. The issue 
> seems to be that the second test is more strict than the first and this 
> second test is being used as an assert.
> If you look at the vertices in my code, it’s clear that it’s possible to 
> select three non-collinear vertices if a more strict test was used, this 
> avoiding the assertion error.

It does look like a bug, the algorithm apparently *constructs* (inexact) 
vectors, which seems to violate the CGAL philosophy of predicates. Maybe 
we could check instead if Traits_yz_3 says that the points are collinear 
(we don't seem to have a version of orientation taking 3 points and a 
vector).

--
Marc Glisse