Find a Region centroid in C#

[Find a Region's centroid]

This example shows how to find a Region centroid, the point that is at the “center” of the Region. If you were to make the region out of a thin piece of wood, you could balance it at the centroid.

The example Find the area where two or more circles overlap in C# shows how to find a Region that represents the area where two or more circles overlap. This example shows how to find the centroid of that Region.

To find a region’s centroid, you need to calculate its moments. The moment of a region with respect to a line is the area of the region multiplied by the distance from the centroid to the line: moment = area × distance.

If you use the X axis as the line, then the moment equation is Mx = area × X and the distance to the line is simply the centroid’s X coordinate.

If you rearrange that equation a bit, you can get X = Mx / area. That means if you can calculate the area and the moment with respect to the X axis, then you can calculate the centroid’s X coordinate.

That may not seem like much of an improvement, but it turns out that you can calculate the region’s moment directly by chopping it into rectangles. The centroid of a rectangle lies at its center. You can multiply the centroid’s X coordinate by the rectangle’s area to get its moment.

Now add up all of the moments to get the moment for the whole shape. (If you have equations representing the region, you can use calculus to integrate over the area, adding up the incremental rectangles’ moments.) Using the resulting moment, you can calculate the X coordinate for the combined shape’s centroid.

(Repeat the steps with respect to the Y axis to find the centroid’s Y coordinate.)

The Region object’s GetRegionScans method returns an array of rectangles representing the region. You can use those rectangles to calculate the Region object’s moments Mx and My. From those you can calculate its centroid.

The following RegionCentroid method finds the centroid of a Region by using its scan rectangles. (It’s actually a lot shorter than the preceding explanation.)

// Return the centroid of the region.
private PointF RegionCentroid(Region region, Matrix transform)
{
    float mx = 0;
    float my = 0;
    float total_weight = 0;
    foreach (RectangleF rect in region.GetRegionScans(transform))
    {
        float rect_weight = rect.Width * rect.Height;
        mx += rect_weight * (rect.Left + rect.Width / 2f);
        my += rect_weight * (rect.Top + rect.Height / 2f);
        total_weight += rect_weight;
    }

    return new PointF(mx / total_weight, my / total_weight);
}

The code initializes the moment values mx and my, and the region’s total weight. It then loops through the Region object’s rectangles,a dding each rectangle’s moments to mx and my. It also adds each rectangle’s weight to the total.

When the loop finishes, the code divides the moments by the total weight to get the centroid’s X and Y coordinates.

The following Paint event handler draws the circles you select, their intersection, and the intersection’s centroid.

// Draw the circles.
private void Form1_Paint(object sender, PaintEventArgs e)
{
    e.Graphics.SmoothingMode = SmoothingMode.AntiAlias;

    // Find the intersection of all circles.
    Region intersection = FindCircleIntersections(Centers, Radii);

    // Draw the region.
    if (intersection != null)
    {
        e.Graphics.FillRegion(Brushes.LightGreen, intersection);

        // Get the region's centroid.
        PointF centroid = RegionCentroid(intersection,
            e.Graphics.Transform);
        e.Graphics.FillEllipse(Brushes.Red,
            centroid.X - 3, centroid.Y - 3, 7, 7);
    }

    // Draw the circles.
    for (int i = 0; i < Centers.Count; i++)
    {
        e.Graphics.DrawEllipse(Pens.Blue,
            Centers[i].X - Radii[i], Centers[i].Y - Radii[i],
            2 * Radii[i], 2 * Radii[i]);
    }
}

This code calls FindCircleIntersections (described in the earlier post to get the Region representing the circles’ region of intersection.

If the Region isn’t null, the code fills it with light green. It use RegionCentroid to find the centroid and marks it with a red circle.

The event handler finishes by drawing the circles.


Download Example   Follow me on Twitter   RSS feed   Donate




This entry was posted in algorithms, geometry, graphics, mathematics and tagged , , , , , , , , , , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *