Scipy: Centroid of convex hull

Question

how can I calculate the centroid of a convex hull using python and scipy? All I found are methods for computing Area and Volume.

regards,frank.

Padishah

If you are looking for the actual barycenter of the volume circumscribed by the convex hull, assuming uniform density, do not use the answers below. The just give you the mean of the coordinates of the points describing the hull. – Alika

Answer 1

Assuming you have constructed the convex hull using scipy.spatial.ConvexHull, the returned object should then have the positions of the points, so the centroid may be as simple as,

import numpy as np
from scipy.spatial import ConvexHull

points = np.random.rand(30, 2)   # 30 random points in 2-D
hull = ConvexHull(points)

#Get centoid
cx = np.mean(hull.points[hull.vertices,0])
cy = np.mean(hull.points[hull.vertices,1])

Which you can plot as follows,

import matplotlib.pyplot as plt
#Plot convex hull
for simplex in hull.simplices:
    plt.plot(points[simplex, 0], points[simplex, 1], 'k-')

#Plot centroid
plt.plot(cx, cy,'x',ms=20)
plt.show()

The scipy convex hull is based on Qhull which should have method centrum, from the Qhull docs,

A centrum is a point on a facet's hyperplane. A centrum is the average of a facet's vertices. Neighboring facets are convex if each centrum is below the neighbor facet's hyperplane.

where the centrum is the same as a centroid for simple facets,

For simplicial facets with d vertices, the centrum is equivalent to the centroid or center of gravity.

As scipy doesn't seem to provide this, you could define your own in a child class to hull,

class CHull(ConvexHull):

    def __init__(self, points):
        ConvexHull.__init__(self, points)

    def centrum(self):

        c = []
        for i in range(self.points.shape[1]):
            c.append(np.mean(self.points[self.vertices,i]))

        return c

 hull = CHull(points)
 c = hull.centrum()

Partook

Thx for helping. I will check if the calculated centroid is always inside the hull.... BTW: do you know how to plot the hull in 3D? I'm using Axes3D and scatter. Simply scatter the simplices? – Padishah

I've just added a method with append so should work in N dimensions. I guess you can plot the vertices as a scatter using matplotlib as in matplotlib.org/mpl_toolkits/mplot3d/tutorial.html#scatter-plots or a line plot using the simplices as above but in 3D... – Partook

Answer 2

The simple 'mean' method is not correct if the hull has points that are irregularly spaced around the perimeter, or at least will give a skewed answer. The best approach that I use is to calculate the centroids of the delaunay triangles of the hull points. This will weight the calculation to calculate the centroid as the COM of the shape, not just the average of vertices:

from scipy.spatial import ConvexHull, Delaunay

def _centroid_poly(poly):
    
    T = Delaunay(poly).simplices
    n = T.shape[0]
    W = np.zeros(n)
    C = 0
    
    for m in range(n):
        sp = poly[T[m, :], :]
        W[m] = ConvexHull(sp).volume
        C += W[m] * np.mean(sp, axis=0)
    
    return C / np.sum(W)

poly = np.random.rand(30, 2)
# will calculate the centroid of the convex hull of poly
centroid_hull = _centroid_poly(poly)

Something like this should work.

Disfrock

Answer 3

To find the geometric centre of the hull's vertices simply use,

# Calculate geometric centroid of convex hull 
hull = ConvexHull(points)   
centroid = np.mean(points[hull.vertices, :], axis=0)

To plot the hull try,

import numpy as np
import pylab as pl
import scipy as sp
import matplotlib.pyplot as plt
import mpl_toolkits.mplot3d as a3

#  Plot polyhedra    
ax = a3.Axes3D(pl.figure())
facetCol = sp.rand(3)
for simplex in hull.simplices:
    vtx = [points[simplex[0],:], points[simplex[1],:], points[simplex[2],:]]
    tri = a3.art3d.Poly3DCollection([vtx], linewidths = 2, alpha = 0.8)
    tri.set_color(facetCol)
    tri.set_edgecolor('k')
    ax.add_collection3d(tri)

# Plot centroid      
ax.scatter(centroid0], centroid[1], centroid[2]) 
plt.axis('equal')
plt.axis('off')
plt.show()

Ufa

Answer 4

This solution is correct also if the hull has points that are irregularly spaced around the perimeter.

import numpy as np
from scipy.spatial import ConvexHull

def areaPoly(points):
    area = 0
    nPoints = len(points)
    j = nPoints - 1
    i = 0
    for point in points:
        p1 = points[i]
        p2 = points[j]
        area += (p1[0]*p2[1])
        area -= (p1[1]*p2[0])
        j = i
        i += 1

    area /= 2
    return area

def centroidPoly(points):
    nPoints = len(points)
    x = 0
    y = 0
    j = nPoints - 1
    i = 0

    for point in points:
        p1 = points[i]
        p2 = points[j]
        f = p1[0]*p2[1] - p2[0]*p1[1]
        x += (p1[0] + p2[0])*f
        y += (p1[1] + p2[1])*f
        j = i
        i += 1

    area = areaPoly(hull_points)
    f = area*6
    return [x/f, y/f]

# 'points' is an array of tuples (x, y)
points = np.array(points)
hull = ConvexHull(points)
hull_points = points[hull.vertices]
centroid = centroidPoly(hull_points)

Rutger

Thank you for taking the time to provide an answer to the question. Since questions often receive multiple answers, you are encouraged to provide some context to your answer -- such as explaining why your solution may be better than other solutions. – Nonmoral