Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

How to compute the convex hull of a set of points in the plane?

How to compute the convex hull of a set of points in the plane and obtain the resulting vertices as a list in the good order?

The following does not work because the vertices are returned in any order. You can confirm this by drawing the polygon of them.

sage: p = Polyhedron(vertices = [(random(),random()) for _ in range(10)])
sage: p.vertices()
(A vertex at (0.02426982921, 0.8569166506),
 A vertex at (0.9906153404, 0.5055452233),
 A vertex at (0.8056807969, 0.9885901971),
 A vertex at (0.02148155632, 0.6201313201),
 A vertex at (0.8789116179, 0.4107095649),
 A vertex at (0.1045180727, 0.2367290111))
sage: polygon(p.vertices())

The function p.plot() does show the polyhedra correctly, so I found the following method to get the list I want :

sage: good = p.plot()._objects[-1]
sage: good
Polygon defined by 6 points
sage: I_want_this_list = zip(good.xdata, good.ydata)
sage: polygon(I_want_this_list)

There should be a cleaner way to get my list no? In general, the polygon might not be stored in the last item of the list p.plot()._objects...

click to hide/show revision 2
retagged

How to compute the convex hull of a set of points in the plane?

How to compute the convex hull of a set of points in the plane and obtain the resulting vertices as a list in the good order?

The following does not work because the vertices are returned in any order. You can confirm this by drawing the polygon of them.

sage: p = Polyhedron(vertices = [(random(),random()) for _ in range(10)])
sage: p.vertices()
(A vertex at (0.02426982921, 0.8569166506),
 A vertex at (0.9906153404, 0.5055452233),
 A vertex at (0.8056807969, 0.9885901971),
 A vertex at (0.02148155632, 0.6201313201),
 A vertex at (0.8789116179, 0.4107095649),
 A vertex at (0.1045180727, 0.2367290111))
sage: polygon(p.vertices())

The function p.plot() does show the polyhedra correctly, so I found the following method to get the list I want :

sage: good = p.plot()._objects[-1]
sage: good
Polygon defined by 6 points
sage: I_want_this_list = zip(good.xdata, good.ydata)
sage: polygon(I_want_this_list)

There should be a cleaner way to get my list no? In general, the polygon might not be stored in the last item of the list p.plot()._objects...

click to hide/show revision 3
retagged

How to compute the convex hull of a set of points in the plane?

How to compute the convex hull of a set of points in the plane and obtain the resulting vertices as a list in the good order?

The following does not work because the vertices are returned in any order. You can confirm this by drawing the polygon of them.

sage: p = Polyhedron(vertices = [(random(),random()) for _ in range(10)])
sage: p.vertices()
(A vertex at (0.02426982921, 0.8569166506),
 A vertex at (0.9906153404, 0.5055452233),
 A vertex at (0.8056807969, 0.9885901971),
 A vertex at (0.02148155632, 0.6201313201),
 A vertex at (0.8789116179, 0.4107095649),
 A vertex at (0.1045180727, 0.2367290111))
sage: polygon(p.vertices())

The function p.plot() does show the polyhedra correctly, so I found the following method to get the list I want :

sage: good = p.plot()._objects[-1]
sage: good
Polygon defined by 6 points
sage: I_want_this_list = zip(good.xdata, good.ydata)
sage: polygon(I_want_this_list)

There should be a cleaner way to get my list no? In general, the polygon might not be stored in the last item of the list p.plot()._objects...

click to hide/show revision 4
retagged

How to compute the convex hull of a set of points in the plane?

How to compute the convex hull of a set of points in the plane and obtain the resulting vertices as a list in the good order?

The following does not work because the vertices are returned in any order. You can confirm this by drawing the polygon of them.

sage: p = Polyhedron(vertices = [(random(),random()) for _ in range(10)])
sage: p.vertices()
(A vertex at (0.02426982921, 0.8569166506),
 A vertex at (0.9906153404, 0.5055452233),
 A vertex at (0.8056807969, 0.9885901971),
 A vertex at (0.02148155632, 0.6201313201),
 A vertex at (0.8789116179, 0.4107095649),
 A vertex at (0.1045180727, 0.2367290111))
sage: polygon(p.vertices())

The function p.plot() does show the polyhedra correctly, so I found the following method to get the list I want :

sage: good = p.plot()._objects[-1]
sage: good
Polygon defined by 6 points
sage: I_want_this_list = zip(good.xdata, good.ydata)
sage: polygon(I_want_this_list)

There should be a cleaner way to get my list no? In general, the polygon might not be stored in the last item of the list p.plot()._objects...