6 ms·

CGAL – Computational Geometry Algorithms Library

147 points by lobo_tuerto 10y ago

santaclaus 10y ago
My experiences with CGAL: 1. Everything under the sun is implemented! 2. Horrible build system, giant dependency (worse than Boost here)... I wish they had gone header only like Eigen or ViennaCL. 3. Ugly license. Essentially a no-go everywhere I've worked, although still fine for academic projects.
- bjterry 10y ago
  CGAL is pretty cool. It was tricky to get set up. I was trying to use it as part of a mostly Python utility, and there are SWIG bindings for it that should theoretically have worked, but they were a huge pain and half the core functionality wasn't implemented at all even in the basic 2D kernel. After trying in vain to add the functionality I needed to the SWIG bindings, eventually I just wrote the core algorithm entirely in C++ (despite having no real C++ experience) and called into it from Cython. The API uses enough templated code that it would be hard to get going if you don't have a solid background in C++ or a language with an advanced type system (Haskell in my case). I didn't find it particularly difficult to get working with Homebrew. Given my scant knowledge of C++ build systems, I would have thought it would be a lot harder. If you are actually a C++ programmer I imagine it would be pretty straightforward. I agree that the licensing limits its uses quite a bit. The truth is that almost anything you build is probably going to use the GPL'd components. The only things that are LGPL are basic math and the geometry kernels.
  - droelf 10y ago
    I faced similar problems with the SWIG bindings ... almost impossible to add any functionality and they lack quite a lot of features. That's why I started a new set of Python bindings, based off the old ones and using pybind11: https://github.com/wolfv/pygal https://github.com/wolfv/pygal
- ska 10y ago
  How is dual licence ugly? It's not expensive for commercial use.
  - w0utert 10y ago
    It's quite expensive, especially if you only need one feature from one package that depends on multiple other GPL packages (which is most of them). Everything included we got quoted over $25K for a feature which was decidedly non-trivial, but the cost was still well above the "let's license it instead of re-implementing ourselves" threshold.
    - wiz21c 10y ago
      Considering http://www.cgal.org/exact.html http://www.cgal.org/exact.html I dare to say that 25K is not that much; if you had to do it yourself, it'd be probably very expensive (of course, I don't know how good you are :-) but you see what I mean). (and yes, I did 2 years of R&D on quad trees with polygon intersections and "exact computation" is super tough to achieve, you need lots of testing)
      - w0utert 10y ago
        For the application we were considering and the algorithms we liked from CGAL, exact computation wasn't really an issue. I agree 25K is peanuts if the choice is between developing yourself from scratch or licensing something from CGAL. But in our case the choice was between CGAL, using a simpler and possibly less advanced/less accurate solution, or using an alternative LGPL package. Especially considering the many dependencies most CGAL packages have on other packages, the value proposition for just using a small part of the library for a single algorithm quickly becomes a hard sell...
        ris 10y ago
        > For the application we were considering and the algorithms we liked from CGAL, exact computation wasn't really an issue. So it sounds more like you weren't trying to buy the right tool for the job.
- deleted 10y ago
  [deleted]
- geezerjay 10y ago
  > 2. Horrible build system, giant dependency (worse than Boost here)... I wish they had gone header only like Eigen or ViennaCL. I assume that Eigen went header only because that library is mostly template metaprogramming (and a master class at that).
SOLAR_FIELDS 10y ago
This is the golden standard for geometric libraries. If you are building a geometric library and want to scale it up to enterprise levels you cannot do better than starting from this. It's built by a consortium of universities who have contributed many many years of research in computational geometry to its codebase. It solves edge cases that GEOS/JTS have not come close to solving. If you need something to just do calculations for display on a Leaflet map, PostGIS/JTS/GEOS/Turf.js will do just fine. If you want to build something that needs to be rock solid, lightning fast, and 100% accurate in all cases, use this library.
- santaclaus 10y ago
  > If you want to build something that needs to be rock solid, lightning fast, and 100% accurate in all cases, use this library. Ehhhh depends what bits of CGAL you are using. Their mesh booleans kind of suck.
- jayeshsalvi 10y ago
  I would recommend OpenCASCADE. It's more thorough geometry kernel for any CAD applications. https://en.wikipedia.org/wiki/Open_Cascade_Technology https://en.wikipedia.org/wiki/Open_Cascade_Technology
  - haldean 10y ago
    I would recommend against OCC; for a time, my full-time job was fighting its total lack of reliability and debuggability. It sets a new bar for impossible-to-understand C++ code (a bar I thought boost had set so high it was impassable) and its error reporting is totally useless (every exception is exactly the same: StdFail_NotDone. Good luck figuring out what went wrong) CGAL's pretty good; they've got an implementation for everything but not all of them are worth using. I just got done reimplementing the RANSAC algorithm in a client's codebase because CGAL's was super slow. But on the whole, it's an amazing feat of open source software. If you can pony up, though, Parasolid is where it's at. Hands down the most reliable geometry kernel I've ever used, and their support is fantastic.
    - 10y ago
