Sign in to follow this  
Kwizatz

How to find the center point of a convex hull?

Recommended Posts

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 this post


Link to post
Share on other sites
Quote:
Original post by Kwizatz
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 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 vertices

D3DXVECTOR3 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 this post


Link to post
Share on other sites
Quote:
Original post by erissian
Do 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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
Quote:
Original post by Kwizatz
Quote:
Original post by erissian
Do 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 this post


Link to post
Share on other sites
Quote:
Original post by erissian
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?


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 this post


Link to post
Share on other sites
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 this post


Link to post
Share on other sites
Quote:
Original post by Aardvajk
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.
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 this post


Link to post
Share on other sites
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.area

center = numerator/denominator

Share this post


Link to post
Share on other sites
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';
}


Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this