/**
 * 
 */

package math.geom2d.grid;

import java.util.ArrayList;
import java.util.Collection;

import math.geom2d.Box2D;
import math.geom2d.Point2D;
import math.geom2d.point.PointArray2D;
import math.geom2d.point.PointSet2D;
import math.geom2d.line.LineSegment2D;
import math.geom2d.line.StraightLine2D;
import math.geom2d.line.LinearShape2D;

/**
 * Defines a triangle grid, with various size and orientation. The grid contains
 * triangle with all edges the same length.
 * 
 * @author dlegland
 */
public class TriangleGrid2D implements Grid2D {

    double x0    = 0;
    double y0    = 0;
    double s     = 1;

    double theta = 0;

    /**
     * Returns TRUE if the number n is even (like 0, 2, 4...).
     * 
     * @param n an integer
     * @return TRUE if n is even.
     */
    private final static boolean isEven(int n) {
        return Math.abs(n*.5-Math.floor(n*.5))<.25;
    }

    public TriangleGrid2D() {
        this(0, 0, 1, 0);
    }

    /**
     * @param s size of the triangle tile
     */
    public TriangleGrid2D(double s) {
        this(0, 0, s, 0);
    }

    /**
     * @param x0 x-coord of grid origin
     * @param y0 y-coord of grid origin
     */
    public TriangleGrid2D(double x0, double y0) {
        this(x0, y0, 1, 0);
    }

    /**
     * @param x0 x-coord of grid origin
     * @param y0 y-coord of grid origin
     * @param s size of the triangle tile
     */
    public TriangleGrid2D(double x0, double y0, double s) {
        this(x0, y0, s, 0);
    }

    /**
     * @param x0 x-coord of grid origin
     * @param y0 y-coord of grid origin
     * @param s size of the triangle tile
     * @param theta orientation of the grid with horizontal
     */
    public TriangleGrid2D(double x0, double y0, double s, double theta) {
        this.x0 = x0;
        this.y0 = y0;
        this.s = s;
        this.theta = theta;
    }

    /**
     * Assumes unit grid.
     * 
     * @param point the grid origin
     */
    public TriangleGrid2D(Point2D point) {
        this(point.x(), point.y(), 1, 0);
    }

    /**
     * @param point the grid origin
     * @param s size of the triangle tile
     */
    public TriangleGrid2D(Point2D point, double s) {
        this(point.x(), point.y(), s, 0);
    }

    /**
     * @param point the grid origin
     * @param s size of the triangle tile
     * @param theta orientation of the grid with horizontal
     */
    public TriangleGrid2D(Point2D point, double s, double theta) {
        this(point.x(), point.y(), s, theta);
    }

    /**
     * @deprecated grids are supposed to be immutable (0.8.0)
     */
    @Deprecated
    public void setOrigin(Point2D point) {
        this.x0 = point.getX();
        this.y0 = point.getY();
    }

    public Point2D getOrigin() {
        return new Point2D(x0, y0);
    }

    public double getSize() {
        return s;
    }

    /**
     * @deprecated grids are supposed to be immutable (0.8.0)
     */
    @Deprecated
    public void setSize(double s) {
        this.s = s;
    }

    /**
     * @deprecated grids are supposed to be immutable (0.8.0)
     */
    @Deprecated
    public void setAngle(double theta) {
        this.theta = theta;
    }

    public double getTheta() {
        return theta;
    }

