pdfbox-trunk/pdfbox/src/main/java/org/apache/pdfbox/pdmodel/graphics/shading/ShadedTriangle.java
/*
 * Copyright 2014 The Apache Software Foundation.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.pdfbox.pdmodel.graphics.shading;

import java.awt.Point;
import java.awt.geom.Point2D;
import java.util.HashSet;
import java.util.Set;

/**
 * This is an assistant class for accomplishing type 4, 5, 6 and 7 shading. It
 * describes a triangle actually, which is used to compose a patch. It contains
 * the degenerated cases, a triangle degenerates to a line or to a point. This
 * was done as part of GSoC2014, Tilman Hausherr is the mentor.
 *
 * @author Shaola Ren
 */
class ShadedTriangle
{
    protected final Point2D[] corner; // vertices coordinates of a triangle
    protected final float[][] color;
    private final double area; // area of the triangle

    /*
     degree = 3 describes a normal triangle, 
     degree = 2 when a triangle degenerates to a line,
     degree = 1 when a triangle degenerates to a point
     */
    private final int degree;

    // describes a rasterized line when a triangle degerates to a line, otherwise null
    private final Line line;

    // corner's edge (the opposite edge of a corner) equation value
    private final double v0;
    private final double v1;
    private final double v2;

    /**
     * Constructor.
     *
     * @param p an array of the 3 vertices of a triangle
     * @param c an array of color corresponding the vertex array p
     */
    ShadedTriangle(Point2D[] p, float[][] c)
    {
        corner = p.clone(); // yes this is a shallow clone
        color = c.clone();
        area = getArea(p[0], p[1], p[2]);
        degree = calcDeg(p);

        if (degree == 2)
        {
            if (overlaps(corner[1], corner[2]) && !overlaps(corner[0], corner[2]))
            {
                Point p0 = new Point((int) Math.round(corner[0].getX()),
                        (int) Math.round(corner[0].getY()));
                Point p1 = new Point((int) Math.round(corner[2].getX()),
                        (int) Math.round(corner[2].getY()));
                line = new Line(p0, p1, color[0], color[2]);
            }
            else
            {
                Point p0 = new Point((int) Math.round(corner[1].getX()),
                        (int) Math.round(corner[1].getY()));
                Point p1 = new Point((int) Math.round(corner[2].getX()),
                        (int) Math.round(corner[2].getY()));
                line = new Line(p0, p1, color[1], color[2]);
            }
        }
        else
        {
            line = null;
        }

        v0 = edgeEquationValue(p[0], p[1], p[2]);
        v1 = edgeEquationValue(p[1], p[2], p[0]);
        v2 = edgeEquationValue(p[2], p[0], p[1]);
    }

    /**
     * Calculate the degree value of a triangle.
     *
     * @param p 3 vertices coordinates
     * @return number of unique points in the 3 vertices of a triangle, 3, 2 or
     * 1
     */
    private int calcDeg(Point2D[] p)
    {
        Set<Point> set = new HashSet<>();
        for (Point2D itp : p)
        {
            Point np = new Point((int) Math.round(itp.getX() * 1000), (int) Math.round(itp.getY() * 1000));
            set.add(np);
        }
        return set.size();
    }

    public int getDeg()
    {
        return degree;
    }

    /**
     * get the boundary of a triangle.
     *
     * @return {xmin, xmax, ymin, ymax}
     */
    public int[] getBoundary()
    {
        int[] boundary = new int[4];
        int x0 = (int) Math.round(corner[0].getX());
        int x1 = (int) Math.round(corner[1].getX());
        int x2 = (int) Math.round(corner[2].getX());
        int y0 = (int) Math.round(corner[0].getY());
        int y1 = (int) Math.round(corner[1].getY());
        int y2 = (int) Math.round(corner[2].getY());

        boundary[0] = Math.min(Math.min(x0, x1), x2);
        boundary[1] = Math.max(Math.max(x0, x1), x2);
        boundary[2] = Math.min(Math.min(y0, y1), y2);
        boundary[3] = Math.max(Math.max(y0, y1), y2);

        return boundary;
    }

