Tag: math

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);
    }

Find Convex hull of given points using Gift wrapping algorithm

This is implementation of Grift wrapping algorithm for finding convex hull.

  private static final Integer ZERO = new Integer(0);


/**
     * Find Convex hull of given points
     * 
     * @ref http://en.wikipedia.org/wiki/Gift_wrapping_algorithm
     * @param vertices
     * @return
     */
    private static List findConvexHull(final List vertices)
    {
        if (vertices == null)
            return Collections.emptyList();

        if (vertices.size() < 3)
            return vertices;

        final List points = new ArrayList(vertices);
        final List hull = new ArrayList();
        Point pointOnHull = getExtremePoint(points, true);
        Point endpoint = null;
        do
        {
            hull.add(pointOnHull);
            endpoint = points.get(0);

            for (final Point r : points)
            {
                // Distance is used to find the outermost point -
                final int turn = findTurn(pointOnHull, endpoint, r);
                if (endpoint.equals(pointOnHull) || turn == -1 || turn == 0
                    && dist(pointOnHull, r) > dist(endpoint, pointOnHull))
                {
                    endpoint = r;
                }
            }
            pointOnHull = endpoint;
        } while (!endpoint.equals(hull.get(0))); // we are back at the start

        return hull;
    }


    private static double dist(final Point p, final Point q)
    {
        final double dx = (q.x - p.x);
        final double dy = (q.y - p.y);
        return dx * dx + dy * dy;
    }


   /**
     * Returns -1, 0, 1 if p,q,r forms a right, straight, or left turn. 
     * 1 = left, -1 = right, 0 = none
     * 
     * @ref http://www-ma2.upc.es/geoc/mat1q1112/OrientationTests.pdf
     * @param p
     * @param q
     * @param r
     * @return 1 = left, -1 = right, 0 = none
     */
    private static int findTurn(final Point p, final Point q, final Point r)
    {
        final int x1 = (q.x - p.x) * (r.y - p.y);
        final int x2 = (r.x - p.x) * (q.y - p.y);
        final int anotherInteger = x1 - x2;
        return ZERO.compareTo(anotherInteger);
    }