1
$\begingroup$

I am trying to calculate the center of gravity of a polygon.

My problem is that I need to be able to calculate the center of gravity for both regular and irregular polygons and even self intersecting polygons.

Is that possible?

I've also read that: http://paulbourke.net/geometry/polyarea/ But this is restricted to non self intersecting polygons.

How can I do this? Can you point me to the right direction?

Sub-Question: Will it matter if the nodes are not in order? if for example you have a square shape and you name the top right point (X1Y1) and then the bottom right point (X3Y3)?

In other words if your shape is like 4-1-2-3 (naming the nodes from left to right top to bottom)

Note: Might be a stupid question but I'm not a maths student or anything!

Thanks

  • 0
    Even if you have already accepted yoriki's answer, please tell us: what is a self intersecting polygon, how is it given, are parts of it counted twice or even negatively, and so on.2011-03-11
  • 0
    @Christian Blatter Have a look here: http://paulbourke.net/geometry/polyarea/ there are some examples of self intersecting polygons. I dont have a specific problem (a specific polygon) to solve I just need an algorithm that can be applied to every case!2011-03-11
  • 0
    @Christian Blatter Same comment...I wrote an algorithm that given an arbitrary set of vertices would ideally form a non-self intersecting polygon! Im not sure if its correct though!Have a look if you can: stackoverflow.com/questions/5278801/…. Any comment would be appreciated!2011-03-11

3 Answers 3

1

I think your best bet will be to convert the self-intersecting polygon into a set of non-self-intersecting polygons and apply the algorithm that you linked to to each of them. I don't think it's possible to solve your problem without finding the intersections, and if you have to find the intersections anyway, the additional effort of using them as new vertices in a rearranged vertex list is small compared to the effort of finding them.

To answer your subquestion: Yes, the order of the nodes does matter, especially if the polygon is allowed to be self-intersecting since in that case the order is an essential part of the specification of the polygon and different orders specify different polygons -- for instance, the "square" with the ordering you describe would be the polygon on the right-hand side of the two examples of self-intersecting polygons that the page you linked to gives (rotated by $\pi/2$).

P.S.: I just realized that different orders can also specify different non-self-intersecting (but not convex) polygons, so the only case where you could specify a polygon by its vertices alone is if you know it's convex. But even then you have to use the vertices in the right order in the algorithm you linked to.

  • 0
    To begin with thanks for the reply! I wrote an algorithm that given an arbitrary set of vertices would ideally form a non-self intersecting polygon! Im not sure if its correct though!Have a look if you can: http://stackoverflow.com/questions/5278801/validity-of-algorithm-for-creation-of-a-non-self-intersecting-polygon. Any comment would be appreciated!2011-03-11
0

If you are given just a list of points $z_i=(x_i, y_i)$ $\>(1\leq i\leq n)$ then it is not immediate how these points should determine a certain polygon. Maybe you want the convex hull $C$ of these points. There are algorithms that accept your list as input and produce a second list $(w_i)_{1\leq i\leq m}$ (a subset of the $z_i$) containing the corners of $C$ in counter-clockwise order. Using this second list you can compute the area and centroid of $C$ by means of the formulas given in the quoted source.

These formulas come from an application of Green's theorem to $C$ and its boundary $\partial C$. It reads as follows: $${\rm area}(C)={1\over2}\int_{\partial C}(x\,dy- y\,dx).$$ If you apply this formula to an arbitrary closed curve, as, e.g., the piecewise linear curve $\gamma$ determined by the original $z_i$ you get very strange results: Every part enclosed by $\gamma$ is counted as many times as it is surrounded counterclockwise by $\gamma$.

  • 0
    You lost me mate! Allow me to explain what I'm trying to do! Basically I want to calculate the closest meeting point for a group of people. The idea is that you would have more than 3 people scattered on a map and based on their coordinates you should calculate the closest meeting point. Then I suppose that the way you determine the polygon doesn't really matter or does it? In fact is it the centroid that I should be looking at or is there a different way to achieve that?2011-03-11
  • 0
    @mixkat: Given your description of the problem, finding the centroid of the polygon your group forms seems like overkill. Treat each person like a point mass and find the center of mass of your collection of points as: $$\left(\frac{\sum_{i=0}^n x_i}{n}, \frac{\sum_{i=0}^n y_i}{n}\right).$$2011-03-12
  • 0
    @EricNitardy Yeah turns out that its actually a lot easier..Christian already gave me this answer in the corresponding thread in SO but thanks anyway!!2011-03-12
0

This doesn't work for irregular polygons such as the following: X Y 3 0 3 50 0 50 0 56 3 80 28 80 28 0 3 0