Ask Your Question
2

Ordered list of vertices of polygon

asked 2015-10-06 09:46:23 -0600

B r u n o gravatar image

updated 2017-01-05 15:24:16 -0600

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
3

answered 2015-10-06 11:10:54 -0600

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

Comments

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

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

1 follower

Stats

Asked: 2015-10-06 09:46:23 -0600

Seen: 289 times

Last updated: Oct 06 '15