Skip to Content.
Sympa Menu

cgal-discuss - Re: [cgal-discuss] Epick convex_hull_3 assertion

Subject: CGAL users discussion list

List archive

Re: [cgal-discuss] Epick convex_hull_3 assertion


Chronological Thread 
  • From: Marc Glisse <>
  • To:
  • Subject: Re: [cgal-discuss] Epick convex_hull_3 assertion
  • Date: Sat, 3 Jan 2015 23:31:07 +0100 (CET)

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



Archive powered by MHonArc 2.6.18.

Top of Page