Ask Your Question
1

Getting convex hull of a set of points and plotting the polygon

asked 2016-05-26 05:45:37 +0100

ameetnsharma gravatar image

updated 2019-08-29 16:05:06 +0100

FrédéricC gravatar image

I'm using sagemath cloud.

I'm trying to get the convex hull of a finite set of points, then plotting the polygon. If I just plot the polygon with the vertices directly, I don't get the vertices in the right order to make up a convex polygon (plots edges joining the wrong points). Then I found out about cyclic_sort_vertices_2d which I thought would sort the vertices into the right order, but that's giving me errors. I don't understand the meaning of the errors. Appreciate any help.

here's the relevant code:

hull = Polyhedron(vertices=thePoints);
hull.vertices();
cyclic_sort_vertices_2d(hull.vertices());

And I have this import line at the top of my code for cyclic sort:

from sage.geometry.polyhedron.plot import cyclic_sort_vertices_2d;

Here's my output:

 (A vertex at (9464.0, 10816.0), A vertex at (8736.0, 7735.0), A vertex at (7904.0, 8736.0), A vertex at (11088.0, 5607.0), A vertex at (15552.0, 6480.0), A vertex at (8160.0, 9248.0), A vertex at (8568.0, 9792.0), A vertex at (11076.0, 10140.0), A vertex at (12852.0, 5355.0))

And errors:

Error in lines 28-30
Traceback (most recent call last):
  File "/projects/sage/sage-6.10/local/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 905, in execute
    exec compile(block+'\n', '', 'single') in namespace, locals
  File "", line 1, in <module>
  File "/projects/sage/sage-6.10/local/lib/python2.7/site-packages/sage/geometry/polyhedron/plot.py", line 245, in cyclic_sort_vertices_2d
    adjacency_matrix = Vlist[0].polyhedron().vertex_adjacency_matrix()
  File "sage/misc/cachefunc.pyx", line 2215, in sage.misc.cachefunc.CachedMethodCallerNoArgs.__call__ (/projects/sage/sage-6.10/src/build/cythonized/sage/misc/cachefunc.c:14346)
    self.cache = f(self._instance)
  File "/projects/sage/sage-6.10/local/lib/python2.7/site-packages/sage/geometry/polyhedron/base.py", line 1847, in vertex_adjacency_matrix
    return self._vertex_adjacency_matrix()
  File "/projects/sage/sage-6.10/local/lib/python2.7/site-packages/sage/geometry/polyhedron/base.py", line 312, in _vertex_adjacency_matrix
    face_lattice = self.face_lattice()
  File "sage/misc/cachefunc.pyx", line 2215, in sage.misc.cachefunc.CachedMethodCallerNoArgs.__call__ (/projects/sage/sage-6.10/src/build/cythonized/sage/misc/cachefunc.c:14346)
    self.cache = f(self._instance)
  File "/projects/sage/sage-6.10/local/lib/python2.7/site-packages/sage/geometry/polyhedron/base.py", line 3172, in face_lattice
    face_constructor=face_constructor, required_atoms=atoms_vertices)
  File "/projects/sage/sage-6.10/local/lib/python2.7/site-packages/sage/geometry/hasse_diagram.py", line 182, in Hasse_diagram_from_incidences
    for coatom, atoms in enumerate(coatom_to_atoms)]
KeyError: (frozenset([]), frozenset([0]))
edit retag flag offensive close merge delete

3 Answers

Sort by » oldest newest most voted
1

answered 2016-05-26 10:58:07 +0100

B r u n o gravatar image

You should give us the exact code you are using. Below is an example that does (if I am not mistaken) what you want:

sage: thePoints = [(9464.0, 10816.0),(8736.0, 7735.0), (7904.0, 8736.0), (11088.0, 5607.0),(15552.0, 6480.0),(8160.0, 9248.0),(8568.0, 9792.0),(11076.0, 10140.0),(12852.0, 5355.0)]
sage: hull = Polyhedron(vertices=thePoints)
sage: hull.vertices() # not in cyclic order
(A vertex at (7904, 8736),
 A vertex at (8160, 9248),
 A vertex at (8568, 9792),
 A vertex at (8736, 7735),
 A vertex at (9464, 10816),
 A vertex at (11076, 10140),
 A vertex at (11088, 5607),
 A vertex at (12852, 5355),
 A vertex at (15552, 6480))
sage: from sage.geometry.polyhedron.plot import cyclic_sort_vertices_2d
sage: cyclic_sort_vertices_2d(hull.vertices()) # in cyclic order
[A vertex at (15552, 6480),
 A vertex at (11076, 10140),
 A vertex at (9464, 10816),
 A vertex at (8568, 9792),
 A vertex at (8160, 9248),
 A vertex at (7904, 8736),
 A vertex at (8736, 7735),
 A vertex at (11088, 5607),
 A vertex at (12852, 5355)]
edit flag offensive delete link more
0

answered 2018-07-05 13:44:33 +0100

jipilab gravatar image

Since I see that you have decimal entries, this suggests that you have used "RDF" as a base ring for your polygon.

You may check if it is the case by calling P.base_ring()

There is a known bug in RDF that pops up when plotting:

https://trac.sagemath.org/ticket/24877

Otherwise, if you just want to visualize your polygon your should be able to visualize it with the command ".plot()".

More details will be explained in the extended tutorial which will appear in version 8.3:

https://trac.sagemath.org/ticket/22572

Under "Geometry", "A longer introduction... " (once version 8.3 is out):

http://doc.sagemath.org/html/en/thema...

edit flag offensive delete link more
0

answered 2018-07-03 16:57:27 +0100

pang gravatar image

Also

P1 = Polyhedron(vertices = [[-5,2], [4,4], [3,0], [1,0], [2,-4], [-3,-1], [-5,-3]])
P1.plot()

as in A Brief Introduction to Polytopes in Sage

edit flag offensive delete link more

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: 2016-05-26 05:45:37 +0100

Seen: 1,970 times

Last updated: Jul 05 '18