Centroid of a polygon
Gemoetry problem:
Wikipedia (and my math teacher) says that we can find the centroid of an arbitrary polygon by taking the avarage of their coordinates.
http://en.wikipedia.org/wiki/Centroid
What if there is a lot of points close to one side of the polygon, and only one on the other?
The averaging method clearly doesn't work here.
Am I misunderstanding Wikipedia?
Wikipedia (and my math teacher) says that we can find the centroid of an arbitrary polygon by taking the avarage of their coordinates.
x1 + x2 + ... + xk
C = -------------------
k
|
http://en.wikipedia.org/wiki/Centroid
What if there is a lot of points close to one side of the polygon, and only one on the other?
/\
/ \
/ \
/ \
/ \
\/\/\/\/\/
|
The averaging method clearly doesn't work here.
Am I misunderstanding Wikipedia?
Are we assuming that this a regular type of polygon? Like, as in we are not using decagons than look like pacman but more like a circle?
Last edited on
The centroid is the center of mass; it should still be accurate even in such a case. The only way to prove that it doesn't work would be if the centroid ended up outside the polygon in question. Keep in mind that there is a significantly increased amount of mass concentrated in those zigzagging points which compensates for the significant skew they place on the average.
| kevinkjt2000 wrote: |
|---|
| Are we assuming that this a regular type of polygon? |
Regular polygons, no curves for simplicity.
| tummychow wrote: |
|---|
| Keep in mind that there is a significantly increased amount of mass concentrated in those zigzagging points which compensates for the significant skew they place on the average. |
I don't agree. Compare these two polygons.
/\
/ \
/ \
/ \
/ \
\/\/\/\/\/ |
/\
/ \
/ \
/ \
/ \
---------- |
Their area(mass) is exactly the same with the same distribution, but the centroid is not on the same place (or even close).
Your math teacher left off an important piece of information about the centroid.
http://en.wikipedia.org/wiki/Centroid
By simply averaging the points, you miss the moment -- particularly as the geometric object in your example is not regularly interspersed by points.
There are a lot of different ways to handle this problem, and there is ongoing research by people to overcome it. You can try googling around a bit for more.
Good luck!
[edit] One way to overcome is to compute a new collection of regular points by overlaying the polygon on an grid and recalculate from that. (That's not the whole answer, but it is a start.)
http://en.wikipedia.org/wiki/Centroid
By simply averaging the points, you miss the moment -- particularly as the geometric object in your example is not regularly interspersed by points.
There are a lot of different ways to handle this problem, and there is ongoing research by people to overcome it. You can try googling around a bit for more.
Good luck!
[edit] One way to overcome is to compute a new collection of regular points by overlaying the polygon on an grid and recalculate from that. (That's not the whole answer, but it is a start.)
Last edited on
You are misunderstanding Wikipedia. And I believe it is because you are confusing the term "points" with "vertices".
There are a couple of ways to do this that are easy to compute algorithmically.
The first would be to tessellate the polygon into triangles, find the centroid of each triangle then use the formula presented here: http://en.wikipedia.org/wiki/Centroid#Centroid_by_geometric_decomposition.
This is a good method to use when you need to find the centroid of a non-planar surface. Most 3D animation is done using tessellated surfaces.
The other is a "shotgun average" approach. Project a bounding box (or circle) around your polygon and project a random number of points on that surface. Average the points that fall within the polygon to find the center: http://en.wikipedia.org/wiki/Centroid#Centroid_of_a_finite_set_of_points
There are a couple of ways to do this that are easy to compute algorithmically.
The first would be to tessellate the polygon into triangles, find the centroid of each triangle then use the formula presented here: http://en.wikipedia.org/wiki/Centroid#Centroid_by_geometric_decomposition.
This is a good method to use when you need to find the centroid of a non-planar surface. Most 3D animation is done using tessellated surfaces.
The other is a "shotgun average" approach. Project a bounding box (or circle) around your polygon and project a random number of points on that surface. Average the points that fall within the polygon to find the center: http://en.wikipedia.org/wiki/Centroid#Centroid_of_a_finite_set_of_points
Thank you PanGalactic, now I understand. We really should learn the English names of the mathematical terms in school :/ .
Wikipedia is not wrong actually...
Centroid is indeed center of mass. Let me clarify: the formula you gave gives the centroid **of the points**, not of the figure they enclose.
In your example, imagine it this way: the points each represent 1kg heavy lead balls, and the sides of the triangle are connected by a very light thread. Then, indeed, the center of mass would shift towards the lower side of your triangle.
If you want to compute the center of mass **of the figure enclosed by your points**, I can give you a very quick formula (no triangulation involved, that is an expensive operation). However, here is the catch: what is the figure enclosed by your points? If you just give the points, there are multiple ways to "connect the dots" to form it. Therefore, when you represent your polygon, you must give **the order of points**, or, which couples of points form "sides".
Centroid is indeed center of mass. Let me clarify: the formula you gave gives the centroid **of the points**, not of the figure they enclose.
In your example, imagine it this way: the points each represent 1kg heavy lead balls, and the sides of the triangle are connected by a very light thread. Then, indeed, the center of mass would shift towards the lower side of your triangle.
If you want to compute the center of mass **of the figure enclosed by your points**, I can give you a very quick formula (no triangulation involved, that is an expensive operation). However, here is the catch: what is the figure enclosed by your points? If you just give the points, there are multiple ways to "connect the dots" to form it. Therefore, when you represent your polygon, you must give **the order of points**, or, which couples of points form "sides".
Last edited on
| I can give you a very quick formula |
That would be great!
| there are multiple ways to "connect the dots" to form it. |
I guess the simplest way is to assume, that we have points p1, p2... pn, and they are connected one after the other.
Suppose you are given the points (x_1,y_1)->...-> (x_n,y_n)-> (x_1,y_1), where by -> i denote that a point is linked to the next. Let the enclosed figure be non-self-intersecting.
Observe the segment (x_k, y_k) ->(x_{k+1}, y_{k+1}). For simplicity assume we are looking at (x_1, y_1) ->(x_2, y_2). Now draw a perpendicular from each of these points to the x-axis. The two projections, (x_1, 0) and (x_2,0), together with the two starting points form a trapezoid of area (x_2-x_1)*(y_1+y_2)/2. Note that I do not put absolute values anywhere! This is *very important*: some trapezoids will have negative areas. That means that we add some trapezoids, and subtract others, depending on their orientation.
Now simply sum up the areas of the so obtained trapezoids: \sum_k (x_{k}-x_{k-1})*(y_{k}+y_{k-1})/2. A simple geometric argument **which uses the non-self-intersection of the enclosed polygon**, which I leave to yourself, will convince you that the total sum of the trapezoid's areas, taking into account the cancellations of the negative areas, will be exactly the area of the enclosed figure.
An important note: it is key that the polygon (x_1,y_1)->...-> (x_n,y_n)-> (x_1,y_1) is closed (the end point equals the start point. Note that I didn't care where the coordinate system was located. This means, that if you translated the coordinate system, the expression I gave you should remain the same (since volume doesnt change under translation). Translating the x coordinate doesnt change the value of any of the summands. Translating the y coordinates with a value L changes each summand by (x_k-x_{k-1})*L, but it changes the total expression by 0=((x_2-x_1)+...+(x_n-x_{n-1})+(x_1-x_n))*L.
Observe the segment (x_k, y_k) ->(x_{k+1}, y_{k+1}). For simplicity assume we are looking at (x_1, y_1) ->(x_2, y_2). Now draw a perpendicular from each of these points to the x-axis. The two projections, (x_1, 0) and (x_2,0), together with the two starting points form a trapezoid of area (x_2-x_1)*(y_1+y_2)/2. Note that I do not put absolute values anywhere! This is *very important*: some trapezoids will have negative areas. That means that we add some trapezoids, and subtract others, depending on their orientation.
Now simply sum up the areas of the so obtained trapezoids: \sum_k (x_{k}-x_{k-1})*(y_{k}+y_{k-1})/2. A simple geometric argument **which uses the non-self-intersection of the enclosed polygon**, which I leave to yourself, will convince you that the total sum of the trapezoid's areas, taking into account the cancellations of the negative areas, will be exactly the area of the enclosed figure.
An important note: it is key that the polygon (x_1,y_1)->...-> (x_n,y_n)-> (x_1,y_1) is closed (the end point equals the start point. Note that I didn't care where the coordinate system was located. This means, that if you translated the coordinate system, the expression I gave you should remain the same (since volume doesnt change under translation). Translating the x coordinate doesnt change the value of any of the summands. Translating the y coordinates with a value L changes each summand by (x_k-x_{k-1})*L, but it changes the total expression by 0=((x_2-x_1)+...+(x_n-x_{n-1})+(x_1-x_n))*L.
Last edited on
Thanks tition.
What happens after we sum up the areas of the obtained trapezoids (and get the area of the original polygon)?
What happens after we sum up the areas of the obtained trapezoids (and get the area of the original polygon)?
Oh crap... I was writing in a brain-damaged mode, sorry for that! My previous post was not on topic (well, actually it is a little bit relevant).
Again sorry for wasting your time! Anyways, here's how I would find the centroid of a figure [Edit:] *without triangulation, provided the points of the figure are given in clockwise order*. First of all, let me point out that the formula for doing this is actually in the wikipedia article under paragraph "Centroid by geometric decomposition".
http://en.wikipedia.org/wiki/Centroid#Centroid_of_a_finite_set_of_points
The punchline is that you don't need any *real* triangulation: simply take the formula as it is given, but allow *signed* areas. Let me explain:
The formula I am pointing you to is
For the triangulation, simply pick the "fake" triangulation
T_1=(x_1, y_1) (x_2, y_2) (x_3,y_3)
T_2=(x_1, y_1) (x_3,y_3) (x_4,y_4)
...
T_{n-2}= (x_1, y_1) (x_{n-1},y_{n-1}) (x_n,y_n)
Now if A_{k-2} is the area of triangle T_{k-2}= x_1 x_{k-1} x_k, then A_{k-2} is given by the formula
Note that the above formula gives at times negative area, and at times - positive. That will precisely account for the fact that some of the triangles in our triangulation have pieces lying outside of our figure.
The centroid C_k of each T_{k-2} is of course given by:
.
I hope you now see how to apply the above formula. The simplicity of this approach is now evident: it works in arbitrary dimension. All you need to do in arbitrary dimension (for example, in 3D or 1D), is to
note that the area in dimension D of a simplex(=triangle in 2D, tetrahedron in 3D - simplex is the general word for arbitrary dimension) will be given by:
Let the simplex be given with points P_0= (x0_1, x0_2, ..., x0_D) ... P_{D}= (xD_1, xD_2, ..., xD_D) (a simplex in N dimensions has always N+1 vertices - triangle has 3 and tetrahedron has 4). Then the area of the enclosed simplex is given by the D by D determinant
Of course, you must also normalize the centroids properly: they will be the average of D+1 points, so you must always divide by 1/(D+1).
Do you know how to compute determinants?
Cheers
Again sorry for wasting your time! Anyways, here's how I would find the centroid of a figure [Edit:] *without triangulation, provided the points of the figure are given in clockwise order*. First of all, let me point out that the formula for doing this is actually in the wikipedia article under paragraph "Centroid by geometric decomposition".
http://en.wikipedia.org/wiki/Centroid#Centroid_of_a_finite_set_of_points
The punchline is that you don't need any *real* triangulation: simply take the formula as it is given, but allow *signed* areas. Let me explain:
The formula I am pointing you to is
(\sum_k C_i A_i)/(\sum A_i)For the triangulation, simply pick the "fake" triangulation
T_1=(x_1, y_1) (x_2, y_2) (x_3,y_3)
T_2=(x_1, y_1) (x_3,y_3) (x_4,y_4)
...
T_{n-2}= (x_1, y_1) (x_{n-1},y_{n-1}) (x_n,y_n)
Now if A_{k-2} is the area of triangle T_{k-2}= x_1 x_{k-1} x_k, then A_{k-2} is given by the formula
|
|
Note that the above formula gives at times negative area, and at times - positive. That will precisely account for the fact that some of the triangles in our triangulation have pieces lying outside of our figure.
The centroid C_k of each T_{k-2} is of course given by:
|
|
I hope you now see how to apply the above formula. The simplicity of this approach is now evident: it works in arbitrary dimension. All you need to do in arbitrary dimension (for example, in 3D or 1D), is to
note that the area in dimension D of a simplex(=triangle in 2D, tetrahedron in 3D - simplex is the general word for arbitrary dimension) will be given by:
Let the simplex be given with points P_0= (x0_1, x0_2, ..., x0_D) ... P_{D}= (xD_1, xD_2, ..., xD_D) (a simplex in N dimensions has always N+1 vertices - triangle has 3 and tetrahedron has 4). Then the area of the enclosed simplex is given by the D by D determinant
|
|
Of course, you must also normalize the centroids properly: they will be the average of D+1 points, so you must always divide by 1/(D+1).
Do you know how to compute determinants?
Cheers
Last edited on
Thank you tition, that's really nice.
I'm still gathering dust in a secondary school, so not yet, but I understand the method for two dimensions.
I'm gonna write a nice simulation to see if it works :).
| Do you know how to compute determinants? |
I'm still gathering dust in a secondary school, so not yet, but I understand the method for two dimensions.
I'm gonna write a nice simulation to see if it works :).
Topic archived. No new replies allowed.