ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 05 Apr 2012 14:29:07 +0200How to triangulate polygon with sage?https://ask.sagemath.org/question/8857/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.
Thu, 05 Apr 2012 01:56:02 +0200https://ask.sagemath.org/question/8857/how-to-triangulate-polygon-with-sage/Answer by Volker Braun for <p>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.).</p>
<p>Does sage have a built-in method to triangulate the resulting polygon? (It appears to me as though this is not the case.)</p>
<p>If not, I would love to see your homemade code to do this.</p>
https://ask.sagemath.org/question/8857/how-to-triangulate-polygon-with-sage/?answer=13425#post-id-13425The `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>)]
Thu, 05 Apr 2012 10:39:33 +0200https://ask.sagemath.org/question/8857/how-to-triangulate-polygon-with-sage/?answer=13425#post-id-13425Comment by Bill for <p>The <code>polygon()</code> function is for plotting, not for polyhedral computations. You can do the following:</p>
<pre><code>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>)
</code></pre>
<p>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:</p>
<pre><code>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>)]
</code></pre>
https://ask.sagemath.org/question/8857/how-to-triangulate-polygon-with-sage/?comment=19984#post-id-19984I will look at that algorithm. Thanks.Thu, 05 Apr 2012 14:29:07 +0200https://ask.sagemath.org/question/8857/how-to-triangulate-polygon-with-sage/?comment=19984#post-id-19984Comment by Bill for <p>The <code>polygon()</code> function is for plotting, not for polyhedral computations. You can do the following:</p>
<pre><code>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>)
</code></pre>
<p>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:</p>
<pre><code>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>)]
</code></pre>
https://ask.sagemath.org/question/8857/how-to-triangulate-polygon-with-sage/?comment=19988#post-id-19988Thanks 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.)Thu, 05 Apr 2012 11:41:30 +0200https://ask.sagemath.org/question/8857/how-to-triangulate-polygon-with-sage/?comment=19988#post-id-19988Comment by Volker Braun for <p>The <code>polygon()</code> function is for plotting, not for polyhedral computations. You can do the following:</p>
<pre><code>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>)
</code></pre>
<p>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:</p>
<pre><code>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>)]
</code></pre>
https://ask.sagemath.org/question/8857/how-to-triangulate-polygon-with-sage/?comment=19987#post-id-19987I 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) Thu, 05 Apr 2012 12:21:24 +0200https://ask.sagemath.org/question/8857/how-to-triangulate-polygon-with-sage/?comment=19987#post-id-19987