# How to find the center point of a convex hull?

## Recommended Posts

Kwizatz    1392
Hello everyone. I need to find the center of a convex hull which is given by either a set of planes or a collection of polygons. I was calculating it by just taking the center of its AABB as the center of the hull but it turns out that sometimes the center of the AABB is outside the convex hull or could be directly on one of the faces (think of a wedge), so I need a better method. I am thinking about something like using the plane equations to find a point where the distance to all the planes is... well something, I guess I could use support points in order to find a point that is right between one face and the support point on the opposite direction and then average all of them. I don't really need a fast algorithm, this is to go in my level compiler so it is preprocessing, but it would be great if there was a fast algorithm already out there. Anyway, is there already an algorithm or a 'simple' way to do this out there? Thanks in Advance [smile].

##### Share on other sites
erissian    727
Do you need the center of area, on the hull, or the center of volume, wherever that may be?

##### Share on other sites
Aardvajk    13207
Quote:
 Original post by KwizatzI am thinking about something like using the plane equations to find a point where the distance to all the planes is... well something, I guess I could use support points in order to find a point that is right between one face and the support point on the opposite direction and then average all of them.

I can't speak for 3D but for 2D hulls defined by a list of vertices, I've always found the centre by finding the average vertex where each component is just the mean average of the sum of all of the components of the vertices.

I don't think there is an any more defined concept of a centre for an arbitrarily shaped convex shape or hull.

// Pts is a vector of world-space verticesD3DXVECTOR3 FindCentreOf2DShape(const std::vector<D3DXVECTOR3> &Pts){    D3DXVECTOR3 Av(0,0,0);	    for(std::vector<D3DXVECTOR3>::const_iterator I=Pts.begin();I!=Pts.end();++I) Av+=*I;    D3DXVECTOR3 Pos;    Pos.x=Av.x/float(Pts.size());	    Pos.y=Av.y/float(Pts.size());    return Pos;}

I assume the same would work for 3D.

##### Share on other sites
Kwizatz    1392
Quote:
 Original post by erissianDo you need the center of area, on the hull, or the center of volume, wherever that may be?

Center of volume, although it could be an approximation right now as what I need is a point inside the hull, I intend on using it as the center of mass for physics calculations later, so the closest to the center the better.

##### Share on other sites
Kwizatz    1392
Quote:
 Original post by Aardvajk...I assume the same would work for 3D.

Yes, should be a matter of adding the extra dimension, I'll test it out and post the results. Just one thing though, this doesn't assume that the origin is contained in the hull right? or on the other hand that it isn't? because it may or may not be so.

Thanks!

##### Share on other sites
Kwizatz    1392
Ok, that seems to work, or at least I am not getting the same assert exception, which probably means it is all good, thanks again! I'll post if I find any further issues [smile].

##### Share on other sites
erissian    727
Quote:
Original post by Kwizatz
Quote:
 Original post by erissianDo you need the center of area, on the hull, or the center of volume, wherever that may be?

Center of volume, although it could be an approximation right now as what I need is a point inside the hull, I intend on using it as the center of mass for physics calculations later, so the closest to the center the better.

Taking into account that you want to use a center of mass, and assuming the hull is a homogeneous material, why not use the center of mass equation with the polygon barycenters as the position vectors, and the polygon areas as masses?

##### Share on other sites
Kwizatz    1392
Quote:
 Original post by erissianTaking into account that you want to use a center of mass, and assuming the hull is a homogeneous material, why not use the center of mass equation with the polygon barycenters as the position vectors, and the polygon areas as masses?

Huh? I am afraid that went over my head, could you elaborate a bit more?

I get the equation:

R = ∑ mi ri/∑ mi

Where m is the masses and r the positions you mention, but how do I calculate the barycenters? would that be the average calculation Aardvajk gave? is it the same as their centroids?

##### Share on other sites
ibebrett    205
hes saying you can average the center of mass for each face to determine the center of mass for the convex hull. your center of mass is guarunteed to be inside the hull if it is convex.

##### Share on other sites
Sneftel    1788
Quote:
 Original post by AardvajkI can't speak for 3D but for 2D hulls defined by a list of vertices, I've always found the centre by finding the average vertex where each component is just the mean average of the sum of all of the components of the vertices.
This is not true for the center of mass. Consider arbitrarily splitting a vertex into two vertices with a 0-length edge between them. That vector becomes doubly weighted in the center calculation, despite the shape not changing.

To calculate the centroid (center of mass) of a convex hull, calculate the centroid of each of its triangles, then find their average, weighted by the area of each triangle.

##### Share on other sites
erissian    727
Yes. It would be the average position of the individual polygon. Instead of mass, you would use area, so the idea would essentially be:

for each polygon    for each vertex in polygon        average_position += vertex.position    average_position /= num_vertexes    numerator += average_position * polygon.area    denominator += polygon.areacenter = numerator/denominator

##### Share on other sites
Kwizatz    1392
Alright, got it now, thanks everyone [smile], now I just have to implement it.

##### Share on other sites
alvaro    21246
If you do all the area operations with sign, you can simply loop through the edges and pretend that they form a triangle with the origin. It simplifies the code a bit:
#include <iostream>#include <vector>struct Point {  double x, y;  Point(double x, double y) : x(x), y(y) {  }  Point &unorthodox_sum(Point const &p) {    x += p.x;    y += p.y;    return *this;  }  Point &unorthodox_scaling(double scale) {    x *= scale;    y *= scale;    return *this;  }};class Polygon {  std::vector<Point> vertices;public:  template <typename It>  Polygon(It begin, It end) : vertices(begin, end) {  }  Point &operator[](unsigned n) {    return vertices[n%vertices.size()];  }  Point const &operator[](unsigned n) const {    return vertices[n%vertices.size()];  }  unsigned size() const {    return vertices.size();  }};Point barycenter(Polygon const &P) {  Point result(0.0,0.0);  double total_area=0.0;  for(unsigned i=0; i<P.size(); ++i) {    double triangle_area = 0.5*(P[i].x*P[i+1].y-P[i].y*P[i+1].x);    total_area += triangle_area;    Point triangle_barycenter((P[i].x+P[i+1].x)*(1.0/3.0), (P[i].y+P[i+1].y)*(1.0/3.0));    triangle_barycenter.unorthodox_scaling(triangle_area);    result.unorthodox_sum(triangle_barycenter);  }  result.unorthodox_scaling(1.0/total_area);  return result;}int main() {  Point points[4]={Point(1.0,0.0),Point(3.0,2.0),Point(1.0,2.0),Point(0.0,1.0)};  Polygon polygon(points, points+4);  Point b = barycenter(polygon);  std::cout << '(' << b.x << ',' << b.y << ')' << '\n';}