How to triangulate polygon with sage?

If I feed sage a list of vertices, then the polygon() function can create a 2D polygon determined by visiting these edges in order (with self-intersections, repeated edges, holes, etc.).

Does sage have a built-in method to triangulate the resulting polygon? (It appears to me as though this is not the case.)

If not, I would love to see your homemade code to do this.

edit retag close merge delete

Sort by ยป oldest newest most voted

The polygon() function is for plotting, not for polyhedral computations. You can do the following:

sage: square = Polyhedron([(0,0), (1,0), (0,1), (1,1)])
sage: square
A 2-dimensional polyhedron in ZZ^2 defined as the convex hull of 4 vertices
sage: square.triangulate()
(<0,1,3>, <0,2,3>)


If you are more serious about triangulations, this should get you started. As usual, the online help is your friend if you want to know more:

sage: pc = PointConfiguration([(0,0), (1,0), (0,1), (1,1)])
sage: pc
A point configuration in QQ^2 consisting of 4 points. The triangulations of this point configuration are assumed to be connected, not necessarily fine, not necessarily regular.
sage: pc.triangulations_list()
[(<0,1,2>, <1,2,3>), (<0,1,3>, <0,2,3>)]

more

Thanks for the suggestion. Unfortunately, I am working in a setting where taking the convex hull of the vertices of my polygon is not what I want to do. (My polygons have holes in them.)

( 2012-04-05 04:41:30 -0600 )edit

I don't think Sage has anything for non-convex polygons. One should implement Chazelle's algorithm, I suppose (http://wiki.xomb.org/images/0/09/Chazelle_PolygonCutting.pdf)

( 2012-04-05 05:21:24 -0600 )edit

I will look at that algorithm. Thanks.

( 2012-04-05 07:29:07 -0600 )edit