Getting the boundary of a rectangle using the convex hull (in python)
I am trying to get the boundary of a rectangle using scipy.ConvexHull(), and it's failing to do so.
u=np.linspace(0, 4, 8)
v=np.linspace(5, 10, 8)
u,v=np.meshgrid(u,v)
u=u.flatten()
v=v.flatten()
points2D=np.vstack([u,v]).T
hull = ConvexHull(points2D)
convex_hull_plot_2d(hull)
boundaryList = hull.vertices
print boundaryList
gives only the four corners:[ 0 7 63 56]
Perturbing the points a bit using the option qhull_options="QJ Pp" as follows:
hull = ConvexHull(points2D, qhull_options="QJ Pp")
gives more points: [62 56 40 8 0 2 6 7 15 23 47 55 63], but still not the full boundary set.
Can someone tell me a proper fix for this?
The mathematical definition of convex hull states
In mathematics, the convex hull or convex envelope of a set X of points in the Euclidean plane or in a Euclidean space (or, more generally, in an affine space over the reals) is the smallest convex set that contains X.
Smallest convex set that contains a rectangle are indeed the four corners that you get.
To get all the points on the boundary you can use the Delaunay triangulation and then compute the convex hull from the resulting Delaunay grid,
import numpy as np
import matplotlib.pyplot as plt
from scipy.spatial import Delaunay
u=np.linspace(0, 4, 8)
v=np.linspace(5, 10, 8)
u,v=np.meshgrid(u,v)
u=u.flatten()
v=v.flatten()
points2D=np.vstack([u,v]).T
tri = Delaunay(points2D)
plt.triplot(points2D[:,0], points2D[:,1], tri.simplices.copy())
boundary = (points2D[tri.convex_hull]).flatten()
bx = boundary[0:-2:2]
by = boundary[1:-1:2]
plt.plot(points2D[:,0], points2D[:,1], 'o')
plt.plot(bx, by, 'rs')
plt.xlim(-1,5)
plt.ylim(4,11)
plt.show()
To create the hull after forming the triangulation the program uses tri.convex_hull. This returns the vertices of facets forming the convex hull for the triangulation points. In your, 2D case, these are lines and the output comes out as a set of neighboring points comprising each line. Note that this approach is considered inefficient as it needs to form the triangulation in addition to convex hull.
The remaining of the program extracts the x and corresponding y values for each point and plots them together with the triangulation resulting in
