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

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
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
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 close merge delete

Sort by » oldest newest most voted

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)]

more

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...

more

Also

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

more