import javax.swing.*;
import java.util.Random;
import java.awt.*;
import java.awt.geom.*;
import java.awt.event.*;
import static java.lang.Math.*;

// two issues - intersection criteria seem to be wrong
//   - need to store how all intersecting triangles are constraining movement, rather than responding to one at a time

public class Triangles implements Runnable {
    static boolean DEBUG = false;

    static final int WIDTH = 600;

    public static boolean pointInTriangle (double a0x, double a0y, double a1x, double a1y, double a2x, double a2y, double px, double py) {
        double a01_cross_a02 = (a1x - a0x) * (a2y - a0y) - (a1y - a0y) * (a2x - a0x);
        double a01_cross_a0p = (a1x - a0x) * (py  - a0y) - (a1y - a0y) * (px  - a0x);
        double a12_cross_a1p = (a2x - a1x) * (py  - a1y) - (a2y - a1y) * (px  - a1x);
        double a20_cross_a2p = (a0x - a2x) * (py  - a2y) - (a0y - a2y) * (px  - a2x);

        //~ System.out.println("a01_cross_a02 " + a01_cross_a02 + "\ta01_cross_a0p " + a01_cross_a0p + "\ta12_cross_a1p " + a12_cross_a1p + "\ta20_cross_a2p " + a20_cross_a2p);

        return ((a01_cross_a02 <= 0) && (a01_cross_a0p <= 0) && (a12_cross_a1p <= 0) && (a20_cross_a2p <= 0)) ||
            ((a01_cross_a02 >= 0) && (a01_cross_a0p >= 0) && (a12_cross_a1p >= 0) && (a20_cross_a2p >= 0));
    }

    static void testPointInTriangle (double a0x, double a0y, double a1x, double a1y, double a2x, double a2y, double px, double py, boolean expectedResult) {
        if (pointInTriangle(a0x, a0y, a1x, a1y, a2x, a2y, px, py) == expectedResult)
            System.out.print(" pass  ");
        else
            System.out.print("*FAIL* ");

        System.out.printf("pointInTriangle(%.2f, %.2f, %.2f, %.2f, %.2f, %.2f, %.2f, %.2f) == %b\n", a0x, a0y, a1x, a1y, a2x, a2y, px, py, expectedResult);
    }

    public static boolean linesIntersect (double a0x, double a0y, double a1x, double a1y, double b0x, double b0y, double b1x, double b1y) {
        double a0a1_cross_a0b0 = (a1x - a0x) * (b0y - a0y) - (a1y - a0y) * (b0x - a0x);
        double a0a1_cross_a0b1 = (a1x - a0x) * (b1y - a0y) - (a1y - a0y) * (b1x - a0x);

        //~ System.out.printf("a0a1_cross_a0b0 %.2f\ta0a1_cross_a0b1 %.2f\n", a0a1_cross_a0b0, a0a1_cross_a0b1);

        if (a0a1_cross_a0b0 * a0a1_cross_a0b1 > 0) return false; // b0 and b1 on same side of a

        double b0b1_cross_b0a0 = (b1x - b0x) * (a0y - b0y) - (b1y - b0y) * (a0x - b0x);
        double b0b1_cross_b0a1 = (b1x - b0x) * (a1y - b0y) - (b1y - b0y) * (a1x - b0x);

        //~ System.out.printf("b0b1_cross_b0a0 %.2f\tb0b1_cross_b0a1 %.2f\n", b0b1_cross_b0a0, b0b1_cross_b0a1);

        return (b0b1_cross_b0a0 * b0b1_cross_b0a1 <= 0); // a0 and a1 on different sides of b
    }

    static void testLinesIntersect (double a0x, double a0y, double a1x, double a1y, double b0x, double b0y, double b1x, double b1y, boolean expectedResult) {
        if (linesIntersect(a0x, a0y, a1x, a1y, b0x, b0y, b1x, b1y) == expectedResult)
            System.out.print(" pass  ");
        else
            System.out.print("*FAIL* ");

        System.out.printf("linesIntersect(%.2f, %.2f, %.2f, %.2f, %.2f, %.2f, %.2f, %.2f) == %b\n", a0x, a0y, a1x, a1y, b0x, b0y, b1x, b1y, expectedResult);
    }

