/** Polygon, any number of points, may be concave
 * @author: Phil Gage
 */
class Polygon extends BoundedPlane {
    Point vertex[];
    double x[], y[];
    private Vector3 temp = new Vector3();

    Polygon (Point vertex[], Color color) {
        super(color);
        if (vertex.length < 3) {
            System.out.println("Error, Polygon() must have at least 3 vertices");
            return;
        }
        this.vertex = vertex;
        // Set point on plane to first vertex
        point = vertex[0];
        // Get normal by cross product of first 3 vertices
        normal = new Vector3(vertex[0]);
        normal.subtract(vertex[1]);
        temp.set(vertex[2]);
        temp.subtract(vertex[1]);
        normal.cross(temp);
        normal.normalize();
        d = -vertex[0].dot(normal);
        this.extent = new Extent();
//        extent = getExtent ();
        getExtent ();
//System.out.println("extent="+extent);
        x = new double[vertex.length+1];
        y = new double[vertex.length+1];
    }

    /** Triangle */
    Polygon (Point p1, Point p2, Point p3, Color color) {
        this (new Point[] {p1,p2,p3}, color);
    }

    /** Quadrilateral */
    Polygon (Point p1, Point p2, Point p3, Point p4, Color color) {
        this (new Point[] {p1,p2,p3,p4}, color);
    }

    /** Returns positive if ray intersects polygon */
    double intersect (Ray ray, Intersection intersection) {
        double fraction, xintercept;
        int count = 0;
        // Check if ray intersects extent first (to speed up)
//        if (update?) getExtent ();
        double t = super.intersect (ray,intersection);
        if (t > 0.0) {
            // Find dominant normal axis, project onto other two
            // Subtract the intersection.point to center about origin
            // (Could have one loop outside if, but slower)
            if (normal.x > normal.y && normal.x > normal.z) {
                for (int i=0; i<vertex.length; i++) {
                    x[i] = vertex[i].z - intersection.point.z;
                    y[i] = vertex[i].y - intersection.point.y;
                }
            }
            else if (normal.y > normal.x && normal.y > normal.z) {
                for (int i=0; i<vertex.length; i++) {
                    x[i] = vertex[i].x - intersection.point.x;
                    y[i] = vertex[i].z - intersection.point.z;
                }
            }
            else {
                for (int i=0; i<vertex.length; i++) {
                    x[i] = vertex[i].x - intersection.point.x;
                    y[i] = vertex[i].y - intersection.point.y;
                }
            }

            // Copy first point as last to simplify loop below
            x[vertex.length] = x[0];
            y[vertex.length] = y[0];

            // Count polygon side intersections with positive X axis
            // Use "<=" and ">" to avoid counting same vertex twice
            for (int i=0; i<vertex.length; i++) {
                if ((y[i] <= 0.0 && y[i+1] > 0.0) ||
                    (y[i] > 0.0 && y[i+1] <= 0.0)) {
                    // If both Xs right, count, else if one right,
                    // then check, else skip (to speed up only)
                    if (x[i] > 0.0 && x[i+1] > 0.0)
                        ++count;
                    else if (x[i] > 0.0 || x[i+1] > 0.0) {
                        // this interpolation could be improved...
                        fraction = y[i] / (y[i] - y[i+1]);
                        xintercept = fraction * x[i+1] +
                                     (1.0 - fraction)*x[i];
                        if (xintercept > 0.0)
                            ++count;
                    }
                }
            }

            // If even number of intersections, point not in polygon
            if ((count % 2) == 0)
                t = 0.0;
        }
        return t;
    }

    Extent getExtent () {
        extent.min.set(Constants.INFINITY,Constants.INFINITY,Constants.INFINITY);
        extent.max.set(-Constants.INFINITY,-Constants.INFINITY,-Constants.INFINITY);
        for (int i=0; i<vertex.length; i++) {
            if (extent.min.x > vertex[i].x) extent.min.x = vertex[i].x;
            if (extent.min.y > vertex[i].y) extent.min.y = vertex[i].y;
            if (extent.min.z > vertex[i].z) extent.min.z = vertex[i].z;
            if (extent.max.x < vertex[i].x) extent.max.x = vertex[i].x;
            if (extent.max.y < vertex[i].y) extent.max.y = vertex[i].y;
            if (extent.max.z < vertex[i].z) extent.max.z = vertex[i].z;
        }
        // If extent dimension is zero, increase a bit
        if (Math.abs(extent.min.x - extent.max.x)<Constants.EPSILON) {
            extent.min.x -= 0.1;
            extent.max.x += 0.1;
        }
        if (Math.abs(extent.min.y - extent.max.y)<Constants.EPSILON) {
            extent.min.y -= 0.1;
            extent.max.y += 0.1;
        }
        if (Math.abs(extent.min.z - extent.max.z)<Constants.EPSILON) {
            extent.min.z -= 0.1;
            extent.max.z += 0.1;
        }
        return extent;
    }
}