Ask Your Question

How to triangulate polygon with sage?

asked 2012-04-04 18:56:02 -0600

Bill gravatar image

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 flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted

answered 2012-04-05 03:39:33 -0600

Volker Braun gravatar image

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>)]
edit flag offensive delete link 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.)

Bill gravatar imageBill ( 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 (

Volker Braun gravatar imageVolker Braun ( 2012-04-05 05:21:24 -0600 )edit

I will look at that algorithm. Thanks.

Bill gravatar imageBill ( 2012-04-05 07:29:07 -0600 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools


Asked: 2012-04-04 18:56:02 -0600

Seen: 480 times

Last updated: Apr 05 '12