    /**
     * Get the line of a triangle.
     *
     * @return points of the line, or null if this triangle isn't a line
     */
    public Line getLine()
    {
        return line;
    }

    /**
     * Whether a point is contained in this ShadedTriangle.
     *
     * @param p the target point
     * @return false if p is outside of this triangle, otherwise true
     */
    public boolean contains(Point2D p)
    {
        if (degree == 1)
        {
            return overlaps(corner[0], p) || overlaps(corner[1], p) || overlaps(corner[2], p);
        }
        else if (degree == 2)
        {
            Point tp = new Point((int) Math.round(p.getX()), (int) Math.round(p.getY()));
            return line.linePoints.contains(tp);
        }

        /*
         the following code judges whether a point is contained in a normal triangle, 
         taking the on edge case as contained
         */
        double pv0 = edgeEquationValue(p, corner[1], corner[2]);
        /*
         if corner[0] and point p are on different sides of line from corner[1] to corner[2], 
         p is outside of the triangle
         */
        if (pv0 * v0 < 0)
        {
            return false;
        }
        double pv1 = edgeEquationValue(p, corner[2], corner[0]);
        /*
         if vertex corner[1] and point p are on different sides of line from corner[2] to corner[0], 
         p is outside of the triangle
         */
        if (pv1 * v1 < 0)
        {
            return false;
        }
        double pv2 = edgeEquationValue(p, corner[0], corner[1]);
        /*
         only left one case:
         if corner[1] and point p are on different sides of line from corner[2] to corner[0], 
         p is outside of the triangle, otherwise p is contained in the triangle
         */
        return pv2 * v2 >= 0; // !(pv2 * v2 < 0)
    }

    /*
     check whether two points overlaps each other, as points' coordinates are 
     of type double, the coordinates' accuracy used here is 0.001
     */
    private boolean overlaps(Point2D p0, Point2D p1)
    {
        return Math.abs(p0.getX() - p1.getX()) < 0.001 && Math.abs(p0.getY() - p1.getY()) < 0.001;
    }

    /*
     two points can define a line equation, adjust the form of the equation to 
     let the rhs equals 0, calculate the lhs value by plugging the coordinate 
     of p in the lhs expression
     */
    private double edgeEquationValue(Point2D p, Point2D p1, Point2D p2)
    {
        return (p2.getY() - p1.getY()) * (p.getX() - p1.getX())
                - (p2.getX() - p1.getX()) * (p.getY() - p1.getY());
    }

    // calculate the area of a triangle
    private double getArea(Point2D a, Point2D b, Point2D c)
    {
        return Math.abs((c.getX() - b.getX()) * (c.getY() - a.getY())
                - (c.getX() - a.getX()) * (c.getY() - b.getY())) / 2.0;
    }

    /**
     * Calculate the color of a point.
     *
     * @param p the target point
     * @return an array denotes the point's color
     */
    public float[] calcColor(Point2D p)
    {
        int numberOfColorComponents = color[0].length;
        float[] pCol = new float[numberOfColorComponents];

        switch (degree)
        {
            case 1:
                for (int i = 0; i < numberOfColorComponents; i++)
                {
                    // average
                    pCol[i] = (color[0][i] + color[1][i] + color[2][i]) / 3.0f;
                }
                break;
            case 2:
                // linear interpolation
                Point tp = new Point((int) Math.round(p.getX()), (int) Math.round(p.getY()));
                return line.calcColor(tp);
            default:
                float aw = (float) (getArea(p, corner[1], corner[2]) / area);
                float bw = (float) (getArea(p, corner[2], corner[0]) / area);
                float cw = (float) (getArea(p, corner[0], corner[1]) / area);
                for (int i = 0; i < numberOfColorComponents; i++)
                {
                    // barycentric interpolation
                    pCol[i] = color[0][i] * aw + color[1][i] * bw + color[2][i] * cw;
                }
                break;
        }
        return pCol;
    }

    @Override
    public String toString()
    {
        return corner[0] + " " + corner[1] + " " + corner[2];
    }
}
