2D Convex hull crash in CGAL

[kintel]

Reported by @More-Wrong.
See CGAL issue: CGAL/cgal#1703

w = 10;
t = 2;
$fn = 20;
hull() {
   translate([0,3*w/4]) {
      rotate([0,0,60]) {
         translate([-10, -w/2+0.05]) {
            square([10, t]);
         }
      }
   }
   translate([-w/2, -w/2+t]) {
      square([t, 0.000000000000001]);
   }
}

Stack trace:

#3	0x0000000101d57d70 in CGAL::postcondition_fail(char const*, char const*, int, char const*) ()
#4	0x00000001002c3590 in std::__1::back_insert_iterator<std::__1::list<CGAL::Point_2<CGAL::Cartesian<double> >, ... 
#5	0x00000001002bfa75 in std::__1::back_insert_iterator<std::__1::list<CGAL::Point_2<CGAL::Cartesian<double> >, ... 
#6	0x00000001002bfa21 in std::__1::back_insert_iterator<std::__1::list<CGAL::Point_2<CGAL::Cartesian<double> >, ... 
#7	0x00000001002b477d in std::__1::back_insert_iterator<std::__1::list<CGAL::Point_2<CGAL::Cartesian<double> >, ... 
#8	0x00000001002a1c80 in GeometryEvaluator::applyHull2D(AbstractNode const&) at /Users/kintel/code/OpenSCAD/openscad/src/GeometryEvaluator.cc:169

---

Want to back this issue? Post a bounty on it! We accept bounties via Bountysource.

[kintel]

Update from CGAL: convex_hull_2 needs an exact kernel

[nophead]

I thought OpenSCAD no longer used CGAL for 2D operations?

[kintel]

In general not, but we haven't found a suitable replacement for 2D convex hulls

[nophead]

Oh, I thought you had rolled your own. It is very simple in 2D. IIRC you find an extreme point and then look for the point which creates the biggest angle to it and so on as you go around the outside.

…

On 24 November 2016 at 18:40, Marius Kintel ***@***.***> wrote: In general not, but we haven't found a suitable replacement for 2D convex hulls — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#1871 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAijhVASPn6WoXdQOh_PSPI0zuTBx2Xiks5rBdoWgaJpZM4K7R6x> .

[donbright]

i would imagine that if you use fixed-width floating point coordinates, then translating and rotating a set of points in space will result in different topology for the hull at different orientations and locations. in other words if you traverse the points of the hull clockwise and print out each point's coordinates, you will get a different list depending on where the object is located in space.

[kintel]

@donbright That's pretty accurate. Not sure that topology would differ but certainly vertex count and relative position. Otoh, it already does as we perform 2D hulls using floating point coordinates.

[kintel]

The reported example now works without crashing.