Sign in to follow this  
godsenddeath

Finding the center point for a convex polygon

Recommended Posts

I'm trying to re-write an obj loader i wrote a while back, and one thing I was wanting to do is handle faces of an arbitrary size (well, n >= 3) since the .obj file format doesn't limit the number of vertices in a face, Then triangulate the face by using the center point along with connected vertices to form triangles. I'm not a huge math guy, so the best thing I can think of is to use (avgx, avgy, avgz), as the center point, but I'm fairly sure that will crash and burn.

does anyone know of a simple (or complex if need be) algorithm to determine the centerpoint of a convex polygon given its vertices.


Thanks.

Share this post


Link to post
Share on other sites
Yup, just convert it to a triangle fan, like Luca said. I believe this is how most 3D applications export to .obj.[color="#000000"][u][url="../../user/102074-luca-deltodesco/"][/url][/u][/color]

Share this post


Link to post
Share on other sites
Another popular method, which id's engines use, is the following: Given vertices 0,1,...,n-1, you have a triangle strip with vertices,

0, 1, n-1, 2, n-2, 3, n-3, 4, n-4, ...

[Next, on the subject of "center points" of polygons (even though this isn't really what you need): There are various notions of "center points." Any convex combination (weighted sum with weights between 0 and 1, and adding up to 1; sum in the vector addition sense) of vertices is going be "inside" the polygon, so you could e.g. choose all the weights to be 1/n. Other points that have a certain appeal include the actual center of mass (which you typically compute by triangulating the polygon), and the Chebyshev center (the point farthest away from the closest edge; it's the solution to a certain linear program).]

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