How to draw a polygon (parts was bent inward) edge on a group of points with Python?

Question

I am trying to draw a polygon (concave) edge on a K-Means cluster shown below (fig_1).

With @ypnos's help, This piece of code plot everything except the edge.

df = pd.read_csv('https://raw.githubusercontent.com/MachineIntellect/dataset.ml/master/watermelon/watermelon_4_0.csv')
X = df.iloc[:,1:].to_numpy()
m0 = X[5]
m1 = X[11]
m2 = X[23]
centroids = np.array([m0, m1, m2])
labels = pairwise_distances_argmin(X, centroids)
m0 = X[labels == 0].mean(0)
m1 = X[labels == 1].mean(0)
m2 = X[labels == 2].mean(0)
new_centroids = np.array([m0, m1, m2])
plt.xlim(0.1,0.9)
plt.ylim(0, 0.8)
plt.scatter(X[:,0], X[:,1])
plt.scatter(new_centroids[:,0], new_centroids[:,1], c='r', marker = '+')
for i in range(3):    
    points = X[labels == i]
    hull = ConvexHull(points)
    for simplex in hull.simplices:
        plt.plot(points[simplex, 0], points[simplex, 1], 'r-')

(fig_2)

The scikit-learn doc seems to be inspiring

The question is that the edges pointed by the arrow in fig_1 are different from the correspondence in fig_2.

the edge of the polygon that was being pointed to by the arrow was bent inward (thanks to @dwilli).

Thanks to @ImportanceOfBeingErnest's reminder, scipy.spatial.ConvexHull may not be able to produce concave.

Is there any other module/package to do this (concave)?

any hint would be appreciated.

Answer 1

What your inspiration shows is a Voronoi diagram. The coloring shows for any coordinate in the graph, which cluster it would be associated to.

The polygons you show in your first figure are a rough approximation of the convex hull of your cluster members. You could use scipy.spatial.ConvexHull or cv2.convexHull() (from OpenCV) to compute it. The documentation of the former also gives an example on how to plot it.