ioquatix 10y ago
This is used by OpenSCAD for building meshes from boolean operations. It's awesome, but a bit slow if you do anything complex.
je42 10y ago
libigl also has some wrappers around cgal.
tschmidt 10y ago
Is anyone working on Rust bindings?
- marvy 10y ago
  I doubt it. The library seems very happy to exploit whatever C++ features are available, especially templates, to the point where I wonder how easy it would be to use from a language where templates are even slightly different compared to how C++ does it. Could you port the STL to Rust? I don't know Rust, so I can't answer that. But if not, then there's not much hope of CGAL bindings.
droelf 10y ago
I've used CGAL extensively in the past and found the implemented algorithms to be of fantastic quality. The major pain points for me were also the really sub-par Python bindings. Which are actually worse now, since they've switched over to SWIG from Boost.Python. If anyone ever needs Python bindings for CGAL that make sense, check my little pet project out: https://github.com/wolfv/pygal https://github.com/wolfv/pygal :)
marcosscriven 10y ago
It was a while ago now, but managed to get a Javascript build of this going with Emscripten: https://github.com/marcosscriven/cgaljs https://github.com/marcosscriven/cgaljs
abetusk 10y ago
My experience with CGAL is that it's slow, clunky and very difficult to work with. I understand that it's the 'gold standard' of libraries but for the purpose I was using it for (2d polygon boolean operations, polygon offsetting), I found ClipperLib [1] to be far superior in terms of ease of use, stability and execution speed. There's even a JavaScript port of ClipperLib [2]. I highly recommend ClipperLib to anyone that only needs simple 2d polygon manipulation. [1] http://angusj.com/delphi/clipper.php http://angusj.com/delphi/clipper.php [2] https://sourceforge.net/p/jsclipper/wiki/documentation/ https://sourceforge.net/p/jsclipper/wiki/documentation/
- geezerjay 10y ago
  > My experience with CGAL is that it's slow, clunky and very difficult to work with. I can't comment on the slowness and clunkyness, but in my very limited experience with CGAL I also felt it was needlessly difficult to work with. Perhaps investing some work in the documentation would help shed this idea.
mrcactu5 10y ago
Python bindings for CGAL -- no subsitute for reading through the C code (or implementing your own crude algorithms) https://github.com/sciencectn/cgal-bindings https://github.com/sciencectn/cgal-bindings

147 points by lobo_tuerto 10y ago

My experiences with CGAL: 1. Everything under the sun is implemented! 2. Horrible build system, giant dependency (worse than Boost here)... I wish they had gone header only like Eigen or ViennaCL. 3. Ugly license. Essentially a no-go everywhere I've worked, although still fine for academic projects.

bjterry 10y ago
CGAL is pretty cool. It was tricky to get set up. I was trying to use it as part of a mostly Python utility, and there are SWIG bindings for it that should theoretically have worked, but they were a huge pain and half the core functionality wasn't implemented at all even in the basic 2D kernel. After trying in vain to add the functionality I needed to the SWIG bindings, eventually I just wrote the core algorithm entirely in C++ (despite having no real C++ experience) and called into it from Cython. The API uses enough templated code that it would be hard to get going if you don't have a solid background in C++ or a language with an advanced type system (Haskell in my case). I didn't find it particularly difficult to get working with Homebrew. Given my scant knowledge of C++ build systems, I would have thought it would be a lot harder. If you are actually a C++ programmer I imagine it would be pretty straightforward. I agree that the licensing limits its uses quite a bit. The truth is that almost anything you build is probably going to use the GPL'd components. The only things that are LGPL are basic math and the geometry kernels.
- droelf 10y ago
  I faced similar problems with the SWIG bindings ... almost impossible to add any functionality and they lack quite a lot of features. That's why I started a new set of Python bindings, based off the old ones and using pybind11: https://github.com/wolfv/pygal https://github.com/wolfv/pygal
ska 10y ago
How is dual licence ugly? It's not expensive for commercial use.
- w0utert 10y ago
  It's quite expensive, especially if you only need one feature from one package that depends on multiple other GPL packages (which is most of them). Everything included we got quoted over $25K for a feature which was decidedly non-trivial, but the cost was still well above the "let's license it instead of re-implementing ourselves" threshold.
  - wiz21c 10y ago
    Considering http://www.cgal.org/exact.html http://www.cgal.org/exact.html I dare to say that 25K is not that much; if you had to do it yourself, it'd be probably very expensive (of course, I don't know how good you are :-) but you see what I mean). (and yes, I did 2 years of R&D on quad trees with polygon intersections and "exact computation" is super tough to achieve, you need lots of testing)
    - w0utert 10y ago
      For the application we were considering and the algorithms we liked from CGAL, exact computation wasn't really an issue. I agree 25K is peanuts if the choice is between developing yourself from scratch or licensing something from CGAL. But in our case the choice was between CGAL, using a simpler and possibly less advanced/less accurate solution, or using an alternative LGPL package. Especially considering the many dependencies most CGAL packages have on other packages, the value proposition for just using a small part of the library for a single algorithm quickly becomes a hard sell...
      - ris 10y ago
        > For the application we were considering and the algorithms we liked from CGAL, exact computation wasn't really an issue. So it sounds more like you weren't trying to buy the right tool for the job.