    public static boolean trianglesIntersect (double a0x, double a0y, double a1x, double a1y, double a2x, double a2y, double b0x, double b0y, double b1x, double b1y, double b2x, double b2y) {
        if (pointInTriangle(a0x, a0y, a1x, a1y, a2x, a2y, b0x, b0y)) {
            //~ System.out.println("b0 in A");
            return true;
        }

        if (pointInTriangle(a0x, a0y, a1x, a1y, a2x, a2y, b1x, b1y)) {
            //~ System.out.println("b1 in A");
            return true;
        }

        if (pointInTriangle(a0x, a0y, a1x, a1y, a2x, a2y, b2x, b2y)) {
            //~ System.out.println("b2 in A");
            return true;
        }

        if (pointInTriangle(b0x, b0y, b1x, b1y, b2x, b2y, a0x, a0y)) {
            //~ System.out.println("a0 in B");
            return true;
        }

        if (pointInTriangle(b0x, b0y, b1x, b1y, b2x, b2y, a1x, a1y)) {
            //~ System.out.println("a1 in B");
            return true;
        }

        if (pointInTriangle(b0x, b0y, b1x, b1y, b2x, b2y, a2x, a2y)) {
            //~ System.out.println("a2 in B");
            return true;
        }

        if (linesIntersect(a0x, a0y, a1x, a1y, b0x, b0y, b1x, b1y)) {
            //~ System.out.println("a01 X b01");
            return true;
        }

        if (linesIntersect(a0x, a0y, a2x, a2y, b0x, b0y, b1x, b1y)) {
            //~ System.out.println("a02 X b01");
            return true;
        }

        if (linesIntersect(a0x, a0y, a1x, a1y, b0x, b0y, b2x, b2y)) {
            //~ System.out.println("a01 X b02");
            return true;
        }

        // believed to be sufficient

        return false;
    }

    Random random;

    static class Triangle {
        int     size;
        double  x;
        double  y;
        double  orient;
        Color   color;
        Path2D  path;
        double  norm_sin, norm_cos;
        double  delta_sin, delta_cos;
        double  apex_x, apex_y;
        double  port_x, port_y;
        double  star_x, star_y;

        Triangle (Triangle other) {
            copy(other);
        }

        Triangle (Random random, int scale) {
            size = scale + random.nextInt(scale) + random.nextInt(scale);
            x = random.nextInt(WIDTH) - WIDTH/2;
            y = random.nextInt(WIDTH) - WIDTH/2;
            orient = random.nextInt(360);
            color = new Color(128 + random.nextInt(32), 64 + random.nextInt(32), 64 + random.nextInt(64), 192 + random.nextInt(32));
            recalculateControlPoints();
        }

        void draw (Graphics2D g) {
            if (path == null) {
                path = new Path2D.Double();
                buildPath();
            }

            g.setColor(color);
            g.fill(path);
        }

        void recalculateControlPoints () {
            if (x >  WIDTH/2) x =  WIDTH/2;
            if (x < -WIDTH/2) x = -WIDTH/2;
            if (y >  WIDTH/2) y =  WIDTH/2;
            if (y < -WIDTH/2) y = -WIDTH/2;

            norm_sin = sin(toRadians(orient));
            norm_cos = cos(toRadians(orient));

            delta_sin = size * norm_sin;
            delta_cos = size * norm_cos;

            apex_x = x + delta_sin;
            apex_y = y + delta_cos;

            port_x = x - delta_sin - 0.5 * delta_cos;
            port_y = y - delta_cos + 0.5 * delta_sin;

            star_x = x - delta_sin + 0.5 * delta_cos;
            star_y = y - delta_cos - 0.5 * delta_sin;
        }

        void buildPath () {
            path.moveTo(apex_x, apex_y);
            path.lineTo(port_x, port_y);
            path.lineTo(star_x, star_y);
        }

        boolean intersects (Triangle other) {
            return trianglesIntersect(this.apex_x, this.apex_y, this.port_x, this.port_y, this.star_x, this.star_y,
                    other.apex_x, other.apex_y, other.port_x, other.port_y, other.star_x, other.star_y);
        }

