Revision history [back]

Context: I am interested in Newton polygons of bivariate polynomials. The Newton polygon of $p\in \mathsf K[x,y]$ is the convex hull of the support of $p$. This polygon (obtained through p.newton_polygon()) is in SageMath a Polyhedron. My question is about Polyhedron, and is not (as far as I can tell) specific to Newton polygons.

My question: Is there a way to get the list of vertices of a two-dimensional Polyhedron (that is a polygon in mathematical terms), ordered clockwise or counterclockwise? That is, the list of vertices one gets by following the border of the polygon in one sense or the other. Equivalently, I would be satisfied to get the ordered list of edges (one-dimensional faces).

Given the methods provided with the class Polyhedron, I can get the following informations:

• Unordered list of vertices, in different format: tuple (vertices), list (vertices_list), matrix (vertices_matrix), generator (vertex_generator);
• Unordered list of edges (faces, with argument 1 to get the unidimensional faces = edges);
• Adjacency between vertices¹, in different format: graph (vertex_graph), adjacency matrix (vertex_adjacency_matrix);
• Orderer adjacency between vertices, but the order has to be defined by a linear form (vertex_digraph).

I guess it is not very hard to reconstruct what I need from these informations, but I wonder if there is a very simple way of getting the ordered list of vertices. Note that there is an additional method that could be relevant, though I do not know what the output represents: facet_adjacency_matrix.

¹ The (undirected) adjacency is not fully sufficient: It requires some (easy) computation to produce a directed adjacency from it, and some (somewhat less simple) additional computation to produce the (say) counterclockwise orientation.

Context: I am interested in Newton polygons of bivariate polynomials. The Newton polygon of $p\in \mathsf K[x,y]$ is the convex hull of the support of $p$. This polygon (obtained through p.newton_polygon()) is in SageMath a Polyhedron. My question is about Polyhedron, and is not (as far as I can tell) specific to Newton polygons.

My question: Is there a way to get the list of vertices of a two-dimensional Polyhedron (that is a polygon in mathematical terms), ordered clockwise or counterclockwise? That is, the list of vertices one gets by following the border of the polygon in one sense or the other. Equivalently, I would be satisfied to get the ordered list of edges (one-dimensional faces).

Given the methods provided with the class Polyhedron, I can get the following informations:

• Unordered list of vertices, in different format: tuple (vertices), list (vertices_list), matrix (vertices_matrix), generator (vertex_generator);
• Unordered list of edges (faces, with argument 1 to get the unidimensional faces = edges);
• Adjacency between vertices¹, in different format: graph (vertex_graph), adjacency matrix (vertex_adjacency_matrix);
• Orderer adjacency between vertices, but the order has to be defined by a linear form (vertex_digraph).

I guess it is not very hard to reconstruct what I need from these informations, but I wonder if there is a very simple way of getting the ordered list of vertices. Note that there is an additional method that could be relevant, though I do am not know sure what the output represents: facet_adjacency_matrix.

¹ The (undirected) adjacency is not fully sufficient: It requires some (easy) computation to produce a directed adjacency from it, and some (somewhat less simple) additional computation to produce the (say) counterclockwise orientation.

Context: I am interested in Newton polygons of bivariate polynomials. The Newton polygon of $p\in \mathsf K[x,y]$ is the convex hull of the support of $p$. This polygon (obtained through p.newton_polygon()) is in SageMath a Polyhedron. My question is about Polyhedron, and is not (as far as I can tell) specific to Newton polygons.

My question: Is there a way to get the list of vertices of a two-dimensional Polyhedron (that is a polygon in mathematical terms), ordered clockwise or counterclockwise? That is, the list of vertices one gets by following the border of the polygon in one sense or the other. Equivalently, I would be satisfied to get the ordered list of edges (one-dimensional faces).

Given the methods provided with the class Polyhedron, I can get the following informations:

• Unordered list of vertices, in different format: tuple (vertices), list (vertices_list), matrix (vertices_matrix), generator (vertex_generator);
• Unordered list of edges (faces, with argument 1 to get the unidimensional faces = edges);
• Adjacency between vertices¹, in different format: graph (vertex_graph), adjacency matrix (vertex_adjacency_matrix);
• Orderer adjacency between vertices, but the order has to be defined by a linear form (vertex_digraph).

I guess it is not very hard to reconstruct what I need from these informations, but I wonder if there is a very simple way of getting the ordered list of vertices. Note that there is an additional method that could be relevant, though I am not sure what the output represents: facet_adjacency_matrix.

¹ The (undirected) adjacency is not fully sufficient: It requires some (easy) computation to produce a directed adjacency from it, and some (somewhat less simple) additional computation to produce the (say) counterclockwise orientation.