Hacker News Reader

Comment by SOLAR_FIELDS | Hacker News Reader

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.

View on HN

> 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

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

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.

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)

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.

Reply on news.ycombinator.com