        void copy (Triangle other) {
            this.size   = other.size;
            this.x      = other.x;
            this.y      = other.y;
            this.orient = other.orient;
            this.color  = color;
            this.path   = null;
            recalculateControlPoints();
        }

        void repel (Triangle other, double weight) {
            double d2      = (this.x - other.x)  * (this.x - other.x)  + (this.y - other.y)  * (this.y - other.y);
            double d2_apex = (apex_x - other.x) * (apex_x - other.x) + (apex_y - other.y) * (apex_y - other.y);
            double d2_tail = (x - delta_sin - other.x) * (x - delta_sin - other.x) + (y - delta_cos - other.y) * (y - delta_cos - other.y);

            if (d2_apex < d2_tail) {
                double cross = (apex_x - x) * (other.y - y) - (apex_y - y) * (other.x - x);

                if (cross < 0) orient -= weight * 5;
                if (cross > 0) orient += weight * 5.5;
            }

            if (d2 > 1) {
                double d = sqrt(d2);
                //~ System.out.println("(this.x - other.x) / d\t" + ((this.x - other.x) / d));
                this.x  += weight * (this.x - other.x) / d;
                this.y  += weight * (this.y - other.y) / d;
            } else {
                this.x  += weight * norm_sin;
                this.y  += weight * norm_cos;
                //~ System.out.println("norm_sin\t" + norm_sin);
                //~ this.orient += 1.5;
            }
        }
    }

    final Triangle[] triangles;
    final Triangle[] triangles1;
    final Triangle[] triangles2;
    final int[] fit;
    final int[] fit1;

    public Triangles (String...args) {
        int trianglecount = (args.length > 0) ? Integer.parseInt(args[0]) : 23;
        int seed = (args.length > 1) ? Integer.parseInt(args[1]) : 23;

        random = new Random(seed);
        triangles = new Triangle[trianglecount];
        triangles1 = new Triangle[trianglecount];
        triangles2 = new Triangle[trianglecount];
        fit = new int[trianglecount];
        fit1 = new int[trianglecount];

        int scale = 10 * (5 - Math.min(trianglecount, 80)/20);

        for (int i = 0; i < trianglecount; ++i)
            fit[i] = trianglecount;

        for (int i = 0; i < trianglecount; ++i)
            triangles[i] = makeElement(random, scale);

        for (int i = 0; i < trianglecount; ++i)
            triangles1[i] = makeElement(random, scale);

        for (Triangle triangle : triangles)
            triangle.recalculateControlPoints();

        anneal(1,1,random);
    }

    Triangle makeElement (Random random, int scale) {
        return new Triangle(random, scale);
    }

    String getTitle () {
        return "Triangle Storm";
    }

    public void run () {
        final JFrame frame = new JFrame(getTitle());

        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

        final JPanel panel = new JPanel() {
            public void paintComponent(Graphics g) {
                super.paintComponent(g);

                Graphics2D g2D = (Graphics2D)g;

                g2D.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON );

                g2D.translate(getWidth() / 2, getHeight() / 2);

                for (Triangle triangle : triangles)
                    triangle.draw(g2D);


                if (DEBUG) {
                    int trianglecount = triangles.length;

                    for (int i = 0; i < trianglecount; ++i) {
                        Triangle triangle = triangles[i];
                        Triangle triangle1 = triangles1[i];

                        g2D.setColor(Color.BLACK);
                        g2D.drawLine( (int)triangle1.apex_x, (int)triangle1.apex_y, (int)triangle1.port_x, (int)triangle1.port_y );
                        g2D.drawLine( (int)triangle1.port_x, (int)triangle1.port_y, (int)triangle1.star_x, (int)triangle1.star_y );
                        g2D.drawLine( (int)triangle1.star_x, (int)triangle1.star_y, (int)triangle1.apex_x, (int)triangle1.apex_y );
                        g2D.setColor(Color.BLUE);
                        g2D.drawLine( (int)triangle.x, (int)triangle.y, (int)triangle1.x, (int)triangle1.y );
                    }

                    g2D.setColor(Color.RED);

                    for (int i = 0; i < trianglecount; ++i) {
                        for (int j = 0; j < trianglecount; ++j) {
                            if (i != j) {
                                if (triangles[j].intersects(triangles[i])) {
                                    g2D.drawLine((int)triangles[j].x, (int)triangles[j].y, (int)triangles[i].x, (int)triangles[i].y);
                                }
                            }
                        }

                        //~ if (fit[i] > 0)
                            g2D.drawString(""+fit[i], (int)triangles[i].x, (int)triangles[i].y);
                    }
                }
            }
        };