    /*
     * (non-Javadoc)
     * 
     * @see math.geom2d.grid.Grid2D#getClosestVertex(Point2D)
     */
    public Point2D getClosestVertex(Point2D point) {
        // create the base line
        double cot = Math.cos(theta);
        double sit = Math.sin(theta);
        StraightLine2D baseLine = new StraightLine2D(x0, y0, cot, sit);

        // compute distance to line, and deduces indices of surrounding lines
        double s2 = s*Math.sqrt(3)/2;
        double d = baseLine.signedDistance(point);
        int n1 = (int) Math.floor(d/s2);
        int n2 = (int) Math.ceil(d/s2);

        // compute the two surrounding lines
        StraightLine2D line1 = baseLine.parallel(n1*s2);
        StraightLine2D line2 = baseLine.parallel(n2*s2);

        // projection of point on the surrounding lines
        double t = line1.project(point);

        Point2D p1, p2, p3;
        if (isEven(n1)) {
            p1 = line1.point(Math.floor(t/s)*s);
            p2 = line1.point(Math.ceil(t/s)*s);
            p3 = line2.point((Math.floor(t/s)+.5)*s);
        } else {
            p1 = line1.point((Math.floor(t/s)+.5)*s);
            p2 = line2.point(Math.floor(t/s)*s);
            p3 = line2.point(Math.ceil(t/s)*s);
        }

        Point2D res = p1;
        double minDist = res.distance(point);

        double d2 = p2.distance(point);
        if (d2 getEdges(Box2D box) {

        // init the array of line segments
        ArrayList array = new ArrayList();

        double d = s*Math.sqrt(3)/2;
        double dmin, dmax;

        for (int k = 0; k<3; k++) {
            // consider a line through origin with one of the 2 orientations
            double theta2 = this.theta+Math.PI*(k)/3.0;
            double cot = Math.cos(theta2);
            double sit = Math.sin(theta2);
            StraightLine2D baseLine = new StraightLine2D(x0, y0, cot, sit);

            // get extreme distances of box corners to the base line
            dmin = Double.POSITIVE_INFINITY;
            dmax = Double.NEGATIVE_INFINITY;
            for (Point2D point : box.vertices()) {
                double dist = baseLine.signedDistance(point);
                dmin = Math.min(dmin, dist);
                dmax = Math.max(dmax, dist);
            }

            // compute the number of lines in each direction
            double s2 = s*Math.sqrt(3)/2;
            int i0 = (int) Math.ceil(dmin/s2);
            int i1 = (int) Math.floor(dmax/s2);

            // add each clipped line
            for (int i = i0; i<=i1; i++) {
                StraightLine2D line = baseLine.parallel(d*i);
                for (LinearShape2D arc : line.clip(box)) {
                    if (arc instanceof LineSegment2D)
                        array.add((LineSegment2D) arc);
                }
            }
        }
        return array;
    }

    /*
     * (non-Javadoc)
     * 
     * @see math.geom2d.grid.Grid2D#getVertices(math.geom2d.Box2D)
     */
    public PointSet2D getVertices(Box2D box) {

        // init the array of line segments
        ArrayList array = new ArrayList();

        double d = s*Math.sqrt(3)/2;
        double dmin, dmax;

        // consider a line through origin with one of the 2 orientations
        double cot = Math.cos(theta);
        double sit = Math.sin(theta);
        StraightLine2D baseLine = new StraightLine2D(x0, y0, cot, sit);

        // get extreme distances of box corners to the base line
        dmin = Double.POSITIVE_INFINITY;
        dmax = Double.NEGATIVE_INFINITY;
        for (Point2D point : box.vertices()) {
            double dist = baseLine.signedDistance(point);
            dmin = Math.min(dmin, dist);
            dmax = Math.max(dmax, dist);
        }

        // compute the number of lines in each direction
        int i0 = (int) Math.ceil(dmin/s);
        int i1 = (int) Math.floor(dmax/s);

        // consider only the first line
        for (int i = i0; i<=i1; i++) {
            // compute supporting line, supposing that the norm of the
            // direction vector equals 1 (should be the case)
            StraightLine2D line = baseLine.parallel(d*i);

            // extract the line segment
            LineSegment2D seg = (LineSegment2D) line.clip(box).firstCurve();

            // compute position of extreme points, which is also the geodesic
            // distance
            double t1 = line.position(seg.firstPoint());
            double t2 = line.position(seg.lastPoint());

            // check if point on this line are shifted or not
            double t0 = isEven(i) ? 0 : s*.5;

            // compute the number of points in each side of the origin
            int j0 = (int) Math.ceil((t1-t0)/s);
            int j1 = (int) Math.floor((t2-t0)/s);

            // iterate on points
            if (j1