Ask Your Question

Ordered list of vertices of polygon

asked 2015-10-06 16:46:23 +0200

B r u n o gravatar image

updated 2017-01-05 22:24:16 +0200

FrédéricC gravatar image

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.

edit retag flag offensive close merge delete

1 Answer

Sort by » oldest newest most voted

answered 2015-10-06 18:10:54 +0200

fidbc gravatar image

A search for "convex hull sagemath" pointed me to this question which in turn led me to the sage manual. I hope this answers your question.

edit flag offensive delete link more


Apparently, I did not search with the relevant keywords! Thanks

B r u n o gravatar imageB r u n o ( 2015-10-07 15:38:42 +0200 )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

1 follower


Asked: 2015-10-06 16:46:23 +0200

Seen: 791 times

Last updated: Oct 06 '15