Toblerity/Shapely — pull request #134 by jwass (2014-05-28 05:30:14+00:00)
Title: Enable Delaunay Triangulation

This enables Delaunay Triangulation, introduced in GEOS 3.4. A new function `shapely.ops.triangulate` takes as input a geometry and returns a list of geometries.

Couple of notes:
- I named the API call `triangulate` since `delaunay_triangulation` is pretty long and would probably be misspelled 99% of the time. If/when there are other types of triangulation, we could switch on a `kind='delaunay'` keyword arg.
- The function is in `shapely.ops`. Since it works with any geometry, there's no reason it couldn't be a method of base geometry but felt like `ops` is the better place for this.
- The GEOS function returns a Geometry Collection, but the Python function pulls out the geoms and returns a list of Polygons or LineStrings.

I'm not passionate about any of the above, let me know if anything should change.
Also:
- ubuntusgis PPA installs GEOS 3.3.8, which doesn't have Delaunay triangulation. So the Travis build skips the tests associated with the new behavior here.
- I couldn't quickly find the exact C API version but since it was added in 3.4.0, I think 1.8.0 is the right version (http://trac.osgeo.org/geos/browser/tags/3.4.2/NEWS)

Here's an example script that uniformly samples the area of __convex__ polygons. It computes the Delaunay triangulation, then samples points in the returned triangles weighted by area.
https://gist.github.com/jwass/ea225c99676adb2a2be9
Resulting plot:
![figure_1](https://cloud.githubusercontent.com/assets/1214350/3100826/ab99b0ce-e624-11e3-882a-f2cdaa826218.png)