deleted 10y ago
[deleted]
geezerjay 10y ago
> 2. Horrible build system, giant dependency (worse than Boost here)... I wish they had gone header only like Eigen or ViennaCL. I assume that Eigen went header only because that library is mostly template metaprogramming (and a master class at that).

SOLAR_FIELDS 10y ago

This is the golden standard for geometric libraries. If you are building a geometric library and want to scale it up to enterprise levels you cannot do better than starting from this. It's built by a consortium of universities who have contributed many many years of research in computational geometry to its codebase. It solves edge cases that GEOS/JTS have not come close to solving. If you need something to just do calculations for display on a Leaflet map, PostGIS/JTS/GEOS/Turf.js will do just fine. If you want to build something that needs to be rock solid, lightning fast, and 100% accurate in all cases, use this library.

santaclaus 10y ago
> If you want to build something that needs to be rock solid, lightning fast, and 100% accurate in all cases, use this library. Ehhhh depends what bits of CGAL you are using. Their mesh booleans kind of suck.
jayeshsalvi 10y ago
I would recommend OpenCASCADE. It's more thorough geometry kernel for any CAD applications. https://en.wikipedia.org/wiki/Open_Cascade_Technology https://en.wikipedia.org/wiki/Open_Cascade_Technology
- haldean 10y ago
  I would recommend against OCC; for a time, my full-time job was fighting its total lack of reliability and debuggability. It sets a new bar for impossible-to-understand C++ code (a bar I thought boost had set so high it was impassable) and its error reporting is totally useless (every exception is exactly the same: StdFail_NotDone. Good luck figuring out what went wrong) CGAL's pretty good; they've got an implementation for everything but not all of them are worth using. I just got done reimplementing the RANSAC algorithm in a client's codebase because CGAL's was super slow. But on the whole, it's an amazing feat of open source software. If you can pony up, though, Parasolid is where it's at. Hands down the most reliable geometry kernel I've ever used, and their support is fantastic.
  - 10y ago

ioquatix 10y ago

This is used by OpenSCAD for building meshes from boolean operations. It's awesome, but a bit slow if you do anything complex.

je42 10y ago

libigl also has some wrappers around cgal.

tschmidt 10y ago

Is anyone working on Rust bindings?

marvy 10y ago
I doubt it. The library seems very happy to exploit whatever C++ features are available, especially templates, to the point where I wonder how easy it would be to use from a language where templates are even slightly different compared to how C++ does it. Could you port the STL to Rust? I don't know Rust, so I can't answer that. But if not, then there's not much hope of CGAL bindings.

droelf 10y ago

I've used CGAL extensively in the past and found the implemented algorithms to be of fantastic quality. The major pain points for me were also the really sub-par Python bindings. Which are actually worse now, since they've switched over to SWIG from Boost.Python. If anyone ever needs Python bindings for CGAL that make sense, check my little pet project out: https://github.com/wolfv/pygal https://github.com/wolfv/pygal :)

marcosscriven 10y ago

It was a while ago now, but managed to get a Javascript build of this going with Emscripten: https://github.com/marcosscriven/cgaljs https://github.com/marcosscriven/cgaljs

abetusk 10y ago

My experience with CGAL is that it's slow, clunky and very difficult to work with. I understand that it's the 'gold standard' of libraries but for the purpose I was using it for (2d polygon boolean operations, polygon offsetting), I found ClipperLib [1] to be far superior in terms of ease of use, stability and execution speed. There's even a JavaScript port of ClipperLib [2]. I highly recommend ClipperLib to anyone that only needs simple 2d polygon manipulation. [1] http://angusj.com/delphi/clipper.php http://angusj.com/delphi/clipper.php [2] https://sourceforge.net/p/jsclipper/wiki/documentation/ https://sourceforge.net/p/jsclipper/wiki/documentation/

geezerjay 10y ago
> My experience with CGAL is that it's slow, clunky and very difficult to work with. I can't comment on the slowness and clunkyness, but in my very limited experience with CGAL I also felt it was needlessly difficult to work with. Perhaps investing some work in the documentation would help shed this idea.

mrcactu5 10y ago

Python bindings for CGAL -- no subsitute for reading through the C code (or implementing your own crude algorithms) https://github.com/sciencectn/cgal-bindings https://github.com/sciencectn/cgal-bindings