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 vertices)
{
if (vertices == null)
return new Point(0, 0);
List hull = null;
if (vertices.size() < 2)
hull = new ArrayList(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);
}
