public static Vector2 CalculateCentroid(Vector2[] points,
int lastPointIndex)
{
float area = 0.0f;
float Cx = 0.0f;
float Cy = 0.0f;
float tmp = 0.0f;
int k;
for (int i = 0; i <= lastPointIndex; i++)
{
k = (i + 1) % (lastPointIndex + 1);
tmp = points[i].X * points[k].Y -
points[k].X * points[i].Y;
area += tmp;
Cx += (points[i].X + points[k].X) * tmp;
Cy += (points[i].Y + points[k].Y) * tmp;
}
area *= 0.5f;
Cx *= 1.0f / (6.0f * area);
Cy *= 1.0f / (6.0f * area);
return new Vector2(Cx, Cy);
}
NOTE: this algorithm doesn`t apply for complex polygons. But How simply check that polygon is not complex, or not self-intersecting ? One way of doing this is brute-force way -> we can check every polygon edge pair for intersection. If there are some edges which intersects, then polygon is complex, otherwise - simple. So by using this brute-force solution, complex polygon check simplifies to lines self-intersection problem. And How do we check if lines self-intersects ? One way is to find-out 2 linear equations of these lines: y = a1*x + b1 ; y = a2*x + b2. Then self-intersection point is simply where these equations equals: a1*x + b1 = a2*x + b2 --> x_intersection = (b2-b1)/(a1-a2). Substituting into any of these two equations we get y_intersection = (a1*b2-a2*b1)/(a1-a2). Next step - we need to check does lines segments intersects, not the whole lines. This is done just comparing does x_intersection is within x_min,x_max of both lines, the similar check apply for y_intersection. So line intersection check simplifies to finding linear equations slope and intercept constants. This is one way of self-intersection test of lines. But there is also other way to do it (if we don`t need exact intersection point) - suppose we have line1 with end-points l1p1,l1p2 and line2 with end-points l2p1,l2p2. Define function DIRECTION(point1,point2,point3) which returns the direction [CLOCKWISE,COUNTER_CLOCKWISE,LINE] in which we traverse path point1->point2->point3. By having such function we can easily define when 2 line segments intersects. Below are one example
when lines intersects:
Another example when lines do not intersects: 
So lines intersects when :
direction(l1p1,l1p2,l2p1) != direction(l1p1,l1p2,l2p2) AND
direction(l2p1,l2p2,l1p1) != direction(l2p1,l2p2,l1p2)
This type of lines intersection test is implemented in polygon self-intersection
test. So you can download
centroid XNA 3.1 project
and try experimenting by drawing various polygons and seeing where centroid is
computed. Final part - some results from this project (centroid is draw as black
pixel): Some convex polygons:
Now, more interesting -> concave polygons:
From the concave polygon examples (especially from first concave) can be seen
that centroid is not the average of (max,min) coordinates in shape. However in
some cases it can be that centroid coincides with AVERAGE(Min,Max) of figure
(for example for rectangle). But in general - it not. If to talk informally,
then centroid is simply the average of ALL points coordinates in shape. Finally
just some examples of complex polygons - as evidence that application detects
complex (or self-intersecting) polygons :-) :
Actually we can also compute centroids of complex polygon by using info from
above mentioned wikipedia site. That is - to get centroid of complex polygon we
need: 1. Decompose complex polygon into N simple polygons. 2. Compute area and
centroid of each simple polygon by method already explained in this article. 3.
Average computed centroids by
some formula. The main task is number 1. - How effectively split complex polygon into
simple ones. This task is left as exercise to the reader :-) Have fun with
centroids, polygons, XNA and 2D/3D programming in general !!