        frame.setLayout(new BorderLayout());
        frame.add(panel, BorderLayout.CENTER);
        frame.setSize(WIDTH + 80, WIDTH + 80);
        frame.setVisible(true);

        new Timer(200, new ActionListener() {
            double ticks = 1;
            public void actionPerformed(ActionEvent evt) {
                ticks += 0.1;
                anneal(5.0/sqrt(ticks), 10.0/sqrt(ticks), random);
                panel.repaint();
            }
        }).start();
    }

    void anneal (double gravity, double weight, Random random) {
        final int trianglecount = triangles.length;

        // make a copy of the triangles
        for (int i = 0; i < trianglecount; ++i) {
            fit[i] = 0;
            fit1[i] = 0;
            triangles1[i].copy(triangles[i]);
        }

        // count intersections before moving
        for (int i = 0; i < trianglecount; ++i) {
            for (int j = 0; j < trianglecount; ++j) {
                if (i != j) {
                    if (triangles[j].intersects(triangles[i])) {
                        ++fit[i];
                        ++fit[j];
                        if (fit[i] == 1 || random.nextInt(fit[i]) == 0)
                            triangles2[i] = triangles[j];
                        if (fit[j] == 1 || random.nextInt(fit[j]) == 0)
                            triangles2[j] = triangles[i];
                    }
                }
            }
        }

        // gravitate triangles to centre
        for (int i = 0; i < trianglecount; ++i) {
            Triangle triangle = triangles1[i];

            if (fit[i] == 0) {
                double dist = sqrt((triangle.x * triangle.x) + (triangle.y * triangle.y));
                triangle.x -= gravity * triangle.x / dist;
                triangle.y -= gravity * triangle.y / dist;
            } else {
                triangle.repel(triangles2[i], weight);
            }

            triangle.recalculateControlPoints();
        }

        // test triangles for collisions
        for (int i = 0; i < trianglecount; ++i) {
            for (int j = 0; j < trianglecount; ++j) {
                if (i != j) {
                    if (triangles1[j].intersects(triangles1[i])) {
                        ++fit1[i];
                        ++fit1[j];
                    }
                }
            }
        }

        // select the best triangles
        for (int i = 0; i < trianglecount; ++i) {
            //~ System.out.printf("i %d fit %d fit-1 %d\n", i, fit[i], fit1[i]);
            if (fit1[i] < fit[i] || fit1[i] == 0 || random.nextInt(3) == 0) {
                triangles[i].copy(triangles1[i]);
            }
        }
    }

    public static void main (String...args) {
        if (args.length < 1 || !"test".equals(args[0])) {
            DEBUG = args.length > 0 && "debug".equals(args[0]);
            SwingUtilities.invokeLater(new Triangles(args));
        } else {
            runTests();
        }
    }

    public static void runTests () {
        testPointInTriangle(0, 0, 3, 0, 0, 4, 1, 1, true);
        testPointInTriangle(0, 0, 0, 4, 3, 0, 1, 1, true);
        testPointInTriangle(0, 0, 3, 0, 0, 4, 3, 4, false);
        testPointInTriangle(0, 0, 3, 0, 0, 4, -1, 2, false);
        testPointInTriangle(0, 0, 3, 0, 0, 4, 2, -2, false);

        testLinesIntersect(0, 0, 1, 1, 0, 1, 1, 0, true);
        testLinesIntersect(0, 0, 0, 1, 1, 0, 1, 1, false);
        testLinesIntersect(-68.09, -227.70, -49.02, -47.29, -53.86, 34.75, 41.00, -56.97, false);
    }
}