How to find the center point of a convex hull?
Author
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].
Do you need the center of area, on the hull, or the center of volume, wherever that may be?
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 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.
Author
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.
Author
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!
Author
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].
Quote:Original post by KwizatzQuote: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?
Author
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?
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.
Quote:Original post by AardvajkThis 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.
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
