XNA quest for centroid of polygon

Now we will talk about XNA Framework and How to find geometrical center of polygon (aka. so called centroid). At first - Why do we need centroid at all ? Well... for example - for some graphics applications we may want drag&drop shape by it`s centroid. Or maybe in some game applications we may need to find shape`s center of gravity, for simulating physics of balancing objects around center of gravity. And in cases when shape material density is uniform (the same over shape) then shape geometrical center (centroid) is also center of gravity (or center of mass). So lets begin search of centroid... For this you will need: - Visual Studio 2008 - XNA 3.1 Framework First - some notes about XNA framework. It`s a pitty that such great 2D/3D .NET library doesn`t have 2D primitives drawing routines. Well, actually it has some, but for being able to draw some 2D primitives like points and lines, you should dig deeply in 3D knowledge - for drawing mentioned primitives in MSDN way you should define 3D vectors and 3D viewports !! What the hell ? If user only wants 2D stuff, it means that all 3D stuff should be abstracted out of the view. So that at the end, framework should have separate levels of abstraction into 2D and 3D. But this is not the case about drawing 2D primtives... So one way of drawing point in non-MSDN way is to generate small rectangle texture in run-time and draw this generated texture on screen. Next thing is drawing a simple line in non-MSDN way. Recipe for that - we take generated 2D rectangle texture earlier and draw it as line by scaling and rotating it as needed. After defining this stuff we have all prerequisites for target problem. Now- How we will find centroid of polygon ? This is not that hard. According to wikipedia centroid formulas can be computed simply, assuming we have polygon vertex coordinates and assuming polygon is not complex. So centroid computation algorithm in C# is this:

---

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 !!