Polygon.java

/*************************************************************************
 *  Compilation:  javac Polygon.java
 *  Execution:    java Polygon
 *
 *  Implementation of 2D polygon, possibly intersecting.
 *
 *  Centroid calculation assumes polygon is nonempty (o/w area = 0)
 *
 *************************************************************************/

public class Polygon { 
    private int N;        // number of points in the polygon
    private Point[] a;    // the points, setting points[0] = points[N]
   
    // default buffer = 4
    public Polygon() {
        N = 0;
        a = new Point[4];
    }


    // double size of array
    private void resize() {
        Point[] temp = new Point[2*N+1];
        for (int i = 0; i <= N; i++) temp[i] = a[i];
        a = temp;
    }

    // return size
    public int size() { return N; }

    // draw polygon
    public void draw() {
        for (int i = 0; i < N; i++)
            a[i].drawTo(a[i+1]);
    }


    // add point p to end of polygon
    public void add(Point p) {
        if (N >= a.length - 1) resize();   // resize array if needed
        a[N++] = p;                        // add point
        a[N] = a[0];                       // close polygon
    }

    // return the perimeter
    public double perimeter() {
        double sum = 0.0;
        for (int i = 0; i < N; i++)
            sum = sum + a[i].distanceTo(a[i+1]);
        return sum;
    }

    // return signed area of polygon
    public double area() {
        double sum = 0.0;
        for (int i = 0; i < N; i++) {
            sum = sum + (a[i].x() * a[i+1].y()) - (a[i].y() * a[i+1].x());
        }
        return 0.5 * sum;
    }

    // return the centroid of the polygon
    public Point centroid() {
        double cx = 0.0, cy = 0.0;
        for (int i = 0; i < N; i++) {
            cx = cx + (a[i].x() + a[i+1].x()) * (a[i].x() * a[i+1].y() - a[i].y() * a[i+1].x());
            cy = cy + (a[i].y() + a[i+1].y()) * (a[i].x() * a[i+1].y() - a[i].y() * a[i+1].x());
        }
        cx /= (6 * area());
        cy /= (6 * area());
        return new Point(cx, cy);
    }


    // does this Polygon contain the point p?
    // if p is on boundary then 0 or 1 is returned, and p is in exactly one point of every partition of plane
    // Reference: http://exaflop.org/docs/cgafaq/cga2.html
    public boolean contains(Point p) {
        int crossings = 0;
        double x = p.x(), y = p.y();
        for (int i = 0; i < N; i++) {
            int j = i + 1;
            boolean cond1 = (a[i].y() <= y) && (y < a[j].y());
            boolean cond2 = (a[j].y() <= y) && (y < a[i].y());
            boolean cond3 = x < (a[j].x() - a[i].x()) * (y - a[i].y()) / (a[j].y() - a[i].y()) + a[i].x();
            if ((cond1 || cond2)  && cond3) crossings++;
        }
        if (crossings % 2 == 1) return true;
        else                    return false; 
    }

    // return string representation of this point
    public String toString() {
        if (N == 0) return "[ ]";
        String s = "";
        s = s + "[ ";
        for (int i = 0; i <= N; i++)
            s = s + a[i] + " ";
        s = s + "]";
        return s;
    }


    // test client
    public static void main(String[] args) {
        int N = Integer.parseInt(args[0]);

        // a square
        Polygon poly = new Polygon();
        poly.add(new Point(0.5, 0.5));
        poly.add(new Point(0.7, 0.5));
        poly.add(new Point(0.7, 0.7));
        poly.add(new Point(0.5, 0.7));

        System.out.println("polygon    = " + poly);
        System.out.println("perimeter  = " + poly.perimeter());
        System.out.println("area       = " + poly.area());
        System.out.println("centroid   = " + poly.centroid());

        // generate N random points in the unit square and check what fraction are in the polygon
        int yes = 0;
        for (int i = 0; i < N; i++) {
            Point p = new Point();
            if (poly.contains(p)) yes++;
        }

        // true answer is = 0.04
        System.out.println("Fraction in circle = " + 1.0 * yes / N);


    }
}