CGAL – Computational Geometry Algorithms Library | Hacker News Reader

CGAL – Computational Geometry Algorithms Library

cgal.org

147 pointslobo_tuerto32 comments

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.

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.

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

How is dual licence ugly? It's not expensive for commercial use.

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.

Considering

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)

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

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

25k is actually pretty cheap for this sort of numerical work. That's also licensing about a quarter of the entire library, regardless of how much your actually using.

To put that in context, 25k is roughly the fully loaded cost of a developer month, if they can do this sort of work properly.

Plenty of specialized libraries out there will cost you twice (or more) as much to acquire and a % on your shipped product.

Thinking of this as expensive is either naive, or just the wrong tool for the job.

And if you're charging for the resulting software then objecting to being charged in return is simply entitlement.

> 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).

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.

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

I would recommend OpenCASCADE. It's more thorough geometry kernel for any CAD applications. https://en.wikipedia.org/wiki/Open_Cascade_Technology

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.

I agree with Parasolid being the best geometry kernel out there! (It's quite expensive though, around $60k per year + revenue share)

Isn't CGAL a dependency for PostGIS? When would you choose to use CGAL directly rather than something built on top of it (e.g. PostGIS or pgrouting)?

My use case is mostly for routing and I'm currently using a heavily modified version of OSRM. If there's potential for even more speedup I'd appreciate any resources ou can point me towards.

PostGIS uses GEOS which is a port of JTS or CGAL depending on what "part" of PostGIS you are using.

I'm unaware of CGAL's networking support, our use case depends heavily on the standard DE9-IM relationships. I would look into graph databases like Neo4j for shortest-path and other types of network analysis. They will probably perform better than pgrouting and make it easier for you to conceptualize the problem.

If you need to do huge operations at scale (i.e. things that are just too big to fit in PostGIS and provide reliability/performance) or need 100% accuracy, I would go with straight CGAL. If not, higher level geometric implementations and platforms are probably going to do just fine.

You might be thinking of GDAL.

CGAL too, in the form of SFCGAL, that implements simple features on top of CGAL.

> rock solid, lightning fast, and 100% accurate in all cases

This is like the CAP theorem[1], but for computational geometry libraries. You cannot have all 3 if your truly are aiming for accuracy, speed, or robustness. There is always another edge case (which turns out to be a common case for you), there is always another computational shortcut (cutting out seat belts for cases you know you won't encounter), and there is always a missing function (that you really need). CGAL is a terrific reference implementation for a remarkably diverse set of algorithms, and its commitment to precision in particular is astounding[2].

All that said, never trust the output of a geometry library function that has not been thoroughly fuzz tested. I guarantee that every one of these libraries will fail in surprising ways when subjected to a brutal fuzz tester. I say this as the author of one of the libraries, and as someone who is familiar with the quirks of all of them. In my experience, the best geometry libraries do one tiny task very fast (backed up by benchmarks) and very reliably (verified through unit and fuzz tests).

[1] https://en.wikipedia.org/wiki/CAP_theorem [2] http://www.cgal.org/exact.html

Writing a useful fuzz-tester for a library like CGAL would be an interesting research problem. CGAL makes it a lot easier for many algorithms because it implements certifying algorithms [1] wherever possible.

[1] https://en.wikipedia.org/wiki/Certifying_algorithm

While JTS and its children might not have loads of algorithms or the fastest implementations, it is rock solid and 99% accurate (I challenge your 100% obviously). If you just need the basic stuff, JTS etc are a great choice.

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 [2] https://sourceforge.net/p/jsclipper/wiki/documentation/

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

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

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

Python bindings for CGAL -- no subsitute for reading through the C code (or implementing your own crude algorithms)

https://github.com/sciencectn/cgal-bindings

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

libigl also has some wrappers around cgal.

Is anyone working on Rust bindings?

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.

Reply on news.ycombinator.com