Computational Geometry in Python | Hacker News Reader

Computational Geometry in Python

blancosilva.github.io

113 pointsics14 comments

That's nice. It looks so simple in Python.

I notice that for convex hulls, they just use a wrapper around QHull. Doing convex hulls well is quite hard. If you intend to use them for collision detection, they must really be convex. The slightest concavity will cause the algorithm to stall at a local minimum. There's also the question of whether faces should be triangular or polygonal. If they're triangular, the convex hull of a cube has coplanar faces, which is bad. If they're polygonal, the polygon will not have perfectly flat faces due to finite precision and may have false convexity. A good compromise, supported in QHull, is to specify a minimum angle for edges. If you require, say, 1 degree of bend at each edge, most of the annoying corner cases go away.

The next step after that intro is constructive solid geometry, where you have union and intersection operations. 3D CAD systems use those heavily. This used to be considered very hard to do. Now you can do it in the browser: http://evanw.github.io/csg.js/

I have yet to see a 100% bulletproof CSG system, unfortunately. The open source packages (Carve, Cork, and others) and the implementations in all commercial packages I have tried will work 99% of the time, but fail horribly on the remaining 1%. This makes their use in automated pipelines tricky. With that said, the solutions out there today are way better than those available even five years ago.

It's hardest for CSG systems that can't say no. If you use Autodesk Inventor, there are some geometries where the fillet generator just gives up and says the geometry is too complex to fillet. Because it's a user-driven program, it has that option.

But a machining simulator does not. Those are programs which simulate what happens as a tool cuts through a part, starting with the geometry of the blank and subtracting every cut. For 2.5D machining (tool always approaches material from straight down), the simulator can use a height field, and that works fine. But the general 3D case, where the tool can come in from any direction, seems to be beyond the state of the art in CSG to get perfectly. I've had both InventorCam and SprutCam blow up.

If you spend $22,000 for a copy of HyperCam, it seems to work much better.

https://www.youtube.com/watch?v=RnIvhlKT7SY

Now that's a triumph of CSG.

In addition to the libraries discussed on the linked page, have a look at Shapely: https://pypi.python.org/pypi/Shapely if you're not already aware of it.

It's GIS-oriented, but in practice, it can be very useful even if you're not strictly dealing with geospatial data.

Computational geometry is a real challenge for python because it requires object oriented design and is speed critical. It is a marvel of technical engineering that this was possible with CGAL, but I don't see this working out unless you have a robust python compiler that is able to remove the various `if` statements that are handled by templates in C++.

If I was to do computational geometry in python, I would wrap CGAL.

Out of curiosity, what specific 'object-oriented' features are needed to robustly implement any given computational geometry algorithm?

The goal is to avoid `if` statements. It is true that a good system will let you deal with many dimensions and data types, but you might be thinking, "I only want this for (x,y,z) floating point data", but there are a few algorithms that require slicing the data into different views and this precisely where things like iterators that are eventually vectorized make the scheme computational tenable.

There are already SWIG generated python bindings for CGAL: https://code.google.com/p/cgal-bindings/

Very interesting. Did the differential geometry module in SymPy not really satisfy your needs? http://docs.sympy.org/0.7.2/modules/geometry.html

Can it also do 3D delaunay tetrahedralizations?

Also, the most difficult aspect (imho) of computational geometry is in decision-making, for instance, to determine if a point lies within an object, and it should give the same outcome even if the problem is viewed from a permutated set of points (which represents essentially the same question).

Does the library offer any solutions in this direction?

This is great! Wonder if using this in a classroom setting would help demonstrate concepts better (since it's easier to play with and adjust)

Maybe, as long as the code doesn't confuse children even more. Perhaps a well though GUI could accomplish this more gracefully.

Exactly. I would encourage the author to put this material together as an IPython Notebook (in conjunction with nbviewer). The IPyNB is a wonderful pedagogic tool.

The OA is very interesting. New educational tools and possibilities are always welcome. However, geogebra is widely used for geometrical investigations on computer at least in the UK.

Reply on news.ycombinator.com