java

Calculate centroid of 2D non crossing polygon

Calculate centroid of 2D non crossing polygon,
To accommodate that points are correct using Gift wrapping algorithm(Finding Convex Hull)

Test case

 
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertNotNull;
 
import java.awt.Point;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
 
import org.junit.Test;
 
public class MathUtilTest
{
 
    @Test
    public void computeCentroidWithHull()
    {
        Point p1 = new Point(1, 1);
        Point p2 = new Point(2, 2);
        Point p3 = new Point(3, 1);
        Point p4 = new Point(1, 0);
        Point p5 = new Point(0, 1);
        Point p6 = new Point(5, 5);
 
        Point centroid2d = MathUtil.centroid2D(Arrays.asList(p1, p2, p3, p4, p5, p6));
        assertEquals(new Point(2, 1), centroid2d);
    }
 
    @Test
    public void computeCentroid()
    {
        Point p1 = new Point(1, 1);
        Point p2 = new Point(2, 2);
        Point p3 = new Point(3, 1);
 
        Point centroid2d = MathUtil.centroid2D(Arrays.asList(p1, p2, p3));
        assertEquals(new Point2D(2, 1), centroid2d);
    }
}

Implementation

    /**
     * Calculate centroid of 2D non crossing polygon, To accommodate that points
     * are correct using Gift wrapping algorithm(Finding Convex Hull)
     * 
     * @ref http://en.wikipedia.org/wiki/Centroid#Centroid_of_polygon
     * @param vertices
     * @return
     */
    public static Point centroid2D(final List<Point> vertices)
    {
        if (vertices == null)
            return new Point(0, 0);
 
        List<Point> hull = null;
        if (vertices.size() < 2)
            hull = new ArrayList<Point>(vertices);
        else
            hull = findConvexHull(vertices);
 
        // Now we can calculate the centroid of polygon using standard mean
        final int len = hull.size();
        final double xy[] = new double[] { 0, 0 };
        for (int i = 0; i < len; ++i)
        {
            final Point p = hull.get(i);
            xy[0] += p.getX();
            xy[1] += p.getY();
        }
 
        final int x = (int) (xy[0] / len);
        final int y = (int) (xy[1] / len);
 
        return new Point(x, y);
    }

Leave a Reply

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

* Copy This Password *

* Type Or Paste Password Here *